A Beetle Math Puzzle

Lessons from a puzzle about prime numbers

[ Wikipedia ]

Doron Zeilberger is a famous combinatorial mathematician based at Rutgers. He is noted for actively using computers in research. His computers even get co-authorship credit under the name “Shalosh B. Ekhad,” which is Hebrew for 3B1—a computer that came from building 3, corridor B, room 1 of AT&T Bell Labs.

Today I thought we would talk about a recent joint paper of Zeilberger on Covering Systems.

This paper has one co-author who is human, Anthony Zaleski, also of Rutgers. It starts with a puzzle about beetles on a circular track. The puzzle does not need a computer to solve—though a computerized visualization would make it more enjoyable. It makes several interesting points, points that are distinctly human, and I hope you might enjoy it.

The Puzzle

They ascribe the puzzle to Jean-Paul Delahaye, who modified Peter Winkler’s writeup of a folk puzzle that Winkler stated about ants.

One places nine beetles on a circular track, where the nine arc distances, measured in meters, between two consecutive beetles are the first nine prime numbers, . The order is arbitrary, and each number appears exactly once as a distance.

At the starting time, each beetle decides randomly whether she would go, traveling at a speed of 1 meter per minute, clockwise or counter-clockwise. When two beetles bump into each other, they immediately do a “U-turn”, i.e. reverse direction. We assume that the size of the beetles is negligible. At the end of minutes, after many collisions, one notices the distances between the new positions of the beetles.

Note that there are two levels of probability: the initial order of the vector of distances and the initial direction of each beetle. Yet after minutes there is a high probability of the distances being exactly the same: the first nine prime numbers. Is this a miracle? What is the probability?

The Lessons

The point is we have deliberately stated the puzzle to make it harder. The way we stated it is misleading and the following lessons are hints to help solve the puzzle.

• That the arc lengths are prime numbers is unimportant. The puzzle works whether or not the distances between the beetles are prime numbers.

• The probability is that the beetles are at the given positions. There is no chance that they will not arrive at the antipode points. None.

The Solution

The first observation is that the circular track’s length is

The second is that the probability is that the distances are the same after minutes. Imagine that each beetle carries a flag. Instead of reversing direction when they collide, let the beetles exchange their flags and continue moving as before. Now the flags always are moving in the same direction at the same speed. This means that after minutes the flags are at the antipode position. But the beetles are located at the same places as flags, and so the distances are the same as before. Note, the beetles are each located at the position of some unique flag, but which flag can change many times.

The only constraint is that the distance traveled in minutes divides the length of the circular track. The fact that the distances are primes is never used.

Open Problems

Zaleski and Zeilberger say:

We point out that very often primes are red herrings. This is definitely the case for covering system, and who knows, perhaps also for the Riemann Hypothesis.

I assume this is a bit tongue in cheek, but their point is valid. Do we miss solutions to problems when we use information that is not really important? How do we decide which information is key and which is redundant? This why I like this puzzle.