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

\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{graphics}
\usepackage{amsfonts}
\usepackage{amssymb}

\addtolength{\textheight}{.05in}

\begin{document}

\pset{5}{March 18, 2003}{Start of class on Tuesday, April 1}

%\newcommand{\solution}[1]{}                          % hide solutions
\newcommand{\solution}[1]{\textbf{Solution.} #1}    % show solution
\newcommand{\comment}[1]{}                          % comment sections

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }
\newcommand{\pr}[1]{\text{Pr} \left\{ #1 \right\} }

\begin{problems}

% RELATIONS
% * equivalence class problem - bracelet with beads
% * modular arithmetic

% DIGRAPHS
% * max degree is king
% * hampath

% INDUCTION
% Fibonacci
%   Cassini's identity
%   sums

% FUNCTIONS
% * n! permutations
% * composition
% * Conan and Xena

% OPTIONAL
% can't have two kings

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


\problem A sequence of four bits is called a {\em nibble}.  Let $N$ be
the set of all nibbles, and let $\sim$ be a binary relation on $N$.
The relation $x \sim y$ holds if and only if $y$ can be obtained by
{\em rotating} $x$ one or more times.  Rotating the nibble $b_1 b_2
b_3 b_4$ gives the nibble $b_4 b_1 b_2 b_3$, where $b_i \in \{ 0, 1
\}$.

\begin{problemparts}

\problempart Show that $\sim$ is an equivalence relation.

\solution{
To show that $\sim$ is an equivalence relation, we must show that it is
symmetric, reflexive and transitive.

Let $R : N \to N$ such that $R(b_1 b_2 b_3 b_4) = 
b_4 b_1 b_2 b_3$. $R$ is simply the rotation operation. 
We shall denote the $n$-th iteration of $R$ by $R^n$. For
example, $R^3(x) = R(R(R(x)))$. 

%The definition of $\sim$ says that $\forall
%x \forall y, x \sim y \leftrightarrow (\exists n)

\begin{itemize}

\item First, we note that for any nibble $x$, $R^4(x) = x$. Therefore for
any nibble x, $x \sim x$, so $\sim$ is reflexive.

\item Now suppose that $x \sim y$. That means that there exists $n>0$ such
that $y=R^n(x)$. Let $m$ be any multiple of 4 such that $m > n$. Because
$R^4(x) = x$, $R^m(x)=x$ (we could prove this by induction on $m/4)$. But
$R^m(x) = R^{m-n}(R^n(x)) = R^{m-n}(y)$ where $m-n>0$. Therefore, $y \sim
x$. We have shown that $\sim$ is symmetric.

\item Finally, suppose $x \sim y$ and $y \sim z$. Then $y = R^n(x)$ and $z
= R^m(y)$ with $n>0$ and $m>0$. Thus, $z = R^m(R^n(x)) = R^{m+n}(x)$ and $m+n>0$, so $x
\sim z$. Therefore $\sim$ is transitive.

\end{itemize}

We conclude that $\sim$ is an equivalence relation as it is reflexive,
symmetric and transitive.
}

\problempart Describe the equivalence classes of $N$ under the
relation $\sim$.

\solution{
The equivalence classes of $\sim$ are produced by taking a
nibble for which the equivalence class isn't known, rotating it to get all
the nibbles in its class, and then repeating this procedure until all
nibbles have been placed in an equivalence class.

The equivalence classes are:

\begin{enumerate}

\item 0000
\item 0001, 0010, 0100, 1000
\item 0011, 0110, 1100, 1001
\item 0101, 1010
\item 0111, 1110, 1101, 1011
\item 1111

\end{enumerate}

}

\end{problemparts}

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

\problem Let $p$ be a positive integer.  Then integers $x$ and $y$ are
{\em congruent modulo $p$} if $x - y$ is a multiple of $p$.  In symbols,
this is written $x \equiv y \pmod{p}$.

\begin{problemparts}

\problempart Which integers are congruent to $1$ mod $4$?

\solution
{
There are infinitely many integers that are congruent to $1$ mod $4$. From
the definition, they are all the integers which can be written $1 + 4 k$, 
where $k$ is any integer. Those integers are: $\dots, -11, -7, -3, 1, 5, 9,
13, \dots$.
}

\problempart Show that congruence modulo $p$ is an equivalence relation.

\solution{
To show that congruence modulo $p$ is an equivalence relation, we show that it
is reflexive, symmetric and transitive.

\begin{itemize}

\item For any integer $x$, $x - x = 0 = p \cdot 0$, so $x \equiv x \pmod{p}$. So
congruence modulo $p$ is reflexive.

\item For any integers $x$ and $y$ such that $x \equiv y \pmod{p}$, we have $x -
y = p k$, where $k$ is an integer. Therefore, $y - x = p \cdot (-k)$,
where $-k$ is also an integer, so $y \equiv x \pmod{p}$. So congruence
modulo $p$ is symmetric.
                   
\item For any integers $x$, $y$ and $z$ such that $x \equiv y \pmod{p}$ and $y
\equiv z \pmod{p}$, there exist integers $i$ and $j$ such that $x -
y = p i$ and $y - z = p j$. Therefore $x - z = x - y + y - z =
p (i + j)$. Since $i + j$ is also an integer, we conclude that $x
\equiv z \pmod{p}$. So congruence modulo $p$ is transitive.

\end{itemize}

Since it is reflexive, symmetric and transitive, congruence modulo $p$ is
an equivalence relation.
}

\end{problemparts}

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

\problem Fibonacci numbers are defined as follows:

\beqn
F(0)	& = &	0 \\
F(1)	& = &	1 \\
F(n)	& = &	F(n - 1) + F(n - 2) \hspace{0.5in} \text{(for $n \geq 2$)}
\eeqn

Thus, the first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, and
21.  Prove that for all $n \geq 1$, $F(n-1) \cdot F(n+1) - F(n)^2 =
(-1)^n$.

\solution{The proof is by induction on $n$.  Let $P(n)$ be the
proposition that $F(n-1) \cdot F(n+1) - F(n)^2 = (-1)^n$.

First, we must show that $P(1)$ holds.  In that case, we have:

\beqn
F(1-1) \cdot F(1+1) - F(1)^2
	& = &	0 \cdot 1 - 1^2 \\
	& = &	-1^1
\eeqn

Therefore, $P(1)$ is true.

Next, we must show for all $n \geq 1$ that $P(n+1)$ is true, assuming that $P(n)$ is
true.  We transform the left side of the equation
in proposition $P(n+1)$ into the right side as follows.

\beqn
&& F((n+1) - 1) \cdot F((n+1) + 1) - F(n+1)^2 \\
	& = &	F(n) \cdot F(n+2) - F(n+1)^2 \\
	& = &	F(n) \cdot (F(n+1) + F(n)) - F(n+1) \cdot (F(n) + F(n-1)) \\
	& = &	F(n) \cdot F(n+1) +
		F(n) \cdot F(n) -
		F(n+1) \cdot F(n) -
		F(n+1) \cdot F(n-1) \\
	& = &	F(n) \cdot F(n) -
		F(n+1) \cdot F(n-1) \\
	& = &	- (-1)^n \\
	& = &	(-1)^{n+1}
\eeqn

We begin by simplifying.  Then we use the definitions of $F(n+2)$ and
$F(n+1)$.  In the next two steps, we multiply out and cancel terms.
In the fifth step, we use the induction hypothesis.  In the last step,
rewriting the expression gives the right side of the equation in
$P(n+1)$.

Since we have proved $P(1)$ and showed that $P(n)$ implies $P(n+1)$
for all $n \geq 1$, the proposition $P(n)$ is true for all $n \geq 1$
and the claim is proved.}

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

\problem Recall that a {\em permutation} is a bijective function
mapping a finite set to itself.  Use induction to prove that there are
$n! = n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1$ different
permutations on a set of $n$ elements.

\solution
{
Let $F(S)$ be the set of permutations of $S$.

Let $P(n)$ be the predicate ``if $S$ is a $n$ element set then $|F(S)| = n!$''.
We shall prove by induction on $n$ that $P(n)$ holds for all
positive integers.

Base case: There is exactly one function from the empty set to the empty
set, it is bijective, and $0!=1$. So $P(0)$ is true.

Inductive step: Suppose that for some integer $n \geq 0$ that $P(n)$
is true.

Let $S$ be a $n+1$ element set. $S = A \cup \{e\}$ where $A$ is a
$n$ element set and $e$ is some element of $S$.

For $m \in S$, let $P_m = \{f \in F(S) : f(e) = m\}$. 
Each element of $F(S)$ is in exactly one of the sets $P_m$, so
$|F(S)| = \sum_{m \in S}|P_m|$. We shall show that there are
bijections between $F(A)$ and $P_e$, as well as between $P_m$ and
$P_e$. From this we can conclude that $|F(S)|= (n+1)|F(A)|
= (n+1)!$ which shows that $P_(n+1)$ is true. We must now simply show
that the bijections we announced exist.

Let $G : F(A) \to P_e$ such that for $i \in A$, $(G(f))(i)
= f(i)$ and $(G(f))(e) = e$. $G$ is injective because if $G(f)=G(g)$
then $\forall i \in A, f(i) = g(i)$, which means that $f = g$. $G$ is
surjective because for $f \in P_e$, we can consider $f'$, the
restriction of $f$ to $A$. $f'$ is in $F(A)$ and $G(f')=f$, so
each element in $P_e$ has a preimage in $F(A)$. Thus $G$ is a bijection.
Therefore, as announced,
we find that there is a bijection between $F(A)$ and $P_e$.

Let $t_m \in F(S)$ be the bijection that exchanges $e$ and $m$, and
leaves all other elements unchanged ($t_e$ is simply the identity function). 
Note that $t_m(t_m(i)) = i$.

Let $g_m : F(S) \to F(S)$ such that $(g_m(f))(i) = t_m(f(i))$. The range of
$g_m$ is included in $F(S)$ because $g_m(f)$ is simply $f$ composed with
$t_m$, and the composition of two permutations of a set $S$ is still a permutation of
$S$. Note that $(g_m(g_m(f)))(i) = t_m(t_m(f(i))) = f(i)$, so $g_m(g_m(f)) = f$. So
$g_m$ is a bijection, and is its own inverse.

For $f \in P_m$, $(g_m(f))(e) = t_m(f(e)) = t_m(m) = e$. So 
$g_m(P_m) \subseteq P_e$. Moreover, for $f \in P_e$, $(g_m(f))(e) =
t_m(f(e)) = t_m(e) = m$. So $g_m(P_e) \subseteq P_m$. Since
$g_m(g_m(f)) = f$, each element $f \in P_e$ is the image by $g_m$ of
$g_m(f)$, which is an element of $P_m$. Therefore, $g_m$ defines a
surjection from $P_m$ to $P_e$. Since $g_m$ is also globally
injective, $g_m$ defines a bijection between $P_m$ and $P_e$.
Therefore, the second type of bijection we had announced exists. Which
allows us to conclude that $P(n+1)$ is true.

Thus by induction on $n$ we have shown that $P(n)$ is true for all $n$.
That is, there are $n!$ permutations of a $n$ element set.

}

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

\problem Let $A$, $B$, and $C$ be finite sets, and let $f : B \to
C$ and $g : A \to B$ be functions.  Let $h$ be the function with
domain $A$ and range $C$ that maps $x \in A$ to $f(g(x))$.  Prove or
disprove the following claims:

\begin{problemparts}

\problempart If $h$ is surjective, then $f$ must be surjective.

\solution
{
True.

For all $x$ in $C$: Since $h$ is surjective, there exists $y$ in $A$ such that 
$h(y) = x$. Therefore, by definition of $h$, $f(g(y)) = x$, so $x$ is in
the image of $f$.

Therefore, all of $C$ is in the image of $f$, so $f$ is surjective.
}

\problempart If $h$ is surjective, then $g$ must be surjective.

\solution
{
False.

Suppose $A = C = \{1\}$ and $B = \{1, 2\}$. Let $f$ be such that $f(1) = f(2) = 1$, and
$g$ such that $g(1) = 1$. In this case $h$ is indeed surjective, as
$h(1) = 1$, but $g$ is not surjective as it doesn't map anything to 2.
}

\problempart If $h$ is injective, then $f$ must be injective.

\solution
{
False.

Taking the same example as in the previous case. $h$ is injective, because
only 1 maps to 1. However, $f$ is not injective as $f(1) = f(2).$
}

\problempart If $h$ is injective, then $g$ must be injective.

\solution
{
True.

For all $x$ and $y$: If $g(x) = g(y)$ then $h(x) = f(g(x)) = f(g(y)) = h(y)$ so $x = y$ because
$h$ is injective.

Therefore, $g$ is injective.
}

\end{problemparts}

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

\problem Xena the Warrior Princess and Conan the Barbarian are playing
poker.  Xena is the dealer.  Conan insists that she first deal him one
card, then one to herself, then one to him, and so forth, until they
each have five cards.  He admits that this gives him a slight edge,
since he gets the first chance to draw a good card.  But he
thoughtfully agrees to give her the first card when he is dealer.
Xena argues that Conan's ``brainless barbarian'' dealing method is
pointless.  She might as well deal five cards to him and then five
cards to herself.

Conan challenges Xena to try her ``prissy princess'' dealing method.
However, after Xena deals five cards to Conan, he asks her what her
odds are of getting a pair of aces.  She guesses maybe 1 in 20 or so.
Conan says, ``Ha!  So much for your math!  Your odds are ZERO, because
I already have three aces!  This proves my point: by dealing to me
first, you gave me first shot at the good cards!''

Prove that Xena's method of dealing is more favorable to Conan or
prove the opposite.  Your argument should make use of a bijection.

\solution{
Let the sample space $S$ be the set of sequences of 52 distinct cards. We
shall consider that each outcome is equally likely because the deck is well
shuffled.

The functions $X_C$ and $C_C$ map outcomes to the set of cards that Xena
and Conan get using Conan's method of dealing, and $X_X$ and $C_X$ do the
same for Xena's method of dealing.

Let $P$ be the permutation of elements of $S$ that maps any sequence $(c_1,
c_2, c_3, \dots)$ to $(c_1, c_3, c_5, c_7, c_9, c_2, c_4, c_6, c_8, c_{10},
c_{11}, c_{12}, c_{13}, \dots)$. $P$ is indeed a permutation of $S$ because
it can be inverted by mapping $(c_1, c_2, c_3, \dots)$ to $(c_1, c_6, c_2,
c_7, c_3, c_8, c_4, c_9, c_5, c_{10}, c_{11}, c_{12}, c_{13})$.
It is easily verified that $X_X(P(s)) = X_C(s)$ and $C_X(P(s)) = C_C(s)$.

For any set of hands $H_X$ and $H_C$, there is a subset $T$ of $S$ that
produces those hands using Conan's method of dealing. Because of the
relations we found in the preceding paragraph, Xena's method of dealing
produces $H_X$ and $H_C$ for any shuffle in $P(T)$. For any 
shuffle $s$ that give those hands with Xena's method of dealing,
$P^{-1}(s)$ must be in $T$ because of those same relations. Therefore,
$P(T)$ is exactly the set of shuffles that produce $H_X$ and $H_C$ with
Xena's method of dealing. Since $P$ is a bijection, $|P(T)|=|T|$ so there are the same
number of shuffles that produce those hands whether Xena's method or
Conan's method of dealing is used. Since shuffles are equally likely, we
conclude that the hands have the same probability with both methods.

Since this reasoning applies for any set of hands, we conclude that both
methods of shuffling are equivalent. Conan is wrong. His reasoning on the
aces is bogus because for each case where he has 3 aces, thus preventing
Xena from having two aces, there are even more cases where he has no aces
and Xena has slightly better odds of having 2 aces.

}

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

\problem Recall that a {\em tournament} is a directed graph such that
for every pair of distinct vertices $u$ and $v$, there is either an
edge from $u$ to $v$ or from $v$ to $u$, but not both.  Furthermore, no
vertex has a self-loop.

\begin{problemparts}

\problempart A {\em Hamiltonian path} is a directed path that visits
every vertex exactly once.  Prove that every tournament contains a
Hamiltonian path.

\solution{The proof is by strong induction on the number of vertices
in the tournament.  Let $P(n)$ be the predicate ``Every $n$-vertex
tournament graph contains a Hamiltonian path''.  We shall show by
induction that $P(n)$ holds for every positive integer $n$.

Base case: A tournament graph with a single vertex trivially contains
a Hamiltonian path.

Inductive step: Assume that $P(1), \ldots, P(n)$ hold, and consider an
$(n+1)$-vertex tournament graph $G$.  Let $a$ be an arbitrary vertex
of $G$.  There are three cases to consider.

First, suppose that all of $a$'s edges are outgoing.  Then let $G'$ be
the $n$-vertex tournament obtained from $G$ by removing vertex $a$ and
all edges connected to $a$.  By induction, $G'$ has a Hamiltonian
path.  Prepending $a$ to the beginning of this path gives a
Hamiltonian path in $G$.

Second, suppose that all of $a$'s edges are incoming.  Then construct
$G'$ as before.  Again, $G'$ has a Hamiltonian path by induction.
Appending $a$ to the end of this path gives a Hamiltonian path in $G$.

Finally, suppose that $a$ has some incoming edges and some outgoing
edges.  Let $G_1$ be the tournament graph on the vertices with edges
directed toward $a$, and let $G_2$ be the tournament graph on the
vertices with edges directed away from $a$.  By induction, both $G_1$
and $G_2$ have Hamiltonian path.  We can then construct a Hamiltonian
path on $G$ by taking the path in $G_1$, appending $a$, and then
appending the Hamiltonian path in $G_2$.

In all cases, $G$ contains a Hamiltonian path. Therefore $P(n+1)$ is
true.  By induction, we conclude that $P(n)$ holds for all $n \ge 1$.
Therefore every tournament graph contains a Hamiltonian path.

(If you wish to consider the empty graph as a tournament graph, the
theorem still holds; the empty path is a Hamiltonian path of the empty
graph.)  }

\problempart A {\em king} is a vertex $u$ such that for every other
vertex $v$, at least one of the following holds:

\begin{enumerate}

\item There is a directed edge from $u$ to $v$.

\item There is another vertex $x$ such that there is a directed edge
from $u$ to $x$ and a directed edge from $x$ to $v$.

\end{enumerate}

Prove that in every tournament, the verticies with the largest number of
outgoing edges must be kings.

\solution
{
We shall prove this by contradiction. Let $a$ be a node with the largest
number $k$ of outgoing edges, and let $b$ be a node that is preventing $a$ from
being a king ($a$ can't reach $b$ in two steps or less).

Since $a$ can't reach $b$ in one step, $b \to a$.

Consider any node $c$ other than $a$ and $b$ such that $a \to c$. Since $a
\nrightarrow b$, there are exactly $k$ such nodes. Because $a$ can't reach
$b$ in two steps, we must have $c \nrightarrow b$, that is $b \to c$.

Thus $b$ has $k$ outgoing edges to the nodes that $a$ has outgoing edges
to, and in addition, $b$ has an extra outgoing edge to $a$. So $b$ has at
least $k+1$ outgoing edges, which violates the definition of $a$ as a
node with the most outgoing edges. 

We must conclude that $b$ does not exist, therefore, $a$ can reach any node
in at most two steps. Therefore, $a$ is a king.
}

\end{problemparts}

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

\end{problems}

\comment{

Original solution to the Hamiltonian path problem.  Uses the
well-ordering principle in the inductive step!

 and let $G'$ be the subgraph of
$G$ that is obtained by removing $a$ and any edges connected to
$a$. $G'$ is a $n$ node graph because it has one fewer nodes than
$G$. $G'$ is a tournament graph because between any pair of nodes,
there is exactly one directed edge (the one that was present in
$G$). Because of the induction hypothesis, there is a Hamiltonian path
$(b_1, \dots, b_n)$ in $G'$.

If $a \to b_1$, then $(a, b_1, \dots, b_n)$ is a
Hamiltonian path for $G$. Similarly, if $a \nrightarrow b_n$ then $b_n \to a$, so  
$(b_1, \dots, b_n, a)$ is a Hamiltonian path for $G$.

Otherwise, $a \nrightarrow b_1$ and $a \to b_n$. 
Let $S = \{k \in \{1, \dots, n\} : a \to b_k\}$. $b_n \in S$, so $S$ is not
empty. By the well ordering principle, there exists $k_0 \in S$ such that
$\forall k \in S, k_0 \le k$. Since $a \nrightarrow b_1$, $1 \notin S$. Thus
$k_0 > 1$. $a \nrightarrow b_{k_0 - 1}$ because otherwise $k_0-1$ would be in
$S$, violating the definition of $k_0$. Consequently, $b_{k_0 - 1} \to a$.
Also, since $k_0 \in S$, $a \to b_{k_0}$. Therefore, $\{b_1, \dots, b_{k_0
- 1}, a, b_{k_0}, \dots, b_n\}$ is a Hamiltonian path of $G$.

In all cases we have shown that $G$ contains a Hamiltonian path. Therefore
$P(n+1)$ is true.

By induction on $n$ we conclude that $P(n)$ holds for all $n \ge 1$.
Therefore all tournament graphs contain a Hamiltonian path (if you wish to
consider the empty graph as a tournament graph the theorem still holds, as
the empty path is a Hamiltonian path of the empty graph).
}

\end{document}
