Some $n>2$ lamps are cyclically connected: lamp $1$ with lamp $2$, ..., lamp $k$ with lamp $k+1$,..., lamp $n-1$ with lamp $n$, lamp $n$ with lamp $1$. At the beginning all lamps are off. When one pushes the switch of a lamp, that lamp and the two ones connected to it change status (from off to on, or vice versa). Determine the number of configurations of lamps reachable from the initial one, through some set of switches being pushed.
Problem
Source: Romania TST 1 2009, Problem 3
Tags: induction, linear algebra, matrix, combinatorics
07.05.2012 02:26
In the case $n\equiv 1, 2\:\:(\textrm{mod }3)$, all configurations are possible, hence the answer is $2^n$. In fact, if $n\equiv 1$, consider the following sequence of moves (the numbers mean "switch the lamp number $x$"): $1,2,4,5,\ldots,(3k+1),(3k+2),\ldots,(n-3),(n-2),n$ leaves the first lamp on and the rest off. By iterating this process, we can light any lamp we want without changing the state of the others. In the same way, if $n\equiv 2$, consider the following: $3,4,6,7,\ldots,3k,(3k+1),\ldots,(n-2),(n-1),1$ leaves the first lamp on the rest off, and we conclude as above. If $n=3k$, for some $k\ge 1$, consider the following strategy: define $a,b,c\in\mathbb{N}$ as follows (here we denote the lamp by its number): \[a=\textrm{number of turned on lamps among } 1,4,\ldots,3k-2.\] \[b=\textrm{number of turned on lamps among } 2,5,\ldots, 3k-1.\] \[c=\textrm{number of turned on lamps among } 3,6,\ldots, 3k.\] Each move increases or decreases $a,b,c$ by one. It follows that the parity of $a,b,c$ changes after each move, and since the start condition is $a=b=c=0$, they will have the same parity in every possible configuration. This is condition is also sufficient for a configuration to be a possible configuration. The basic idea is that you can "move" a lit lamp from a position $k$ to position $k+3$ without changing the state of the others, e.g. with the sequence of moves $k+1,k+2$. This together with induction on $k$ (I don't think it's particularly difficult to prove it) we can show the desired result. The answer is then: $2^{n-2}$.
07.05.2012 03:38
Another way of looking at it: let $T_n$ be the $n$-cycle. If the rank of $A(T_n) + I$ treated as a matrix over $\mathbb{F}_2$ is $r$, then there are $2^r$ configurations. So it all boils down to finding solutions of the equation $A(T_n)x=x$ over $\mathbb{F}_2$. If there are $b$ solutions (i.e. $b$ sets of switches, including the empty set, that when pushed do not change the configuration), then there are $2^n/b$ configurations. Here is a reference: http://math.mit.edu/~rstan/algcomb.pdf There are some nice results in section 12.5.
12.02.2016 09:59
Assign number $1$ to each off lamp and $-1$ to each on lamp. Consider a set of switches. Let $a_i$ be $1$ if we switched lamp $i$ an even number of times and let $a_i$ be $-1$ otherwise. In the end, lamp $i$ will have assigned the number $a_{i-1}a_ia_{i+1}$. Let's say that in the end we wish that our configuration is $\varepsilon_1$ , $\varepsilon_2$ ,..., $\varepsilon_n$ (where $\varepsilon_i \in \{-1,1\}$). This is equivalent to solving $a_1a_2a_3=\varepsilon_1, a_2a_3a_4=\varepsilon_2,...,a_na_1a_2=\varepsilon_n$. In this case, $$a_4=\dfrac{\varepsilon_2}{\varepsilon_1}a_1,\ a_5=\dfrac{\varepsilon_3}{\varepsilon_2}a_2,\ a_6= \dfrac{\varepsilon_4}{\varepsilon_3}a_3,\ a_7=\dfrac{\varepsilon_5}{\varepsilon_4}a_4=\dfrac{\varepsilon_5}{\varepsilon_4}\cdot \dfrac{\varepsilon_2}{\varepsilon_1}a_1,...\ \ (*)$$ In general, $a_k=\dfrac{\varepsilon_{k-2}}{\varepsilon_{k-3}}a_{k-3}=\dfrac{\varepsilon_{k-2}}{\varepsilon_{k-3}}\dfrac{\varepsilon_{k-5}}{\varepsilon_{k-6}}a_{k-6}=...=t_ka_r$ where $r$ is the residue of $n$ modulo $3$ and $t_k\in \{1,-1\}$ . This means that once we fix $a_1,a_2,a_3$, the other $a_i$s are uniquely determined. This solves us the first $n-2$ equations, so we are left with choosing $a_1,a_2,a_3$ such that $a_1a_2a_3=\varepsilon_{1},\ a_{n-1}a_na_1=\varepsilon_{n-1}$ and $a_{n}a_1a_2=\varepsilon_{n}$. If $n\equiv 1(\mathrm{mod}\ 3)$, $$a_{n-1}a_na_1=\varepsilon_{n-1}\Leftrightarrow t_{n-1}t_n a_3a_1^2=\varepsilon_{n-1}\Leftrightarrow a_3=\varepsilon_{n-1}t_nt_{n-1}$$$$a_na_1a_2=\varepsilon_{n}\Leftrightarrow t_na_1^2a_2=\varepsilon_{n} \Leftrightarrow a_2=\varepsilon_{n}t_n$$Choosing $a_1=\varepsilon_1a_2a_3$, we have found a solution for $(*)$. In an almost identical fashion one can find a solution for the system if $n\equiv 2(\mathrm{mod}\ 3)$. Thus, if $n$ is not divisible by $3$, any configuration can be reached, so the answer is $2^n$. If $3$ divides $n$, then $a_n=t_na_3$ and $a_{n-1}=t_{n-1}a_2$, so $\varepsilon_{n-1}=a_{n-1}a_na_1=t_{n-1}t_na_1a_2a_3=t_{n-1}t_n\varepsilon_{1}$ and $\varepsilon{n}=a_na_1a_2=t_na_1a_2a_3=t_n\varepsilon_{1}$, which implies that $\varepsilon_{n-1}$ and $\varepsilon_{n}$ depend on the other $n-2$. Thus, we can choose freely $\varepsilon_1,...\varepsilon_{n-2}$ and $\varepsilon_{n-1}, \varepsilon_{n}$ will be uniquely determined, hence the answer is $2^{n-2}$.