MathDB
Problems
Contests
National and Regional Contests
Ukraine Contests
Official Ukraine Selection Cycle
Ukraine Team Selection Test
2012 Ukraine Team Selection Test
8
8
Part of
2012 Ukraine Team Selection Test
Problems
(1)
-1 on a circle, after 2^k-1 steps, of multiplications
Source: Ukraine TST 2012 p8
5/1/2020
Call arrangement of
m
m
m
number on the circle
m
m
m
-negative, if all numbers are equal to
−
1
-1
−
1
. On the first step Andrew chooses one number on circle and multiplies it by
−
1
-1
−
1
. All other steps are similar: instead of the next number(clockwise) he writes its product with the number, written on the previous step. Prove that if
n
n
n
-negative arrangement in
k
k
k
steps becomes
n
n
n
-negative again, then
(
2
n
−
1
)
(2^n - 1)
(
2
n
−
1
)
-negative after
(
2
k
−
1
)
(2^k - 1)
(
2
k
−
1
)
steps becomes
(
2
n
−
1
)
(2^n - 1)
(
2
n
−
1
)
-negative again.
combinatorics