MathDB
Problems
Contests
National and Regional Contests
Canada Contests
Canada National Olympiad
2022 Canada National Olympiad
3
3
Part of
2022 Canada National Olympiad
Problems
(1)
Process combo
Source: CMO 2022 P3
3/12/2022
Vishal starts with
n
n
n
copies of the number
1
1
1
written on the board. Every minute, he takes two numbers
a
,
b
a, b
a
,
b
and replaces them with either
a
+
b
a+b
a
+
b
or
min
(
a
2
,
b
2
)
\min(a^2, b^2)
min
(
a
2
,
b
2
)
. After
n
−
1
n-1
n
−
1
there is
1
1
1
number on the board. Let the maximal possible value of this number be
f
(
n
)
f(n)
f
(
n
)
. Prove
2
n
/
3
<
f
(
n
)
≤
3
n
/
3
2^{n/3}<f(n)\leq 3^{n/3}
2
n
/3
<
f
(
n
)
≤
3
n
/3
.
combinatorics