Thanks to Jon Campbell for telling me about this one, found at Steven Landsburg's blog, The Big Questions. The original puzzle is from the novel The Yukiad, by David Snaith.
Consider a glass contraption—a perpetual motion machine, really—consisting of a clear glass hula hoop on the ground containing several colored beads, which travel through the hoop, some clockwise, some counterclockwise, all at the same speed, bouncing off each other in perfectly elastic collisions whenever they collide. Whenever two beads collide, they instantly bounce off each other and proceed in the opposite of their original directions, still at the same speed. Take a snapshot of this system at, say, 12PM. Must there be some time in the future when another snapshot of the system will look identical? In other words, does the history of the system repeat itself?
(Hint: for simplicity, start with a few beads, then generalize)
Solution (thanks again to Jon):
Instead of being beads, you can pretend that the system consists of men with different colored hats walking around in a circle at a constant speed, where each man turns around each time he encounters another man. Then the question would be, would there ever be a time when all men are at the same place where they started? But that question is equivalent to the following: instead of turning around each time a man comes across another man, he will walk right by him, but trade hats with him. From the perspective of someone looking at these men from above, this "walk right by but trade hats" scenario (call it A) will look identical to the "turn around and don't trade" scenario (call it B), and the question is, will there ever be a time when all the hats are in the same place as at the beginning.
Using scenario A, it is obvious that after a particular man has walked the entire circle, all of the other men have done the same, and are in their starting positions. But, each may not be wearing the hat he started with, so the proof is not yet done. But even if they aren't wearing the same hats as they were in the beginning after 1 rounding of the circle, they will after some integer number of roundings n. This seems intuitive, and the best way I can explain it is with an example: suppose a red hat started with person X, and after 1 rounding, it is with person Y. It is clear that after some # or roundings, the red hat will end up back with person X -- i.e. it will not end up looping between some group of people that doesn't include X, since there would be no way for it to enter that loop in the first place if it existed. Suppose that for this red hat, the required minimum # of roundings before getting back to person X is 4. Suppose that for some other hat, the minimum # of roundings is 7, and so on, different #s for each hat (but actually there will be various hats that share the same minimum # of roundings). Then, at the very latest, the minimum # of roundings n for which ALL hats are back with their original person is 4*7*(...for all hats). So we know that there exists a # n of roundings after which all hats are back where they started.
