Consider $n$ lamps clockwise numbered from $1$ to $n$ on a circle.
Let $\xi$ to be a configuration where $0 \le \ell \le n$ random lamps are turned on. A cool procedure consists in perform, simultaneously, the following operations: for each one of the $\ell$ lamps which are turned on, we verify the number of the lamp; if $i$ is turned on, a signal of range $i$ is sent by this lamp, and it will be received only by the next $i$ lamps which follow $i$, turned on or turned off, also considered clockwise. At the end of the operations we verify, for each lamp, turned on or turned off, how many signals it has received. If it was reached by an even number of signals, it remains on the same state(that is, if it was turned on, it will be turned on; if it was turned off, it will be turned off). Otherwise, it's state will be changed.
The example for $n=4$, illustrates a configuration where lamps $2$ and $4$ are initially turned on. Lamp $2$ sends signal only for the lamps $3$ e $4$, while lamp $4$ sends signal for lamps $1$, $2$, $3$ and $4$. Therefore, we verify that lamps $1$ and $2$ received only one signal, while lamps $3$ e $4$ received two signals. Therefore, in the next configuration, lamps $1$ and $4$ will be turned on, while lamps $2$ e $3$ will be turned off.
Let $\Psi$ to be the set of all $2^n$ possible configurations, where $0 \le \ell \le n$ random lamps are turned on. We define a function $f: \Psi \rightarrow \Psi$ where, if $\xi$ is a configuration of lamps, then $f(\xi)$ is the configurations obtained after we perform the cool procedure described above.
Determine all values of $n$ for which $f$ is bijective.
This is a problem from Brazillian Olympiad. I tried considering a polynomial $\displaystyle F(x)=\sum_{i=1}^{n}a_ix^i$ where $a_i=1$ if $\displaystyle i^{\text{th}}$ lamp is on, and $0$ otherwise. But I don't see how to incorporate the fact here. If someone could help it would be better. Thanks.
The cool procedure is a linear transformation on the vector space $\mathbb F_2^n$, given by a matrix like this $$ \begin{pmatrix} 1&0&0&\cdots&1&1\\ 1&1&0&\cdots&1&1\\ 0&1&1&\cdots&1&1\\ 0&1&1&\cdots&1&1\\ 0&0&1&\cdots&1&1\\ 0&0&1&\cdots&1&1\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&0&1\\ 0&0&0&\cdots&1&1\\ 0&0&0&\cdots&1&0\\ \end{pmatrix}$$ where the $i$th column has $i+1$ entries $=1$, starting at the diagonal (with wrap-around and note the special case of thelast column). To see what's going on, here are the fullmatrices for small $n$: $$\begin{pmatrix}0\end{pmatrix} \quad\begin{pmatrix}1&1\\1&0\end{pmatrix}\quad\begin{pmatrix}1&1&1\\1&1&1\\0&1&0\end{pmatrix}\quad\begin{pmatrix}1&0&1&1\\1&1&1&1\\0&1&1&1\\0&1&1& 0\end{pmatrix}\quad\begin{pmatrix}1&0&1&1&1\\1&1&0&1&1\\0&1&1&1&1\\0&1&1&1&1\\0&0&1&1&0\end{pmatrix}$$ We notice that the cases $n=1,3,5$ are strikingly non-invertible (there are two identical rows for $n=3,5$. If you think about it a bit, you will find that for all odd $n>1$, the rows $n-1$ and $n-2$ are identical. You can evenb formulate this in the original setup, without matrices: If $n>1$ is odd, lamps $n-2$ and $n-1$ are always affected the same way by all lamps, except that $n-2$ infliuences $n-1$ but not vice versa. As a consequence, the cool procedure syncs these two lamps into the same state, thus defying bijectivity.
The seemingly more difficult part is to show that $f$ is bijective if $n=2m$ is even. Try to find the explicit inverses for $n=2,4,6$ and see if you can find a pattern. Or maybe note that there is always "a lot" of cancelling when adding row $2k-1$ to row $2k$ ...