It's easy to see that light number 1 will be OFF. A little thought shows that light number 2 will be ON, and so will light number 3.
You can convince yourself that light number 4 is OFF because it got turned OFF by solder 1, ON by soldier 2, and OFF by soldier 4.
But it's really hard to see how you can answer the question in general.
We can say that light N is flipped by soldier M exactly if M is a divisor of N. We can therefore say that light N is back ON if N has an even number of divisors, but OFF if it has an odd number of divisors. But who knows what pattern that represents?
There is a mathematical function, known as TAU(N), whose value is the number of distinct divisors of N. So that number of times light N is flipped is TAU(N). So light N is ON if TAU(N) is even, and OFF if TAU(N) is odd.
There is a formula for TAU(N). If N can be written as the product of primes:
N = P1E1 * P2E2 * ... * PKEK
TAU(N) = ( E1 + 1 ) * ( E2 + 1 ) * ... ( EK + 1 )
Obviously, TAU(N) is even if any factor in the formula is even. Therefore, TAU(N) is even if any of E1, E2, ..., EK is odd.
So TAU(N) is odd exactly when every factor is odd, that is when every number E1 through EK is even. But that happens if and only if N is a perfect square.
Conclusion: after the last soldier has marched through the hall, light N is OFF if and only if N is a perfect square. Hence, lights 1, 4, 9, 16, 25, 36, ... are OFF, the rest are ON.
The previous solution is correct. But it is not satisfactory for most people, who haven't heard of the TAU function, which seems to fly into the problem unfairly. Here is a satisfactory solution which any reasonably thoughtful person can follow:
Light N is flipped by every soldier M for which M is a factor of N. Therefore, light N will be back on if the number of factors is even, but off if the number of factors is odd.
For any number N, let L be the square root of N. If N is a perfect square, then L is an integer, and a factor of N. But if N is not a perfect square, then L is not an integer, and is not a factor.
There are exactly as many factors of N less than L, as there are greater than L. That is because, if M is a factor of N, then so is N/M. If one of these numbers is less than L, the other has to be greater than L. (Otherwise, their product would be strictly less than L * L which is N.)
But that means that, not counting L (the square root of N) there must be an even number of factors of N. Therefore, if N is not a perfect square, there are an even number of factors, and so light N is on.
If N is a perfect square, there are an even number of factors that are not L, plus L, making an odd number, and so light N is off.
There are a few points in this argument that may take you a bit of thought before you are willing to agree with them, but I think the entire line of reasoning is transparent.
(I owe this second, superior explanation to Jim Fink of Gettysburg College.)
Back to The Light Flip Puzzle;