A very long straight hallway is lit by lightbulbs that hang from the ceiling, are evenly spaced, and are turned on and off using flip switches on the wall beside each one. As the scene begins, some of the (say, thousand) bulbs are on, and some are off.

Now someone--call him Mr. ONE--runs down the hall flipping all the switches. Next, following Mr. ONE, comes Mr. TWO who proceeds to flip every second switch (2,4,6, etc.). After this comes Mr. THREE, who flips every third switch (3,6,9, etc.), then Mr. FOUR, Mr. FIVE, and so on, until finally Mr. THOUSAND runs past the first 999 bulbs and flips the thousanth switch.

Given that you know the initial pattern of lights that are on, which lights are still on after Mr. THOUSAND makes his run? (solution)