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

  • Thread starter Thread starter Olinguito
  • Start date Start date
  • Tags Tags
    Challenge Switches
AI Thread Summary
The problem involves determining whether all n switches can be turned on after a series of flicks by n people. It is established that all switches can be on if and only if n is congruent to 0 or 1 modulo 4. The proof includes demonstrating that each switch must be flicked an odd number of times, leading to necessary conditions based on the total number of flicks. An inductive approach is used to show that if a solution exists for n=k, it can be extended to n=k+4, confirming the sufficiency of the condition. The discussion concludes with examples for n=5 and n=8, illustrating the solution structure.
Olinguito
Messages
239
Reaction score
0
$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?
 
Mathematics news on Phys.org
[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]
 
Splendid! That is precisely the solution I have in mind. (Happy)
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top