MathDB
Problems
Contests
National and Regional Contests
India Contests
India National Olympiad
2022 India National Olympiad
3
3
Part of
2022 India National Olympiad
Problems
(1)
INMO 2022
Source: INMO 2022 P3
3/6/2022
For a positive integer
N
N
N
, let
T
(
N
)
T(N)
T
(
N
)
denote the number of arrangements of the integers
1
,
2
,
⋯
N
1, 2, \cdots N
1
,
2
,
⋯
N
into a sequence
a
1
,
a
2
,
⋯
a
N
a_1, a_2, \cdots a_N
a
1
,
a
2
,
⋯
a
N
such that
a
i
>
a
2
i
a_i > a_{2i}
a
i
>
a
2
i
for all
i
i
i
,
1
≤
i
<
2
i
≤
N
1 \le i < 2i \le N
1
≤
i
<
2
i
≤
N
and
a
i
>
a
2
i
+
1
a_i > a_{2i+1}
a
i
>
a
2
i
+
1
for all
i
i
i
,
1
≤
i
<
2
i
+
1
≤
N
1 \le i < 2i+1 \le N
1
≤
i
<
2
i
+
1
≤
N
. For example,
T
(
3
)
T(3)
T
(
3
)
is
2
2
2
, since the possible arrangements are
321
321
321
and
312
312
312
(a) Find
T
(
7
)
T(7)
T
(
7
)
(b) If
K
K
K
is the largest non-negative integer so that
2
K
2^K
2
K
divides
T
(
2
n
−
1
)
T(2^n - 1)
T
(
2
n
−
1
)
, show that
K
=
2
n
−
n
−
1
K = 2^n - n - 1
K
=
2
n
−
n
−
1
. (c) Find the largest non-negative integer
K
K
K
so that
2
K
2^K
2
K
divides
T
(
2
n
+
1
)
T(2^n + 1)
T
(
2
n
+
1
)
INMO 2022
Arrangements