light bulb problem?

Question

There is a very long hallway, longer than the eye can see. Along the midline of its ceiling, there are light bulbs, spaced a few feet apart, for as long as the eye can see. A string hangs from each light bulb; a pull of the string turns the light bulb on, and another pull turns the light bulb off.
A woman begins walking down the hall and pulls every single string, turning all of the light bulbs on. A second woman begins walking down the hall and pulls every second string (2,4,6,...), thereby turning off each of those light bulbs. And then a third woman begins to pull every third string (3,6,9,...), thereby turning some light bulbs on and others off. And then a fourth woman does the same (4,8,12,...), and then a fifth woman (5,10,15), and so on. Eventually, the women are only pulling strings that are farther away than can be seen.
Of those that can be seen, which light bulbs are on?

You don't have to give me the answer, but how would you go about answering this?

Wouldn't it be all the squares are on and everything else is off?

Answer 1

Hint: The number of times a switch is toggled is equal to the number of divisors its bulb has. 1 gets toggled once, 2 gets toggled twice, 3 gets toggled twice, 4 gets toggled 3 times, 10 gets toggled 4 times, 60 gets toggled 12 times, etc.

Answer 2

Okay, if you don't want the answer, I'll just give you a strong hint.
The string of the third light bulb is pulled by the 1st and 3rd women, because 1 and 3 are factors of 3. This bulb is off.
The string of the eighth light bulb is pulled by the 1st, 2nd, 4th, and 8th women, because 1,2,4, and 8 are the factors of 8. This bulb is off.
The string of the ninth light bulb is pulled by the 1st, 3rd, and 9th women, because 1,3, and 9 are the factors of 9. This bulb is ON.
Only light bulbs corresponding to numbers with an ODD number of factors will be ON.
What set of numbers (including 9 but not 3 or 8) has an ODD number of factors?

Answer 3

Each light bulb will indeed have its state changed by every woman whose number is a divisor of the light bulb's number.

The first bulb will be on.

The second bulb will be off.

Then off, on, off, off, etc.

Sounds like the Euler function (the number of divisors of n). If even, then the bulb will be off; if odd, then it will be on.

edit: oops--I though all the bulbs were on in the beginning. They weren't.