Answer to Puzzle #6: Switching 100 Light Bulbs

6. There are 100 light bulbs lined up in a row in a long room. Each bulb has its own switch and is currently switched off. The room has an entry door and an exit door. There are 100 people lined up outside the entry door. Each bulb is numbered consecutively from 1 to 100. So is each person.

Person No. 1 enters the room, switches on every bulb, and exits. Person No. 2 enters and flips the switch on every second bulb (turning off bulbs 2, 4, 6...). Person No. 3 enters and flips the switch on every third bulb (changing the state on bulbs 3, 6, 9...). This continues until all 100 people have passed through the room.

What is the final state of bulb No. 64? And how many of the light bulbs are illuminated after the 100th person has passed through the room?

Right first the answers: Light Bulb 64 is on. The total number of bulbs which are on including #64 is 10.

Now the working

Before reading the answer can I interest you in a clue?

We'll use a more eloquent way of working this out, but first lets just brute force it. To that end I've written a simple simulator, and for even more detail below that there is a spread sheet, if you want the extra detail then un-hide it:-

Person 1 is ready to work.   Delay between people =ms
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100 

Whichever way you went, the important thing is what you notice about the bulbs that stayed on? If you haven't seen a pattern then write them down...


some light globe pictures

A More eloquent approach.

First think who will operate each bulb, obviously person #2 will do all the even numbers, and say person #10 will operate all the bulbs that end in a zero. So who would operate for example bulb 48:

Persons numbered: 1 & 48, 2 & 24, 3 & 16, 4 & 12, 6 & 8 ........

That is all the factors (numbers by which 48 is divisible) will be in pairs. This means that for every person who switches a bulb on there will be someone to switch it off. This willl result in the bulb being back at it's original state.

So why aren't all the bulbs off?

Think of bulb 36:-

The factors are: 1, 2, 3, 6, 9, 12, 18, 36
OR 1 & 36, 2 & 18, 3 & 12 and 6

Previously the pairs cancelled, if 2 flicks the switch one way then 18 would flick it back, but in this case 6 is not paired, it's by itself, there is no body to cancel out his action. This is true of all the square numbers.

There are 10 square numbers between 1 and 100 (1, 4, 9, 16, 25, 36, 49, 64, 81 & 100) hence 10 bulbs remain on.

100 Doors

This problem is often written as 100 doors in a row, with each person switching their corresponding door. It's exactly the same.





© Nigel Coldwell 2004 -  – The questions on this site may be reproduced without further permission, I do not claim copyright over them. The answers are mine and may not be reproduced without my expressed prior consent. Please enquire using the link at the top of the page.
 


PayPal
I always think it's arrogant to add a donate button, but it has been requested. If I help you get a job though, you could buy me a pint! - nigel












This Website Uses Cookies

Mostly, but not entirely to remember if you have dismissed this very box. Also to increase the functionality of the site. The cookies I apply do not uniquely identify you, by continuing to use this site you agree to let me place a cookie. I also have advert and analytics providers, for more information click here here.x