Challenge problem #4 Is it possible for all n switches to be on at the end

[Olinguito]

$n$ lights are arranged in a circle, each operated by exactly one of $n$ switches (with each switch operating exactly one light). Flicking a switch turns the light it is operating on if it is off, and off if it is on. Initially all the lights are off. The first person comes and flicks one of the swtiches, then the second person comes and flicks two of the switches, and so on, until the $n$th person comes and flicks all $n$ switches. Is it possible for all $n$ switches to be on at the end?

 

[castor28]

[sp]
It is possible if and only if $n\equiv0\text{ or }1\pmod4$.

To prove that the condition is necessary, we note that each switch must be flicked an odd number of times. As the total number of flicks is $\dfrac{n(n+1)}{2}$, we must have:
$$\begin{align*}
n &\equiv\frac{n(n+1)}{2}\quad&\pmod2\\
2n &\equiv n(n+1)&\pmod4\\
n(n-1)&\equiv0 &\pmod4
\end{align*}$$
and, as $n$ and $n-1$ cannot both be even, the conclusion follows.

To prove that the condition is sufficient, we proceed by induction with a step of 4. The base cases are $n=1$ and $n=4$. The first case is obvious, and, for the second case, we have the solution:
$$
\begin{array}{c|c|c|c|c|}
&1&2&3&4\\
\hline
1&1&0&0&0\\
2&0&1&1&0\\
3&1&1&1&0\\
4&1&1&1&1\\
\hline
\text{total}&3&3&3&1
\end{array}
$$
where '1' stands for a flick, each column after the first corresponds to a switch and each row corresponds to a round.

We now assume that there is a solution for $n=k$ and show that we can extend it to a solution for $n=k+4$. We add 4 columns and 4 rows to the table.

The first $k$ rows are extended with 0. In the rows $k+1$ to $k+4$, we fill the first $k$ columns with 1, and the last 4 columns with a copy of the solution for $n=4$. This is indeed a solution, because:

• Row $i$ contains $i$ 1's.
• The parity of the first $k$ column totals has not changed; it is odd by the induction hypothesis.
• The parity of the last 4 column totals is odd as it is in the case $n=4$.

The solutions for $n=5$ and $n=8$ are shown below:
$$
\begin{array}[t]{c|c|c|c|c|c|}
&1&2&3&4&5\\
\hline
1&1&0&0&0&0\\
2&1&1&0&0&0\\
3&1&0&1&1&0\\
4&1&1&1&1&0\\
5&1&1&1&1&1\\
\hline
\text{total}&5&3&3&3&1
\end{array}
\qquad\begin{array}[t]{c|c|c|c|c|c|c|c|c|}
&1&2&3&4&5&6&7&8\\
\hline
1&1&0&0&0&0&0&0&0\\
2&0&1&1&0&0&0&0&0\\
3&1&1&1&0&0&0&0&0\\
4&1&1&1&1&0&0&0&0\\
5&1&1&1&1&1&0&0&0\\
6&1&1&1&1&0&1&1&0\\
7&1&1&1&1&1&1&1&0\\
8&1&1&1&1&1&1&1&1\\
\hline
\text{total}&7&7&7&5&3&3&3&1
\end{array}
$$
[/sp]

 

[Olinguito]

Splendid! That is precisely the solution I have in mind. (Happy)