\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\begin{document} 
\inclassproblems{3, Fri.}                    % !! start the paper


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

\begin{problem}
In 1769, Euler conjectured that there are no positive integer
solutions to the equation:

\begin{eqnarray*}
a^4 + b^4 + c^4 & = & d^4
\end{eqnarray*}

This was disproved more than 200 years later when Noam Elkies of
Harvard found a solution.  Not bad--- {\em if you're a wimpy Harvard
mathematician.}

Let's make Euler's equation more complicated by adding some coefficients:
\begin{eqnarray}\label{wc}
8 a^4 + 4 b^4 + 2 c^4 & = & d^4
\end{eqnarray}

Use the least-number principle to prove that equation~(\ref{wc}) has no
positive integer solutions.

\solution{Suppose that there exists a solution.  Then, by the least
number principle, there exists a solution that minimizes the sum $a +
b + c + d$.  We will show that, in this solution, $a$, $b$, $c$, and
$d$ must all be even.  However, we can then obtain another solution
over the positive integers with a smaller sum by dividing $a$, $b$,
$c$, and $d$ in half.  This is a contradiction, and so no solution
exists.

All that remains is to show that $a$, $b$, $c$, and $d$ must all be
even.  The left side of equation~(\ref{wc}) is even, so $d^4$ is even,
so $d$ must be even.  Substituting $d = 2 d'$ into equation~(\ref{wc})
gives:

\begin{eqnarray}
8 a^4 + 4 b^4 + 2 c^4 & = & 16 d'^4
\end{eqnarray}

Now $2 c^4$ must be a multiple of 4, since every other term is a
multiple of 4.  This implies that $c^4$ is even and so $c$ is also
even.  Substituting $c = 2 c'$ into the previous equation gives:

\begin{eqnarray}
8 a^4 + 4 b^4 + 32 c'^4 & = & 16 d'^4
\end{eqnarray}

Arguing in the same way, $4 b^4$ must be a mutliple of 8, since every
other term is.  Therefore, $b^4$ is even and so $b$ is even.
Substituting $b = 2 b'$ gives:

\begin{eqnarray}
8 a^4 + 64 b'^4 + 32 c'^4 & = & 16 d'^4
\end{eqnarray}

Finally, $8 a^4$ must be a multiple of 16, $a^4$ must be even, and so
$a$ must also be even.  Therefore, $a$, $b$, $c$, and $d$ must all be
even, as claimed.}
\end{problem}

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

\instatements{\newpage}

\begin{problem}
You are given a chocolate bar that consists of $m \times n$ squares of
chocolate.  Your task is to break it up into $mn$ individual squares.
You are only allowed to split one piece of chocolate at a time using a
vertical or a horizontal break.

For example, suppose that the chocolate bar is $2 \times 2$.  The
first split makes two pieces, both $2 \times 1$.  Each of these pieces
requires one more split to form single squares.  This gives a total of
three splits.

Use the least-number principle to prove the following theorem:

\begin{theorem*}
You need exactly $m n - 1$ splits to break a chocolate bar with $m
\times n$ squares into individual squares.
\end{theorem*}

\solution{Suppose that the claim is false.  There there must exist a
counterexample with smallest area.  This smallest counterexample can
not be a $1 \times 1$ candy bar, because this requires exactly $1
\cdot 1 - 0 = 0$ splits.

So the smallest counterexample must be $m \times n$, where $m$ and $n$
are not both 1.  Orient the bar so that $m > 1$.  Then we can split
the bar to create two bars with sizes

\[
m_1 \times n \hspace{1in} \text{and} \hspace{1in} m_2 \times n
\]

\noindent where $m_1 + m_2 = m$.  The claim must hold for these bars,
since they are both smaller than the smallest counterexample.
However, this implies that dividing up the original bar requires
exactly $1 + (m_1 n - 1) + (m_2 n - 1) = m n - 1$ splits.  This is a
contradiction.  Therefore, the claim must actually be true.

(Alternatively, note that each split increases the total number of
pieces by exactly 1.  Therefore, converting 1 bar into $m n$ pieces
requires exactly $m n - 1$ splits.)}
\end{problem}

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

\end{document}
