bb wrote:
In a long hallway is a series of ceiling lights, each with an individual pull switch (pull a string and the light turns on; pull again and it turns off). There are 20,000 lights in the hallway and they are all turned off. A person comes in and pulls the string on every light thus turning them all on. Then a second person comes in and pulls the string on every second light thus turning every second light off. Then a third person comes in an pulls the string on every third light (3, 6, 9, 12, etc) and thus turning some lights on and others off. Then a fourth person comes in and pulls the string on every fourth light and so on and on until person number 20,000 comes in and pulls just one string on the light 20,000.
Can figure out which lights will be on and which will be off?
P.S. I heard it on the last week's cartalk.
Initially all light bulbs are off. Now, consider one particular light bulb, for example, light bulb #6.
First person will turn it on. Then it will be off when the second person will turn off every second light bulb as 6 is a multiple of 2, then it will be turned on again when 3rd person do the same as 6 is a multiple of 3 and finally it'll be off when 6th person get to it as 6 is a multiple of 6.
1(on)-2(off)-3(on)-6(off) --> so # of variations of a light bulb (on/off) equals to the number of factors of a light bulb and if the number of factors of a light bulb is even (as for 6) then it will end up turned off and if the number of factors of a light bulb is odd it'll end up turned on. Only perfect squares (these are 1, 4, 9, 16, 25, etc) have odd number of factors so only perfect squares less than 20,000 will end up turned on.
Last perfect square which is less than 20,000 is 141^2=19,881. So, there will be total of 141 light bulbs on: 1, 2^2=4, 3^2=9, 4^2=16, 5^2=25, ..., 141^2=19,881.
_________________