\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}

\newtheorem{method}{Proof Idea}
\newtheorem{myaxiom}{Axiom}
\newtheorem{mytheorem}{Theorem}
\newtheorem{myfalsetheorem}[mytheorem]{False Theorem}

\begin{document}

\handout{tut2}{Notes for Recitation 2}{February 12, 1999}

%revised chocolate bar proof and soln to team prob 1b, by ARM, 2/12 10:30am

We review three closely-related proof techniques--- ordinary
induction, strong induction, and well-ordering--- and give examples of
each.

\section{Induction, Strong Induction, and Well-Ordering}

We have seen three closely-related techniques for proving a
proposition involving a natural-valued variable: ordinary induction,
strong induction, and well-ordering.  Each technique is justified by
an axiom.  These three axioms are stated below.

\begin{myaxiom}[Ordinary Induction]
Let $P(n)$ be a predicate.  If $P(0)$ is true and
\[
P(n) \rightarrow P(n+1)
\]
for all $n \in \mathbb{N}$, then $P(n)$ is true for all $n \in \mathbb{N}$.
\end{myaxiom}

\begin{myaxiom}[Strong Induction]
Let $P(n)$ be a predicate.  If $P(0)$ is true and
\[
P(0) \wedge P(1) \wedge \ldots \wedge P(n) \rightarrow P(n+1)
\]
for all $n \in \mathbb{N}$, then $P(n)$ is true for all $n \in
\mathbb{N}$.
\end{myaxiom}

\begin{myaxiom}[Well-Ordering]
Every non-empty subset of $\mathbb{N}$ has a least element.
\end{myaxiom}

At first glance, only ordinary induction and strong induction appear
similar, and well-ordering appears totally unrelated.  Suprisingly,
however, every proposition that can be proved using one technique can
also be proved using the other two.  In fact, if we accept just one of
these three axioms, then the statements of the other two can be proved
as theorems.

In practice, the formats of ordinary and strong induction proofs are
similar to one another, and the format of a well-ordering proof is
entirely different.  In particular, both ordinary and strong induction
proofs contain the statement of an induction hypothesis, a proof of
the base case, and a proof of the inductive step.  By contrast, a
well-ordering proof is typically a proof by contradiction that
contains an appeal to the well-ordering axiom at some key point.

A common objection is that ordinary induction is pointless, since
strong induction is strictly ``better''.  That is, in an ordinary
induction proof, we may assume $P(n)$ to prove $P(n+1)$, but in a
strong induction proof, we may assume $P(0), P(1), \ldots, P(n)$ to
prove $P(n+1)$.  Presumably, proving $P(n+1)$ is easier in a strong
induction proof, since we are allowed to assume more facts.  So why
would anyone ever use ordinary induction?

From a theoretical standpoint, whether one uses ordinary or strong
induction makes no difference.  As noted above, every statement that
can be proved with ordinary induction can be proved with strong
induction and vice versa.  However, from a practical standpoint,
ordinary induction is often sufficient; that is, $P(n+1)$ follows as
easily from $P(n)$ alone as from $P(0), P(1), \ldots, P(n)$ all
together.  In such cases, an ordinary induction proof is marginally
simpler to read and write.

\section{Finding an Induction Proof}

While the format of an induction proof is standard, there is no rigid
plan for finding such a proof.  There are, however, a few good tricks
to know.  There are usually two difficulties in completing a proof by
induction: choosing the right induction hypothesis, $P(n)$, and
completing the inductive step.  (Sometimes proving even the base case
is hard.)  The most obvious candidate for an induction hypothesis is
the theorem statement itself.

\begin{method}
When searching for a proof by induction, first try to lift an
induction hypothesis directly from the theorem statement.
\end{method}

To complete the inductive step, we must prove that $P(n) \rightarrow
P(n+1)$ for all $n \in \mathbb{N}$.  Typically $P(n)$ and $P(n+1)$ are
very similar statements, but with some small difference or gap.  The
challenge is to clearly identify this gap and then to bridge it with
some extra facts.  Working ``backward'' is often helpful.

\begin{method}
To prove $P(n) \rightarrow P(n+1)$, write down $P(n+1)$ and then use
$P(n)$ to reduce this statement to a simpler assertion; this assertion
is the extra fact needed to bridge the gap from $P(n)$ to $P(n+1)$ and
complete the proof.
\end{method}

\section{Proof Examples}

This section shows examples of proofs using ordinary induction, strong
induction, and well ordering.  There are also some bogus examples to
illustrate what can go wrong in an induction proof.

\subsection{Ordinary Induction Examples}

A common use of induction is to generalize an equation involving two
terms to an equation involving an arbitrary number of terms.  For
example, last week we proved that if $A$, $B$, and $C$ are sets, then

\begin{eqnarray*}
A \cap (B \cup C) & = & (A \cap B) \cup (A \cap C).
\end{eqnarray*}

The following theorem generalizes this equation to an arbitary number
of terms.

\begin{mytheorem}[Distributive Law]
Let $A, B_1, B_2, \ldots, B_n$ be sets, where $n \geq 1$.  Then

\begin{eqnarray*}
A \cap (B_1 \cup B_2 \cup \ldots \cup B_n)
	& = &	(A \cap B_1) \cup (A \cap B_2) \cup \ldots \cup (A \cap B_n).
\end{eqnarray*}
\end{mytheorem}

The proof uses ordinary induction.  As is usual for proofs of this
type, the induction hypothesis is lifted directly from the theorem
statement, and the bridge between $P(n)$ and $P(n+1)$ is the simple
two-term equation given above.

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that

\begin{eqnarray*}
A \cap (B_1 \cup \ldots \cup B_n)
	& = &	(A \cap B_1) \cup \ldots \cup (A \cap B_n).
\end{eqnarray*}

In the base case, $P(1)$ is the proposition that $A \cap B_1 = A \cap
B_1$, which is true trivially.  In the inductive step, for $n \geq 0$
assume

\begin{eqnarray*}
A \cap (B_1 \cup \ldots \cup B_n)
	& = &	(A \cap B_1) \cup \ldots \cup (A \cap B_n)
\end{eqnarray*}

in order to prove

\begin{eqnarray*}
A \cap (B_1 \cup \ldots \cup B_n \cup B_{n+1})
	& = &	(A \cap B_1) \cup \ldots
		\cup (A \cap B_n) \cup (A \cap B_{n+1}).
\end{eqnarray*}

We can transform the right side of this equation into the left side as
follows.

\begin{eqnarray*}
(A \cap B_1) \cup \ldots \cup (A \cap B_n) \cup (A \cap B_{n+1})
	& = &	(A \cap (B_1 \cup \ldots \cup B_n)) \cup (A \cap B_{n+1}) \\
	& = &	A \cap (B_1 \cup \ldots \cup B_n \cup B_{n+1})
\end{eqnarray*}

The first step uses the induction hypothesis, and the second step uses
the original two-term equation.  This shows that $P(n)$ implies
$P(n+1)$ and completes the proof.
\end{proof}

The next example of an ordinary induction proof makes use of modular
arithmethic.  Related notation is reviewed below.  In these
definitions, $a$ and $b$ are integers, and $m$ is a positive integer.

\begin{itemize}
\item $a \mid b$ (read ``$a$ divides $b$) means that $b$ is a multiple
of $a$; that is, $b = a k$ for some integer $k$.  For example, $7 \mid
21$, since $21 = 7 \cdot k$ where $k = 3$.

\item $a \equiv b \pmod{m}$ (read ``$a$ is congruent to $b$ modulo
$m$'') means that $a$ and $b$ leave the same remainder when divided by
$m$.  For example, $15 \equiv 9 \pmod{6}$ because 15 and 9 both leave
a remainder of 3 when divided by 6.  Equivalently, $a \equiv b
\pmod{m}$ means that $m \mid (a - b)$.

\item $a \bmod m$ (read ``$a$ mod $m$'') is the remainder when $a$ is
divided by $m$.  For example, $15 \bmod 6$ is equal to 3, because 15 divided
by 6 leaves a remainder of 3.  More precisely, $a \bmod m$ is the
unique number $r$ such that $a = mk + r$ where $k$ is an integer and
$0 \leq r < m$.
\end{itemize}

Note that $a \mid b$ and $a \equiv b \pmod{m}$ are propositions, but
that $a \bmod b$ is an integer quantity.  These two different notions
of ``$\bmod$'' are related in the following way:

\begin{eqnarray*}
a \equiv b \pmod{m} & \text{iff} & (a \bmod m) = (b \bmod m)
\end{eqnarray*}

\begin{mytheorem}
If $n$ is an odd positive integer, then $n^2 \equiv 1 \pmod{8}$.
\end{mytheorem}

This theorem is a little different in that we are not required to
prove a result for all positive $n$, but rather just for odd positive
$n$.

There are two ways to handle this complication.  One approach is to
reformulate the theorem as follows: if $k$ is a non-negative integer,
then $(2k+1)^2 \equiv 1 \pmod 8$.  This is equivalent to the original
theorem, since the expression $2k+1$ takes on all odd positive values
as $k$ takes on all non-negative values.  Now a proof by ordinary
induction on $k$ works.

A second approach is to use a variant of induction.  Suppose that we
prove proposition $P(1)$ and prove that $P(n)$ implies $P(n+2)$ for
all odd positive integers $n$.  Then we should believe that $P(1),
P(3), P(5), \ldots$ are all true for the same reason that we believe
ordinary induction works.  In effect, we introduce a new axiom just as
credible as the original induction axiom.  We will use this second
approach in the proof.

Introducing new induction-like axioms all the time might not seem like
a good idea.  But all of these little variants on induction can be
proven from the simple, original axiom.  So there is no great harm.
The key point is that there must be a chain of implications extending
from each predicate back to the base case (or cases).

\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
$n^2 \equiv 1 \pmod{8}$.  In the base case, $P(1)$ is true because
$1^2 \equiv 1 \pmod{8}$.

In the inductive step, for odd $n \geq 1$ assume that $n^2 \equiv 1
\pmod{8}$ to show that $(n+2)^2 \equiv 1 \pmod{8}$.  Since $n$ is an
odd integer, $4n + 4 = 4(n+1) = 8(\frac{n+1}{2}) \equiv 0 \pmod{8}$.
Adding this to the induction hypothesis implies that $n^2 + 4n + 4
\equiv 1 + 0 \pmod{8}$.  Simplifying this congruence gives $(n+2)^2
\equiv 1 \pmod{8}$.  Therefore, $P(n)$ implies $P(n+2)$, and the claim
is proved by induction.
\end{proof}

This proof contains a mystery.  Where did the magic term $4n + 4$ come
from?  Here is the reasoning that one might follow to discover the
inductive step in this proof.  We want to prove that $(n+2)^2 \equiv 1
\pmod{8}$, and we can assume that $n^2 \equiv 1 \pmod{8}$.  To go from
the assumption to the desired result, we need to add a little bit to
the left side, changing $n^2$ to $(n+2)^2$.  The value of this little
bit is $(n+2)^2 - n^2 = 4n + 4$.  We lucked out because, it is not
hard to see that this is always a multiple of 8 when $n$ is odd.
Arranging these observations into a straight line of reasoning gives
the proof.


\subsection{Strong Induction Example}

We are given a chocolate bar with $m \times n$ squares of chocolate,
and our task is to divide it into $mn$ individual squares.  We 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.  We would like to prove the following general result:
 
\begin{mytheorem}
To divide up a chocolate bar with $m \times n$ squares, we need at
most $m n - 1$ splits.
\end{mytheorem}

This theorem does not immediately lend itself to an induction proof,
since there are two variables.  In general, propositions involving
several natural-valued variables can often be proved by using a sort
of nested induction.  However, in this case, we can get by with a
single-variable induction and a trick.

Intuitively, to break up a big chocolate bar, we need one split to
make two pieces, and then we can break up the two pieces recursively.
This suggests a proof using strong induction on the {\em size} of the
chocolate bar, where size is measured in chocolate squares.  Now
instead of a problem involving two variables (the two dimensions), we
have a problem in one variable (the size).  With this simplification,
we can prove the theorem using strong induction.

\begin{proof}
The proof is by strong induction on the size of the chocolate bar.  Let
$P(k)$ be the proposition that a chocolate bar of size $k$ requires at
most $k - 1$ splits.  

\emph{Base case, $k=1$}: $P(1)$ is true because there is only a single
square of chocolate, and $1 - 1 = 0$ splits are required.

\emph{Induction step}: We suppose $k \geq 1$ and any chocolate bar of size
$s$, where $1 \leq s \leq k$, requires at most $s-1$ splits.  We must now
show there is a way to split a chocolate bar of size $k+1$ with at most
$k$ splits.

To do this, first break the chocolate bar of size $k+1$ into two smaller
pieces of size $p$ and $q$ where $p + q = k + 1$.  This is certainly
possible because the size of the bar is at least two.  Now the pieces of
sizes $p$ and $q$ are between one and $k$, so by strong induction,
breaking these two pieces into single squares requires only $p - 1$ and $q
- 1$ splits, respectively.  The total number of splits required to break
the bar of size $k+1$ into single squares is therefore at most $1 + (p -
1) + (q - 1) = p + q - 1 = (k + 1) - 1 = k$.

This shows that $P(k)$ implies $P(k+1)$, and the claim is proved by
strong induction.
\end{proof}

\textbf{Class Exercise}: The theorem proves that \emph{at most} $mn - 1$
splits are needed to divide up an $m$ by $n$ chocolate bar.  Could you do
better?

\emph{Answer}: The proof really shows that exactly $s - 1$ splits are
needed.  Observe that in the induction step, no matter how we split the
bar into smaller bars of size $p$ and $q$, exactly $(p - 1) + (q - 1) = s
- 1$ splits are required.


\subsection{Well-Ordering Example}

The well-ordering principle gives an alternate proof of the following
familiar fact.

\begin{mytheorem}
The square root of 2 is irrational.
\end{mytheorem}

\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that the square root of 2 is rational.  Then $\sqrt{2}$
is equal to $m / n$ for some integers $m$ and $n > 0$.

Let $S$ be the set of all positive integers $k$ such that $k
\sqrt{2}$ is an integer.  The set $S$ is non-empty, because it
contains $n$.  Thus, by the well-ordering principle, the set $S$
contains a smallest element $k_0$.

Now consider the number $k_0 (\sqrt{2} - 1)$.  This is an integer,
since it is equal to $k_0 \sqrt{2} - k_0$, and both of these terms are
integers.  Furthermore, it is positive, since it is equal to
$k_0 \cdot 0.414\ldots$.  Finally, multiplying this number by
$\sqrt{2}$ gives $2 k_0 - k_0 \sqrt{2}$, which is again an integer
because both terms are integers.  Therefore, the number $k_0 (\sqrt{2}
- 1)$ is an element of $S$ that is smaller than $k_0$.  This is a
contradiction, and so $\sqrt{2}$ must be irrational.
\end{proof}

\textbf{Class Exercise}: How could this argument be generalized to prove
that the square root of an every non-square is irrational?  Why does this
generalized argument not prove that $\sqrt{4}$ is irrational?

\emph{Answer}: Instead of arguing with $\sqrt{2}$, make the argument with
$\sqrt{n}$.  The main trick is that the second paragraph should begin,
``Now consider the number $k_0 (\sqrt{n} - \lfloor \sqrt{n} \rfloor)$''.
If $n$ is a perfect square, then the proof breaks down in the next
sentence; the number $k_0 (\sqrt{n} - \lfloor \sqrt{n} \rfloor)$ is not
positive in this case, but zero.

\subsection{Bogus Examples}

The following theorems are false, but where exactly are the bugs in
the proofs?

\begin{myfalsetheorem}
$\forall x \in \mathbb{R} \ \forall n \in \mathbb{N} \ x^n=1$
\end{myfalsetheorem}

\begin{proof}
The proof by strong induction on $n$.  Let $P(n)$ be the proposition
that $x^n = 1$ for all real $x$.  In the base case, $P(0)$ hold
because $x^n = x^0 = 1$ by definition of ``zeroth power'' of a real
number.

In the inductive step, for $n \geq 0$ assume that $x^k = 1$ for all
real $x$ and for all integers $0 \leq k \leq n$ in order to prove that
$x^{n+1} = 1$ for all real $x$.

We must show that $x^{n+1}=1$. By the induction hypothesis, with $k=n$
and $k=1$, we have $x^n=1$ and $x^1=1$.  So,
\[
x^{n+1} = x^n \cdot x^1 = 1 \cdot 1 = 1.
\]
\end{proof}

The proof of the induction step is not correct when $n=0$.  In this
case, $k=1$ does not satisfy $0 \leq k \leq n$.  Therefore we cannot
assume by strong induction that $x^1 = 1$, which is false anyway when
$x \neq 1$.

\begin{myfalsetheorem}
Let $p$, $n$, and $x_1, x_2,\ldots, x_n$ be positive integers.  If $p
\mid x_1 x_2 \cdots x_n$, then $p \mid x_i$ for some $1 \leq i \leq
n$.
\end{myfalsetheorem}

\begin{proof}
The proof by strong induction on $n$.  Let $P(n)$ be the proposition
that if $p$ divides the product $x_1 x_2 \cdots x_n$, then $p$ divides
$x_i$ for some $1 \leq i \leq n$.  In the base case, $P(1)$ is true
trivially; if $p$ divides the product $x_1$, then $p$ divides $x_1$.

In the inductive step, assume $P(1), \ldots, P(n)$ to prove $P(n+1)$.

So suppose that $p \mid x_1x_2\cdots x_{n+1}$.  Let $y_n = x_n
x_{n+1}$, so $x_1x_2\cdots x_{n+1} = x_1x_2\cdots x_{n-1}y_n$.  Since
the right side of this equality is a product of $n$ terms, we have by
induction that $p$ divides one of them.  If $p \mid x_i$ for some $i <
n$, then we have the desired $i$.  Otherwise $p \mid y_n$.  But since
$y_n$ is a product of the two terms $x_n, x_{n+1}$, we have by strong
induction that $p$ divides one of them.  So in this case $p \mid x_i$
for some $i = n$ or $i = n+1$.
\end{proof}

The statement ``we have by strong induction that $p$ divides one of them''
is the place where the proof breaks down: it appeals to strong induction
to justify applying the induction hypothesis for $2=k\leq n$.  But the
base case was $n=1$, so we can't assume $2 \leq n$.  Note that the
reasoning above is fine for every $n\geq 2$, so the whole proof would be
fine if we had an argument to prove the claim for $n+1=2$.  But of course
we can't prove it for $n+1=2$ because it isn't true: let $p=6, x_1 =2, x_2
=3$.  Even though the reasoning is fine for every $n\geq 2$, the fact that
it failed for $n=1$ let us deduce a patently false result.

\section{Team Problems}

\begin{problems}

\problem %From F97 PS2 Problem 10, much revised by ARM

An $n$-player tournament, consists of some set of $n\geq 2$ elements
called {\em players}, and, for every two distinct players, a specification
that one of the players beats the other.  That is, player $p_1$ beats
player $p_2$ iff $p_2$ does not beat $p_1$, for all players $p_1 \neq
p_2$, and no player beats him/herself.

A sequence of players $p_1,p_2, \ldots, p_k$ (for some $k \leq n$), such
that player $p_i$ beats player $p_{i+1}$ for $1 \leq i < k$ is called a
{\em ranking} of these players.  If also player $p_k$ beats player $p_1$,
the ranking is called a $k$-{\em cycle}.

\bparts

\ppart Prove that in every tournament, either there is a ``champion''
player that beats every other player, or there is a 3-cycle.

{\bf Solution}: (Proof by induction.)  The induction hypothesis $P(n)$, is
``In an $n$-player tournament, either there is a player that
beats every other player, or there is a 3-cycle.''

{\bf Base case $n=2$:} By definition of a 2-player tournament, one of the
players beats the only other player and therefore is the champion.

{\bf Inductive step:}
Assume that $P(n)$ is true in order to show that $P(n+1)$ is true.

Consider an $n+1$-player tournament.  If there is a champion, we are done.
So we may assume that every player is beaten by some other player.  Now
remove any player, say player $p$, and treat the remaining $n$ players as an
$n$-player tournament.  There are two cases:

1) Every player in the $n$-player tournament is beaten by some other
player in the tournament.

2) There is some champion in the $n$-player tournament who beats every
other player in the $n$-player tournament.

In case (1), we have by induction hypothesis a 3-cycle of players in the
$n$-player tournament.  Since a 3-cycle in the $n$-player tournament will
also be a 3-cycle in the full $n+1$-player tournament, we are OK in this
case.

In case (2), there is some ``champion'', $q$, in the $n$-player
tournament.  Since everybody in the ($n+1$)-player tournament is beaten by
somebody, $q$ must be beaten by a player not in the $n$-player tournament,
that is, $p$ beats $q$.  For the same reason, there is some
player $r$ that beats $p$.  Since $r$ is in the $n$-player tournament, $r$
is beaten by the champion $q$.  So we have found a 3-cycle $p,q,r$.


\ppart
A {\em consistent ranking} is a sequence $p_1,p_2, \ldots, p_n$ of all
$n$ players in the tournament such that $p_i$ beats $p_j$ iff $i < j$, for
$1 \leq i,j \leq n$.  Conclude that a tournament has no consistent ranking
iff some subset of three of its players has no consistent ranking.

{\bf Solution}: By definition of tournament, the restriction of the
tournament to any subset of two or more of its players is also a
(sub)tournament.  Also any consistent ranking of a tournament remains
consistent when restricted to a subset of players.  So if some subset of
three players has no consistent ranking, then the whole tournament
can't have a consistent ranking either.

So we have only to prove the converse implication: if every three players
have a consistent ranking, then the tournament as a whole has one.
The proof is by induction on $n$.

{\bf Base case $n=2$:} Every two player tournament obviously has a
consistent ranking.

{\bf Inductive step:} Suppose $n\ge2$ and there is a consistent ranking of
any tournament of $n$ players whose three-player subsets have consistent
rankings.  Now consider any $n+1$ player tournament whose three-player
subsets have consistent rankings.

This tournament cannot have a 3-cycle, because there is no consistent
ranking for the players in the 3-cycle.  Hence, by the previous part, the
tournament has a champion.  The $n$-player tournament obtained by ignoring
the champion also has no 3-cycles, so by induction it has a consistent
ranking.  Then this ranking of $n$-nonchampions followed by the champion
at then end is a consistent ranking of the whole tournament of $n+1$
players.

\eparts

\problem I recently went to a party with my Significant Other; there
were 11 other couples there.  A lot of handshaking happened, but of
course no one shook hands with their Significant Other.  At the end,
it turned out that for every $k$ from $0$ to $22$, someone other than
me had shaken hands with exactly $k$ people.  How many people did I
shake hands with?  Prove your answer.

\textbf{Solution}:
We will prove the following for a set of $n$ couples:
\begin{theorem}
Suppose at a party for $n$ couples (total) it turns out that
someone other than me has shaken $k$ hands for every $k$ from $0$ to $2n-2$. 
Then I must have shaken $n-1$ hands.
\end{theorem}

\begin{proof}
By induction on $n$.

\emph{Base case, $n=1$}: There are no other couples. My wife has shaken
$0$ hands (can't shake with me). I have shaken $0$ hands ($=n-1$). (some
party!)

\emph{Induction case}: Assume $P(n-1)$ is true for some $n>1$. To prove
$P(n)$, consider a party with $n$ couples.

Someone has shaken $2n-2$ hands, i.e., with everyone in the room except
themselves and their spouse. Therefore everyone else but this couple has
shaken hands at least once. So the one who hasn't shaken hands at all must
be this person's spouse. $2n-2$ is paired with $0$.  Consider the subparty
of the remaining $n-1$ couples. I must be in this group since there cannot
be two people who shook hands $2n-2$ times or $0$ times. Consider the
number of times this group of people has shaken hands among themselves,
i.e., not counting handshakes with the $2n-2, 0$ couple. Then the number
of handshakes I see is every number between $0$ and $2n-4$. This is
because this group of people has original handshake counts of
$1,2,3,\ldots, 2n-3$. Since everyone shakes the $2n-2$ person's hand once,
we are left with handshake counts of $0,1,\ldots,2n-4$.  This is exactly
the premise of $P(n-1)$. So by the I.H. I must have shaken $n-2$ hands
within this group. Adding the one handshake with the $2n-2, 0$ couple, I
must have shaken a total of $n-1$ hands.

\end{proof}

Note that there are 24 people (12 couples)in this case.  So $n=12$, and
the answer is that I shook 11 hands.
\end{problems}
\end{document}


