For n ≡ 2 (mod 4), n is even and the total number of switchings is odd, again impossible as the sum of an even number of odd numbers must be even.
]]>@Alg Num Theory: Can you explain a bit further why we can't succeed for n ≡ 3 or n ≡ 2?
I have done some examples but don't understand the generic conclusion.
Thank you.
]]>For n = 4, the process is simple:
0000
1000
1110
0000
1111
using bob bundy’s notation. Let us give this an easy-to-remember name and call it the “four-switch process”.
Now label the switches 1, 2, …, n. Suppose n is a multiple of 4. The first four people perform the “four-switch process” to the first four switches. The next four people then toggle the first four switches and perform the “four-switch process” to switches 5 to 8. Then switches 5–8 will all be on; since switches 1–4 are already on, toggling them an even number of times will leave them on. Hence after the first 8 people, switches 1–8 will be on. Then we can continue the process, persons 9–12 toggling switches 1–8 and doing the “four-switch process” to swtiches 9–12, and so on. Hence when n ≡ 0 (mod 4) it is always possible to leave all the lights on.
Bob was scratching his head over the case n = 5; let me put him out of his misery.
00000
10000
01000
11110
00000
11111
The first person turns the first switch on, persons 2–5 toggle the first switch and perform the four-switch process on switches 2–5. So if n ≡ 1 (mod 4) proceed as follows: persons 6–9 toggle the first 5 switches and do the four-switch process on switches 6–9, persons 10–13 toggle the first 9 switches and do the four-switch process on switches 10–13, and so on – leaving all lights on at the end.
]]>Total number of switchings by the n people: 1+2+…+n = n*(n+1)/2 = always even
For all lights to be on after the whole process, each of them must have been switched by an odd number of times.
So this is a sum of odd numbers, and if n:odd then the total is odd, which is contradictory with the above.
The total number of switchings is even if either n or n+1 is divisible by 4, otherwise (as in bob bundy’s example) it is odd.
However you have managed to show that if n ≡ 3 (mod 4) then it is never possible to have all lights on at the end. You still need to determine whether it’s still the case for other values of n.
PS: You can also argue in similar fashion that if n ≡ 2 (mod 4) then again it’s not possible. This time the total number of switchings is odd and n is even.
]]>If n = 5, then n(n+1)/2 = 5x6/2 = 15
I'll use 0 to indicate a light OFF and 1 for ON.
Here's one possible sequence:
00000
10000
11100
11011
10100
01011
Is it always possible for all the lamps to be turned on at the end of the process?
At the penultimate step, the state has to be
00000
so can you find a way to be sure you could reach this state after n-1 people have had their go?
I'll start thinking about this. I may be 'gone' some time.
Bob
]]>A basic attempt:
Total number of switchings by the n people: 1+2+…+n = n*(n+1)/2 = always even
For all lights to be on after the whole process, each of them must have been switched by an odd number of times.
So this is a sum of odd numbers, and if n:odd then the total is odd, which is contradictory with the above.
Anyone can help me for a more "mathematical" solution? Also, how do we use the restriction that "Each person can only switch each switch once at maximum"?
Many thanks in anticipation!
]]>