Boolean Function Analogs of Covering Systems

Anthony ZALESKI and Doron ZEILBERGER

Prolog: Primes Numbers are (often) Red Herrings

In the September 2017 of Jean-Paul Delahay’s wonderful Logique & Calcul column ([D]), the following variation on one of the numerous Ant Alice puzzles in Peter Winkler’s wonderful book ([W]).

On places nine beetles on a circle, the distances between two consecutive beetles, measured in meters, along the circle are the first nine primes 2, 3, 5, 7, 11, 13, 17, 19, 23. The order is arbitrary, but each of the distances occurs exactly once.

At the starting time, each beetle decides, randomly, whether it is going to walk, at a speed of 1 meter per minute, clockwise or counterclockwise. When two beetels collide, they immediately turn-around. We assume that the size of the beetles are negligible. After 50 minutes, after many collisions and such “U-turns” of the nine beetles, one notes their position and the distances that separate them. These nine distances are still the same nine primes! How can you explain this arithmetical miracle?”

Please think about it for a few minutes and see whether you can explain this miracle (if you have not seen it before).

The beautiful solution is as follows. Let each beetle carry a flag, and whenever they collide, they exchange their flags, like in a relay race. It folows that each of the flags moves in its initial direction at a speed of 1 meter per minute. Since the lenght of the ”track” is

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 = 100 .

After 50 minutes, each flag moved exactly to the opposite point on the circle, hence the relative distances between consecutice flags (and hence consecutive beetles) remain the same. QED.

Delahaye made two changes to Winkler’s original puzzle. First he changed ants to beetles, but very sneakily made the initial distances primes! The solution shows that if the initial distances are a_{1}, …, a_{k}, then the distances are preserved after (a_{1} + … + a_{k})/2 minutes (and of course, any multiple of it). So choosing primes was a huge red herring, that made this delightful brain-teaser so much harder.

We claim that primes are (very possibly) also red herrings in much more “serious” problems, even, who knows?, the Riemann Hypothesis, and the Goldbach conjecture.

References

[D] Jean-Paul Delayahe, Cinq énigmes pour la rentrée, Logique & Calcul, Pour La Science, No. 479, Septembre 2017, 80-85.

[W] Peter Winkler,“Mathematical Mind-Benders”, A.K. Peters, 2007.

Anthony Zaleski, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: az202 at math dot rutgers dot edu .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .