\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{2, Fri.}                    % !! start the paper

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

\begin{problem}

In a group of people, every pair of people has either met or not met.  A
{\em triangle} in a group is a set of three people such that either every
pair of them has met, or else no pair of them has met.

\begin{theorem}
Every group of 6 people contains a triangle.
\end{theorem}

\bparts

\ppart \textbf{Work an example.}  Draw 6 dots to represent the 6
people.  Use solid lines to connect people who met and dotted lines to
connect people who did not meet.  Try to avoid creating a triangle!
Try to figure out what keeps forcing you to create a triangle.

\instatements{\newpage}

\ppart The skeleton of a proof is provided below.  Fill in the
details.

\begin{proof}
The proof is by case analysis\footnote{Describing your approach at the
outset helps orient the reader.}.  Let $x$ be one of the six
people\footnote{Defining some notation may simplify your argument.
However, be sure to {\em define} whatever notation you use.  Don't
just start using it and expect the reader to catch on!}.  There are
two cases:

\begin{enumerate}
\item Among the remaining 5 people, there exist 3 that did meet $x$.
\item Among the remaining 5 people, there exist 3 that did not meet $x$.
\end{enumerate}

At least one of these two cases must hold, because\ldots\footnote{Part
of a case analysis argument is showing that you've covered all the
cases.  Often this is trivial, because the two cases are of the form
``$X$'' and ``not $X$''.  However, the situation here is not so
simple.}

\solution[\vspace{2in}]{If at most 2 met $x$ and at most 2 did not
meet $x$, then at least 1 of the remaining 5 people is left
unaccounted for.}

\underline{Case 1.}  Suppose that there exist 3 people that did meet
$x$.

\solution[\vspace{3in}]{If no pair among those three met, then those
three form a triangle.  However, if some pair among those three did
meet, then that pair, together with $x$, form a triangle.}

Therefore, the group must contain a triangle in this case.

\instatements{\newpage}

\underline{Case 2.}  Suppose that there exist 3 people that did not
meet $x$.

\solution[\vspace{3in}]{If every pair among those three met, then
those three form a triangle.  If some pair among those three did not
meet, then that pair, together with $x$, form a triangle.}

The group must contain a triangle in this case as well.  Therefore, a
group of 6 people contains a triangle in all cases.
\end{proof}

\eparts

\end{problem}

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

\instatements{\newpage}

\begin{problem}

\begin{theorem}
Let $a$ and $b$ be positive integers.  Then $\gcd(a, b)$ is equal to
the smallest positive integer that can be expressed as an integer
linear combination of $a$ and $b$.
\end{theorem}

\bparts

\ppart \textbf{Make sure that you understand all definitions.}  What
is the $\gcd$ of two numbers?  For that matter, what exactly does it
mean that $p$ is a divisor of $q$?  What is an ``integer linear
combination of $a$ and $b$''?  If you don't know, look in Rosen or ask
your TA.  (We've left some space below, in case you want to make
notes, but nothing is required.)

\solution[\vspace{3in}]{An integer $a$ is a {\em divisor} of an
integer $b$ if there exists an integer $c$ such that $a \cdot c = b$.
For example, 9 is a divisor of 27, because $9 \cdot 3 = 27$.

The {\em greatest common divisor} ($\gcd$) of $a$ and $b$ is the
largest integer that is a divisor of both $a$ and $b$.  For example,
the greatest common divisior of 9 and 21 is 3.

An {\em integer linear combination} of $a$ and $b$ is an expression of
the form $x \cdot a + y \cdot b$, where $x$ and $y$ are integers.  For
example, $3 \cdot a + (-5) \cdot b$ is one integer linear combination
of $a$ and $b$.}

\ppart \textbf{Work an example.}  Pick some small values for $a$ and
$b$ and see if the theorem holds.  When searching for an integer linear
combination, remember that negative numbers are integers, too!
{\small (sniff)}

\solution{Suppose we choose $a = 9$ and $b = 21$.  Then $\gcd(a, b) =
3$.  Therefore, we want to find an integer linear combination of $a$
and $b$ that is equal to 3.  Some trial and error turns up the
following solution:

\begin{eqnarray*}
-2 \cdot 9 + 1 \cdot 21 & = & 3
\end{eqnarray*}
}

\instatements{\newpage}

\ppart The skeleton of a proof is given below.  Fill in the details.

\begin{proof}
Let $m$ be the smallest positive integer that can be expressed as a
integer linear combination of $a$ and $b$; in particular, suppose $m =
s a + t b$.

First, we show that $m$ is a divisor of $a$.  We use proof by
contradiction.  Suppose $m$ is {\em not} a divisor of $a$.  Then
dividing $a$ by $m$ using long division yields a quotient $q$ and a
remainder $r$ such that

\begin{eqnarray*}
a & = & q \cdot m + r
\end{eqnarray*}

\noindent where $0 < r < m$.  Rearranging terms in the equation
above, we find:

\solution[
\begin{eqnarray*}
r & = & \hspace{3in} \\
\\
& = & \\
\\
& \ldots &
\end{eqnarray*}
\vspace{2in}
]{
\begin{eqnarray*}
r   & = & a - q \cdot m \\
    & = & a - q \cdot (s a + t b) \\
    & = & (1 - q s) \cdot a + (- q t) \cdot b
\end{eqnarray*}
}

\noindent Therefore, $r$ is a positive number smaller than $m$
expressible as a integer linear combination of $a$ and $b$.  Thus, we
can conclude that $m$ is a divisor of $a$ because\ldots

\solution[\vspace{1.5in}]{\ldots this contradicts the definition of
$m$.  Therefore, our supposition that $m$ is not a divisor of $a$ must
be wrong.}

By a similar argument, $m$ is a divisor of $b$.  Therefore, $m$ is a
common divisor of $a$ and $b$.

\instatements{\newpage}

All that remains is to show that $m$ is the {\em greatest} common
divisor of $a$ and $b$.  Since $\gcd(a, b)$ is a divisor of both $a$
and $b$, there exist integers $x$ and $y$ such that:

\begin{eqnarray*}
x \cdot \gcd(a, b) & = & a \\
y \cdot \gcd(a, b) & = & b
\end{eqnarray*}

\noindent We can now show that $\gcd(a, b)$ is a divisor of $m$ as
follows:

\solution[
\begin{eqnarray*}
m & = & \hspace{3in} \\
\\
\\
  & \ldots & 
\\
\\
\\
  & = & \left(\hspace{3in}\right) \cdot \gcd(a, b)
\end{eqnarray*}]{
\begin{eqnarray*}
m & = & s a + t b \\
  & = & s (x \cdot \gcd(a, b)) + t (y \cdot \gcd(a, b)) \\
  & = & (s x + t y) \cdot \gcd(a, b)
\end{eqnarray*}
}

This implies that $\gcd(a, b) \leq m$.  Since $m$ is a common divisor
of $a$ and $b$ and is at least as large as the greatest common
divisor, $m$ must actually be the greatest common divisor of $a$ and
$b$.
\end{proof}

\eparts

\end{problem}

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

\end{document}
