Problem

Source: Ukraine TST 2012 p8

Tags: combinatorics



parmenides51

01.05.2020 16:57

Call arrangement of $m$ number on the circle $m$-negative, if all numbers are equal to $-1$. On the first step Andrew chooses one number on circle and multiplies it by $-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$-negative arrangement in $k$ steps becomes $n$-negative again, then $(2^n - 1)$-negative after $(2^k - 1)$ steps becomes $(2^n - 1)$-negative again.