% WOP hard eqn
% circle of numbers problem (flip 5)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[twoside,12pt]{article}
\usepackage{light}

\showsolutions

\begin{document}

\problemset{3}{February 15, 2005}{Tuesday, February 22 at 9 PM in Room 32-044}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% swiped from Discrete Applied Mathematics

% not two balls?

\begin{problem}
An urn contains 75 white balls and 150 black balls.  While there are
at least 2 balls remaining in the urn, you repeat the following
operation.  You remove 2 balls selected arbitrarily and then:
%
\begin{itemize}
\item If at least one of the two balls is black, then you discard one
black ball and put the other ball back in the urn.
\item If both of the balls are white, then you discard them both and put a
new black ball into the urn.
\end{itemize}
%
Prove that the urn never reaches the state where it is empty except
for one black ball.
\end{problem}

\solution{We use induction.  Let $P(n)$ be the proposition that the
urn always contains an odd number of white balls.

\noindent \textit{Base case.}  Initially, the urn contains 75 white
balls, which is an odd number, so $P(0)$ is true.

\noindent \textit{Inductive step.}  Suppose that the urn contains an
odd number of white balls after $n$ steps.  If there are fewer than 2
balls remaining, then the process ends.  Otherwise, there are then two
cases:
%
\begin{enumerate}
\item You draw at least one black ball.  Then the number of black
balls decreases by one and the number of white balls is unchanged.
Therefore, the number of white balls remains odd.
\item You draw two white balls.  Then the number of black balls
increases by one, and the number of white balls decreases by two.
Again, the number of white balls remains odd.
\end{enumerate}
%
Thus, the urn still contains an odd number of white balls after $n+1$
steps.  By induction, the urn always contains an odd number of white
balls.  Therefore, the urn can never hold just one black ball and zero
white balls, since zero is even.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
A puzzle toy contains the numbers $1, \ldots, 35$ written on small
circular disks.  The disks are arranged on an oval track with
\textit{no gaps} so that the whole sequence of disks can slide
clockwise or counterclockwise around the track.
%
\begin{center}
\rotatebox{-90}{\includegraphics{track-puzzle}}
\end{center}
%
In addition, the track runs through a circular dial that is four disks
wide.  This dial can be rotated 180 degrees, reversing the order of
the four disks on that portion of the track.  For example, if the dial
were turned in the configuration above, then the the order of 34, 35,
1, 2 would become 2, 1, 35, 34.

Suppose that the puzzle is initially in the state shown above with
numbers increasing counterclockwise around the track.  Prove that no
sequence of operations has the effect of swapping disks only 1 and 2
while leaving all the other disks in the same order.
\end{problem}

\solution{Associate each configuration of the puzzle with a
permutation of the numbers $1, \ldots, 35$ by taking the numbers in
counterclockwise order starting in the middle of the dial.  Thus, the
example configuration corresponds to the permutation:
%
\[
1\ 2\ 3\ \ldots\ 35
\]

Now we use induction on the number of operations.  Let $P(n)$ be the
proposition that after $n$ operations, there are an even number of
inversions.

\noindent \textit{Base case.}  Initially, there are zero inversions.
Since zero is even, $P(0)$ is true.

\noindent \textit{Inductive step.}  Suppose that after $n$ steps there
are an even number of inversions.  There are now three cases to
consider:
%
\begin{itemize}
\item Suppose the dial is turned 180 degrees.  This transforms the
permutation
%
\[
s_1 s_2 s_3 s_4 \ldots s_{32} s_{33} s_{34} s_{35}
\]
%
into the permutation:
%
\[
s_{35} s_{34} s_3 s_4 \ldots s_{32} s_{33} s_2 s_1
\]
%
This amounts to swapping $s_1$ with $s_{35}$ and $s_2$ with $s_{34}$.
Each swap changes the parity of the number of inversions, so after two
swaps there are still an even number of inversions.

\item Suppose that the numbers are rotated one position clockwise
around the track.  This transforms the permutation
%
\[
s_1 s_2 s_3 s_4 \ldots s_{32} s_{33} s_{34} s_{35}
\]
%
into the permutation:
%
\[
s_2 s_3 s_4 \ldots s_{32} s_{33} s_{34} s_{35} s_1 
\]
%
This reverses the order of exactly 34 pairs of disks, $s_1$ and every
other disk.  This changes the parity of the number of inversions 34
times, which leaves an even number of inversions.

\item Similarly, rotating one position counterclockwise reverses the
order of 34 pairs, again leaving an even number of inversions.

\end{itemize}
%
By induction, the number of inversions is always even.  Therefore, the
configuration in which 1 and 2 are swapped (which has 1 inversion) is
unreachable.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\hea}{\heartsuit}
\newcommand{\dia}{\diamondsuit}
\newcommand{\clu}{\clubsuit}
\newcommand{\spa}{\spadesuit}

\begin{problem}
A regular 52-card deck is arranged as follows:
%
\[
A \hea\ 2 \ \ldots\  K \hea\ 
A \clu\ 2 \clu \ \ldots\  K \clu\ 
A \spa\ 2 \spa \ \ldots\  K \spa\ 
A \dia\ 2 \dia \ \ldots\  K \dia
\]
%
In a \textit{perfect shuffle}, the deck is first divided into two
piles, one containing the top 26 cards and the other the bottom 26.
These two piles are then recombined into a single deck by perfectly
interlacing them:
%
\begin{center}
\begin{picture}(144,72)
\thicklines
\multiput(0,0)(0,6){12}{\line(1,0){108}}
\multiput(36,3)(0,6){12}{\line(1,0){108}}
\end{picture}
\end{center}
%
This interlacing process can be done in two different ways since the
new top card could come from the top of either 26-card pile.  So over
a sequence of perfect shuffles, many different arrangements of the
deck can be obtained.  Prove that no sequence of perfect shuffles puts
the deck in the following order:
%
\[
A \hea\ 2 \hea \ \ldots\  K \hea\ 
A \clu\ 2 \clu \ \ldots\  K \clu\ 
A \dia\ 2 \dia \ \ldots\  K \dia\ 
A \spa\ 2 \spa \ \ldots\  K \spa
\]
\end{problem}

\solution{We use induction.  Define the cards in the $i$-th and
$(52-i)$-th positions in the deck to be \textit{opposites}.  Thus, for
example, the top card is opposite the bottom card, the second card is
opposite the next to last card, and the two cards in the middle of the
deck are opposite each other.  Let $P(n)$ be the proposition that
opposite cards are the same color.

\noindent \textit{Base case.}  In the initial configuration, hearts
are opposite diamonds and clubs are opposite spades.  Therefore, all
opposite cards are the same color.

\noindent \textit{Inductive step.}  Suppose that all opposite cards are
the same color.  Consider an arbitrary configuration of the deck:
%
\[
c_1 c_2 c_3 \ldots c_{52}
\]
%
A perfect shuffle leaves the deck in one of the following orders:
%
\begin{gather*}
c_1 c_{27} c_2 c_{28} c_3 c_{29} \ldots c_{25} c_{51} c_{26} c_{52} \\
c_{27} c_1 c_{28} c_2 c_{29} c_3 \ldots c_{51} c_{25} c_{52} c_{26}
\end{gather*}
%
In both cases, exactly the same cards remain opposites: $c_1$ and
$c_{52}$, $c_2$ and $c_{51}$, etc.  So, in particular, opposite cards
are still the same color.

By induction, opposite cards are always the same color.  Therefore,
the hearts, clubs, diamonds, spades configuration is unreachable since
there all opposite cards are different colors.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Prove the following basic facts about greatest common divisors:

\bparts

\ppart $\gcd(ka, kb) = k \cdot \gcd(a, b)$ for all $k > 0$.

\solution{The smallest positive value of
%
\[
s \cdot (k a) + t \cdot (k b) = k  \cdot (s \cdot a + t \cdot b)
\]
%
over all $s, t \in \mathbb{Z}$ is $k$ times the smallest positive
value of
%
\[
s \cdot a + t \cdot b
\]
%
over all $s, t \in \mathbb{Z}$.  The first quantity is $\gcd(ka, kb)$
and the second is $\gcd(a, b)$.  Therefore, $\gcd(ka, kb) = k \gcd(a,
b)$.}

\ppart $\gcd(a, b) = \gcd(a + k b, b)$ for all $k \in \mathbb Z$.

\solution{We show that every linear combination of $a$ and $b$ is a
linear combination of $a + k b$ and $b$ and vice-versa.  
%
\begin{itemize}
\item If $x = s \cdot a + t \cdot b$, then $x = s' \cdot (a + k b) +
t' \cdot b$ where $s' = s$ and $t' = t - s' k$.
\item If $x = s' \cdot (a + k b) + t' \cdot b$, then $x = s \cdot a +
t \cdot b$ where $s = s'$ and $t = t' + s' k$.
\end{itemize}
%
Thus, in particular, the \textit{smallest positive} linear
combinations are equal, so $\gcd(a, b) = \gcd(a + k b, b)$.}

\eparts
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Here is a long run of composite numbers:
%
\[
114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126
\]
%
Prove that there exist arbitrarily long runs of composite numbers.
Consider numbers a little bigger than $n!$ where $n! = n \cdot (n - 1)
\cdots 3 \cdot 2 \cdot 1$.
\end{problem}

\solution{Let $k$ be some natural number such that $1 < k \leq n$.  We
know $k \mid (n! + k)$ because $k \mid n!$ and $k \mid k$. Thus, the
numbers $n!+2, n!+3, n!+4, \ldots, n!+n$ are all composite.  This is a
run of $n-1$ consecutive composite numbers.  Because we can choose $n$
arbitrarily, we know arbitrarily long runs of composite numbers
exist.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Here is a \textit{very, very fun} game.  Initially, there is a
blackboard with the numbers 1309 and 1729 written on it.  Now you and
I take turns; you go first.  On each player's turn, he or she must
write a new positive integer on the board that is the difference of
two numbers that are already there.  The first person who can not
create a new number loses the game.

For example, your first move must be $1729 - 1309 = 420$.  Then I
could play either $1309 - 420 = 889$ or $1729 - 420 = 1309$, and so
forth.

\bparts

\ppart Prove every number written on the board is a multiple of 7 less
than or equal to 1729.

\solution{We use induction.  Let $P(n)$ be the proposition that after
$n$ moves, every number on the board is a positive linear combination
of 1729 and 1390.

\noindent \textit{Base case.}  $P(0)$ is true because 1729 and 1390
are trivial linear combinations of 1729 and 1390.

\noindent \textit{Inductive step.}  Assume that after $n$ moves, every
number on the board is a positive linear combination of 1729 and 1390.
The next number written on the board is also a positive linear
combination, because:
%
\begin{itemize}
\item The rules require the number to be positive.
\item The new number must be a difference of two numbers already on
the board, which are themselves linear combinations of 1729 and 1390
by assumption.  And a difference of linear combinations is another
linear combination.
\end{itemize}
%
By induction, every number on the board is a positive linear
combination of 1729 and 1390.  And every positive linear combination
of 1729 and 1390 is a multiple of $\gcd(1729, 1390) = 7$.}

\ppart Prove that every positive multiple of 7 less than or equal to
1729 is on the board at the end of the game.

\solution{Let $x$ be the smallest number on the board at the end of
the game.  By the Division Algorithm, there exist integers $q$ and $r$
such that $1729 = q \cdot x + r$ where $0 \leq r < x$.  When no more
moves are possible, $1729 - x$ must already be on the board, and thus
so must $1729 - 2x$, \ldots $1729 - (q - 1) x$.  However, $1729 - q x
= r$ can not be on the board, since $r < x$ and $x$ is defined to be
the smallest number there.  The only explanation is that $r = 0$,
which implies that $x \mid 1729$.  By a symmmetric argument, $x \mid
1390$.  Therefore, $x$ is a common divisor of $x$ and $y$.  The only
common divisors of 1729 and 1390 are 1 and 7, and $x$ can not be 1 by
the preceding problem part.  Therefore, 7 is on the board at the end
of the game.  Since no more moves are possible, $1729 - 7$, $1729 - 2
\cdot 7$, \ldots, 7, 0 must all be on the board as well.  So every
positive multiple of of 7 less than or equal to 1729 is on the board
at the end of the game.}

\ppart Who wins?

\solution{There are $1729 / 7 = 247$ numbers on the board at the end
of the game.  Thus, there were $247 - 2 = 245$ moves.  Since you go
first, you also get the last move and win the game.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Prove the following theorem.

\begin{theorem*}
If $\gcd(a, b) = 1$, then $\gcd(a + b, a - b) = 1 \text{ or } 2$.
\end{theorem*}
\end{problem}

\solution{Since $\gcd(a, b) = 1$, there exist integers $s$ and $t$
such that:
%
\[
s \cdot a + t \cdot b = 1
\]
%
Now there is a linear combination of $a + b$ and $a - b$ equal to 2:
%
\[
(s + t) \cdot (a + b) + (s - t) \cdot (a - b) = 2 (s \cdot a + t \cdot b) = 2
\]
%
Thus $\gcd(a + b, a - b)$ is at most 2, which implies it is equal to 1 or 2.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
