MathDB
Problems
Contests
National and Regional Contests
Korea Contests
Korea National Olympiad
2016 Korea National Olympiad
4
4
Part of
2016 Korea National Olympiad
Problems
(1)
Number of n-tuples with given condition
Source: 2016 KMO Senior #4
11/12/2016
For a positive integer
n
n
n
,
S
n
S_n
S
n
is the set of positive integer
n
n
n
-tuples
(
a
1
,
a
2
,
⋯
,
a
n
)
(a_1,a_2, \cdots ,a_n)
(
a
1
,
a
2
,
⋯
,
a
n
)
which satisfies the following.(i).
a
1
=
1
a_1=1
a
1
=
1
.(ii).
a
i
+
1
≤
a
i
+
1
a_{i+1} \le a_i+1
a
i
+
1
≤
a
i
+
1
.For
k
≤
n
k \le n
k
≤
n
, define
N
k
N_k
N
k
as the number of
n
n
n
-tuples
(
a
1
,
a
2
,
⋯
a
n
)
∈
S
n
(a_1, a_2, \cdots a_n) \in S_n
(
a
1
,
a
2
,
⋯
a
n
)
∈
S
n
such that
a
k
=
1
,
a
k
+
1
=
2
a_k=1, a_{k+1}=2
a
k
=
1
,
a
k
+
1
=
2
.Find the sum
N
1
+
N
2
+
⋯
N
k
−
1
N_1 + N_2+ \cdots N_{k-1}
N
1
+
N
2
+
⋯
N
k
−
1
.
combinatorics