There is a row of one million light bulbs, labeled from 1 to 1,000,000. To start with, all the bulbs are off.

What is going to be done with the light bulbs involves "flips". A "flip" is simply the change of state of the light bulb - if the light bulb is off, a flip will turn it on. If a light bulb is on, a flip will turn it off.

Starting with bulb #1, every bulb is flipped (obviously, this results in all the bulbs being on). Next, starting with bulb #2, every second bulb is flipped (resulting in only the odd numbered bulbs remaining on). This continues with bulb #3, and every third bulb being flipped, then starting at #4 and every fourth bulb being flipped, and so on, until we reach bulb #1,000,000 with "every millionth bulb" (just the one, of course) being flipped.

At the end of this exercise, which bulbs are on, and which bulbs are off?

All perfect squares will be on, and the rest off. I believe this puzzle relies on how many products a number has. Most numbers have an even number of products where as perfect squares have an odd number of products.

I sense that this is correct and would love to see a proof that squares have an odd number of different divisors and that all other integers have an even number of different divisors. Sounds like a nice problem indeed.

/Tomas

Tomas, thefifth was indeed correct. As for the proof, it is quite simple.

Any number will always have at least two factors, 1 and itself. Any other factors will always bring in another pair of numbers, which keeps the number of factors even. The only case where this isn't technically true is the case of a square number. In this case, you're bringing in another pair of factors, but they're both exactly the same number, so you're really only adding 1 factor. Thus, square numbers are the only case where a number would have an odd number of factors.

For example, check out the factors of the first 5 square numbers:

1=1
4=1,2,4
9=1,3,9
16=1,2,4,8,16
25=1,5,25

Maybe this is not rigorous enough but I will give it a go...

imagine all the integers from 1 to the number - N, on a line.
now divide this line into two segments at the square root point (this might be directly ON an integer or between two)
now, starting with "1" - any factor of N will have a "brother" factor on the other segment, if not their product will either be less than N or bigger than N (the product of any 2 numbers on the left segment is less than N since the two largest integers there can "reach" maximum to N - same argument applies for the right hand segment bur with opposite results)
therefore we can start to cross off pairs of factors - one from each segment. the only exception is when we got a perfect square, then the division point is exactly "on" a factor.

hope I could make it clear enough,

Nir

Scott, "Any other factors will always bring in another pair of numbers, which keeps the number of factors even." was too compressed for me.

Any chance you can rewrite it? You are using the word "factors" in an uncommon way. I assume that at at least one point here you mean "divisor", since the number itself is a factor only if the number is prime. Do you mean "divisor" when you write "number"? Let's say the number is 15, so it has 1 and 15 as divisors. What's the reasoning that the divisor 3 has to bring another divisor with it (and only one)? I know that it does, of course, but I can't quite follow the resoning.

Ah, just read Nir's take on it. Brilliant idea to look around the point sqrt(N). Forget what I asked above.

/Tomas

What I do know is this, the ones that alternate an Odd number of times will be on, and the ones that alternate an even amount of times will be off.