You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**chen.aavaz****Member**- Registered: 2016-05-05
- Posts: 37

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!

Offline

**bob bundy****Administrator**- Registered: 2010-06-20
- Posts: 8,274

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

Children are not defined by school ...........The Fonz

You cannot teach a man anything; you can only help him find it within himself..........Galileo Galilei

**Online**

**Alg Num Theory****Member**- Registered: 2017-11-24
- Posts: 85
- Website

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)*

Offline

**Alg Num Theory****Member**- Registered: 2017-11-24
- Posts: 85
- Website

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:

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

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

Offline

**chen.aavaz****Member**- Registered: 2016-05-05
- Posts: 37

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

Offline

**Alg Num Theory****Member**- Registered: 2017-11-24
- Posts: 85
- Website

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.

Offline

**chen.aavaz****Member**- Registered: 2016-05-05
- Posts: 37

Thank you very much! Great solution!

Offline

Pages: **1**