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

  • Context: MHB 
  • Thread starter Thread starter Olinguito
  • Start date Start date
  • Tags Tags
    Challenge Switches
Click For Summary
SUMMARY

The problem of determining whether all n switches can be on at the end of a sequential flicking process is resolved by the condition that n must satisfy n ≡ 0 or 1 (mod 4). The proof involves showing that each switch must be flicked an odd number of times, which is derived from the total number of flicks being n(n+1)/2. Induction is used to extend the solution from known cases of n=1 and n=4 to any n=k+4, confirming the validity of the condition for larger values of n.

PREREQUISITES
  • Understanding of modular arithmetic, specifically congruences.
  • Familiarity with mathematical induction techniques.
  • Basic knowledge of combinatorial reasoning.
  • Ability to interpret and construct mathematical proofs.
NEXT STEPS
  • Study modular arithmetic and its applications in combinatorial problems.
  • Learn about mathematical induction and its various forms.
  • Explore combinatorial game theory and related switch problems.
  • Investigate other parity-related problems in number theory.
USEFUL FOR

Mathematicians, educators, students studying combinatorics, and anyone interested in problem-solving strategies involving switches and parity conditions.

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)
 

Similar threads

Replies
21
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 49 ·
2
Replies
49
Views
4K
Replies
3
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
Replies
37
Views
6K
  • · Replies 31 ·
2
Replies
31
Views
5K
Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 125 ·
5
Replies
125
Views
20K