Light bulbs and switches

chen.aavaz · 2018-01-11 20:13:41

There are n light bulbs corresponding 1-to-1 with n switches in a room. Initially all the lights are off.
n people enter the room one by one; the 1st of them switching 1 switch at random, the 2nd 2 switches and so on, until the nth person who switches n switches. Each person can only switch each switch once at maximum. Is it always possible for all the lamps to be turned on at the end of the process? Justify.

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!

Bob · 2018-01-11 20:53:00

hi chen.aavaz

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

Alg Num Theory · 2018-01-12 16:11:36

chen.aavaz wrote:

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.

Last edited by Alg Num Theory (2018-01-12 16:24:50)

Alg Num Theory · 2018-01-12 18:03:18

So if n ≡ 2 or 3 (mod 4) it is never possible to have all lights on at the end. I will show that you can have them all on if n ≡ 0 or 1 (mod 4).

For n = 4, the process is simple:

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.

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.

Last edited by Alg Num Theory (2018-01-13 23:49:34)

chen.aavaz · 2018-01-13 01:35:52

@Alg Num Theory and Bob Bundy: Thanks a lot for your solutions.

@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.

Alg Num Theory · 2018-01-13 03:36:07

For n ≡ 3 (mod 4), n is odd and the total number of switchings is even, which is impossible if each switch is to be flicked an odd number of times: the sum of an odd number of odd numbers must be odd. This is what you proved yourself in post #1.

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.

chen.aavaz · 2018-01-13 12:58:59

Thank you very much! Great solution!

Math Is Fun Forum

#1 2018-01-11 20:13:41

Light bulbs and switches

#2 2018-01-11 20:53:00

Re: Light bulbs and switches

#3 2018-01-12 16:11:36

Re: Light bulbs and switches

#4 2018-01-12 18:03:18

Re: Light bulbs and switches

#5 2018-01-13 01:35:52

Re: Light bulbs and switches

#6 2018-01-13 03:36:07

Re: Light bulbs and switches

#7 2018-01-13 12:58:59

Re: Light bulbs and switches

Board footer