\documentclass[12pt]{article}

\usepackage{amsmath}        % preloaded by amsart above
\usepackage{amssymb}
\usepackage{hyperref}

%           *** CHANGE DIMENSIONS ***
\voffset=-0.3truein     % LaTeX has too much space at page top
% \advance\hoffset by .375 in
% \advance\voffset by .125 in
\addtolength{\textheight}{0.3truein}
\addtolength{\textheight}{\topmargin}
\addtolength{\topmargin}{-\topmargin}
%\showthe\textheight
\textwidth  6.0in       % LaTeX article default 360pt=4.98''
\oddsidemargin 0pt  % \oddsidemargin  .35in   % default is 21.0 pt
\evensidemargin 0pt % \evensidemargin .35in   % default is 59.0 pt
\mathsurround 1pt
%\parindent=20pt

%       *** SWITCH BACK TO PLAIN.TeX USAGE ***
\renewcommand\smallskip{\vskip\smallskipamount}
\renewcommand\medskip{\vskip\medskipamount}
\renewcommand\bigskip{\vskip\bigskipamount}
%==================== END PREAMBLE =========================================
\begin{document}
% Begin body of article here.
\pagestyle{empty}
\parindent=0pt
\vspace*{-1cm}
\Large

\begin{center}
{\bf Square of Differences: \\ Experimentation, Conjecture, and Proof}
\end{center}

\bigskip


{\sc The Game}

Mathematics involves experimentation and discovery, generalization and
conjecture, and proof. The game \emph{Square of Differences} supplies a
valuable exercise in searching for understanding.  The Proofs are
simply the final report on your conclusions.  The presentation below
originated with a \emph{New York Times} article

\url{http://wordplay.blogs.nytimes.com/2011/05/16/numberplay-danger-of-praise/"}

as presented by Lee Kennard.

\medskip

One starts with a square whose four corners are labeled with
nonnegative integers. One then computes the absolute value of the
difference between the two endpoints of each edge, and reports that
(nonnegative integer) on the corresponding midpoint. 

\begin{description}
\item[Step 1.]  Draw a new square
whose vertices are these four numbers, then repeat this process
indefinitely. For example, if we denote the four original numbers by
(1, 2, 3, 4), then the four differences are 1, 1, 1, and 3, which we
report as (1, 1, 1, 3). (Order matters, but cyclic shifts do not.) This
completes the first step; 
\item[Step 2.] gives (0, 0, 2, 2), 
\item[Step 3.] gives (0,2, 0, 2), 
\item[Step 4.] gives (2, 2, 2, 2)
\item[Step 5.] finally  gives (0, 0, 0,0). 
\end{description}

\smallskip
We say that \emph{a game ends} IF it reaches all zeros. 
\medskip

To the mathematician, a natural question to ask is whether the game
always ends. That is, given four nonnegative integers as our starting
point, is there some finite number of steps after which we are left
with all zeros? 
\bigskip

{\sc Short homework:}
\smallskip

Do experiments to see if some pattern emerges.
\smallskip
1. Play Square of Differences with (2, 3, 4, 5) and (10, 20, 30, 40) as
your starting values. Choose three more starting values and play SoD
for each. 
\smallskip

2. In each row of each game, circle the largest number. What do you
notice?
\smallskip

3. Adjust the rules to make a more primitive game that might be easier
to understand:  Copy your five games below, except replace all
instances of even numbers with zeros and all instances of odd numbers
with ones. What do you notice?  [Polya's book {\it How To Solve It} \ has
valuable suggestions for things to try when you are stuck on a
question.]
\smallskip

4. Do you think SoD always ends? ``I don't know.'' is an
appropriate answer.)  Explain.
\bigskip

\centerline{\sc [Pause to experiment and think]}
\newpage

\centerline{\sc Square of Differences: 6 Experiments}

\begin{align*}
\text{Step 0} \quad &(1,\,2,\,3,\,4) \qquad &(2,\,3,\,4,\,5) \qquad &(10,\, 20,\, 30,\, 40) \\
\text{Step 1} \quad &(1,\,1,\,1,\,3) \qquad &(1,\,1,\,1,\,3) \qquad &(10,\,10,\,10,\,30)  \\   
\text{Step 2} \quad &(0,\,0,\,2,\,2) \qquad &(0,\,0,\,2,\,2) \qquad &(0,\,0,\,20,\,20)   \\    
\text{Step 3} \quad &(0,\,2,\,0,\,2) \qquad &(0,\,2,\,0,\,2) \qquad &(0,\,20,\,0,\,20)   \\    
\text{Step 4} \quad &(2,\,2,\,2,\,2) \qquad &(2,\,2,\,2,\,2) \qquad &(20,\,20,\,20,\,20)  \\   
\text{Step 5} \quad &(0,\,0,\,0,\,0) \qquad &(0,\,0,\,0,\,0) \qquad &(0,\,0,\,0,\,0)	 \\    
\end{align*}


\begin{align*}  
\text{Step 0}   \qquad &(1,\,3,\,5,\,11) \qquad &(4,\,3,\,7,\,11) \qquad &(4,\,2,\,6,\,14) \\
\text{Step 1} 	\qquad &(2,\,4,\,6,\,8) \qquad &(1,\,4,\,4,\,7) \qquad &(2,\,4,\,8,\,10)\\
\text{Step 2} 	\qquad &(2,\,2,\,2,\,6) \qquad &(3,\,0,\,3,\,6) \qquad & (2,\,4,\,2,\,8)\\
\text{Step 3} 	\qquad &(0,\,0,\,4,\,4) \qquad &(3,\,3,\,3,\,3) \qquad &(2,\,2,\,6,\,6)\\
\text{Step 4} 	\qquad &(0,\,4,\,0,\,4) \qquad &(0,\,0,\,0,\,0) \qquad &(0,\,4,\,0,\,4)\\
\text{Step 5} 	\qquad &(4,\,4,\,4,\,4) \qquad &	  \qquad &(4,\,4,\,4,\,4)\\ 
\text{Step 6} 	\qquad &(0,\,0,\,0,\,0) \qquad &	 \qquad &(0,\,0,\,0,\,0)
\end{align*}


Based on this,  we make the following observations:
\medskip

{\bf Monotonicity:}
At every step the maximum value either decreases or remains the same;
the maximum value is never increased.
\medskip

{\bf Add a constant:} Comparing the first and second experiments, we see
that if we add the same constant to each of the values, then after one
step we are back where we started.  Thus, we can always assume the
minimum of the values is zero.  I did not see how to use this.
\medskip

{\bf Scaling:} Comparing the first and third examples, if you multiply the
starting values by any constant, then the remainder of the steps are
multiplied by the same constant.  This is clear. 
\smallskip

{\sc Moral:} If you multiply the starting values by any constant, then
if the game ends, it ends  in the \emph{same} number of steps.  We'll
say these two starting values are \emph{equivalent}.  For instance, the
sixth experiment is equivalent (in this sense) to starting with
$(2,\,1,\,3,\,7)$ whose maximum is half its original value, 14.
\medskip

{\bf Even:}  It looks like after at most $4$ steps, all the elements in the list
are even .  We prove this now.  
\smallskip

Using the cyclic symmetry, there are only 6 possible starting
configurations.  After some experimentation (an important step when
presenting your results to others), it is simplest to list them in the
following order:

\begin{enumerate}
\item  (even, even, even, even): already all even.
\item  (odd, odd, odd, odd):   1 step to reduce to all even.
\item  (odd, even, odd, even): 1 step reduces to the previous case.
\item (odd, even, even, odd): 1 step reduces to the previous case.
\item (even, odd, odd, odd) and \ 6. (odd, even, even, even): \\
 1 step reduces to the previous case.
 \end{enumerate}
 \medskip 

Combining observations 1 and  3, we see that if the initial values are
at most 1, then after at most 4 steps we get all zeroes and the game
ends.
\bigskip

{\bf Always Ends:} We now prove the game always ends in a finite number
of steps.  
\medskip

However one begins, after at most $4$ steps the values are always even,
say $(2a,\, 2b,\, 2c,\, 2d)$ with maximum value at most the initial
maximum.  But this is equivalent to the game $(a,\,b,\,c,\,d)$  whose
maximum is at most \emph{half} that of the original game.  Repeating
this a finite number of times we eventually get a game with all even
values $(0,\,0\, 0\,0)$, as desired.
\vskip 20pt

We showed that the game must always end.  How many steps before it
does?  Here is an example showing that for all $n$, there is a game
that takes more that $n$ steps. Define the sequence inductively by
$s_1=0$, $s_2=0$, $s_3=1$, $s_{n}= s_{n-1}+s_{n-2}+s_{n-3}$, $n=4,\,5\,
6\ldots$.  Then a game starting with
$s_n,\,s_{n+1},\,s_{n+2},\,s_{n+3}$ after $3$ steps becomes
$(s_{n-2},\,s_{n-1},\,s_{n}, s_{n+1}$.  Thus a game starting with
$(s_{2n},\, s_{2n+1},\, s_{2n+2},\, s+{2n+3})$ will last $3n + 3$
steps.
\smallskip

However, our proof shows that a game with maximum starting value $N$
ends in at most $4 +4\log_2(N)$ steps (this estimate can be improved)
-- but it may be much shorter, as illustrated by the initial values
$(N.\,N,\,N,\,N)$ which takes only one step.
\medskip

{\bf Variants.}  What if instead of a square one begins with a
triangle or pentagon?


\end{document}
