Here's another riddle. I heard it on Car Talk a couple of weeks ago, and I include it because the answer is elegant in the way that math problems sometimes are.
There is a long hallway, and down it, light bulbs hang from the ceiling. Many many light bulbs, the exact number doesn't matter, say 20,000 just for instance. These lights are all off. Then someone goes down the hall and pulls the chain on each bulb. The next person walks down and pulls every other chain starting with the second one. The next person pulls every third chain (the first chain he pulls is the third one). Then every fourth, fifth, etc.
The last person pulls every twenty thousandth bulb's chain. After all this happens, how can one predict which light bulbs will be left on?