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

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

\begin{document}

\tutprobn{2}{2/12/99}{February 12, 1999}

\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.

\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.
\eparts %% nir added 

\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.

\end{problems}

\newpage


\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 a positive integer, 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}

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

\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}


\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}


\end{document}


