%boole.tex: 
%Boolean Function Analogs of Covering Systems
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf 
Boolean Function Analogs of Covering Systems
}
\medskip
\centerline
{\it Anthony ZALESKI and Doron ZEILBERGER}


{\bf 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 {\it Ant Alice} puzzles in Peter Winkler's wonderful book ([W]).

{\it 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 \quad .
$$
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 {\bf same}. QED.

Delahaye made two changes to Winkler's original puzzle. First he changed {\it ants} to {\it beetles}, but 
{\bf very sneakily} made the initial distances primes! The solution 
shows that if the initial distances are $a_1, \dots, a_k$, then the distances are preserved after
$(a_1+ \dots + a_k)/2$ minutes (and of course, any multiple of it). So choosing {\bf primes}
was a huge {\it 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.


{\bf References}

[D] Jean-Paul Delayahe, {\it Cinq \'enigmes pour la rentr\'ee}, Logique \& Calcul, Pour La Science, {\bf No. 479}, Septembre 2017, 80-85.


[W] Peter Winkler,``{\it Mathematical Mind-Benders}'',  A.K. Peters, 2007.

\bigskip
\hrule
\bigskip
Anthony Zaleski, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt az202 at math dot rutgers dot edu}   \quad .
\bigskip
Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt DoronZeil at gmail dot com}   \quad .


\end






