MathDB
Problems
Contests
National and Regional Contests
Indonesia Contests
Indonesia MO
2011 Indonesia MO
2
2
Part of
2011 Indonesia MO
Problems
(1)
Permutations of (1,...,n) such that sum of a_i/i is integer
Source: Indonesian Mathematics Olympiad 2011, Day 1, Problem 2
9/13/2011
For each positive integer
n
n
n
, let
s
n
s_n
s
n
be the number of permutations
(
a
1
,
a
2
,
⋯
,
a
n
)
(a_1, a_2, \cdots, a_n)
(
a
1
,
a
2
,
⋯
,
a
n
)
of
(
1
,
2
,
⋯
,
n
)
(1, 2, \cdots, n)
(
1
,
2
,
⋯
,
n
)
such that
a
1
1
+
a
2
2
+
⋯
+
a
n
n
\dfrac{a_1}{1} + \dfrac{a_2}{2} + \cdots + \dfrac{a_n}{n}
1
a
1
+
2
a
2
+
⋯
+
n
a
n
is a positive integer. Prove that
s
2
n
≥
n
s_{2n} \ge n
s
2
n
≥
n
for all positive integer
n
n
n
.
induction
number theory proposed