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

%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%\hidesolutions
%\showsolutions

\newcommand{\shorter}{\vspace{-0.3cm}}

\renewcommand{\reading}{Course Notes, Week 8 and Rosen sections 4.1,
4.2, and 4.3.  Stop where the part about combinations begins.}

\begin{document}

\problemset{7}

\graphicspath{{/toc/a/class/6.042/fall02/problemrepository/figures/}}

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

\begin{problem}
Suppose that $a \equiv b \pmod{n}$ and $n > 0$.  Prove or disprove the
following assertions:

\bparts

\ppart $a^c \equiv b^c \pmod{n}$ where $c \geq 0$

\solution{The proof is by induction on $c$ with the hypothesis that
$a^c \equiv b^c \pmod{n}$.  If $c = 0$, then the claim holds, because
$1 \equiv 1 \pmod{n}$.  Now suppose that:

\begin{eqnarray*}
a^c & \equiv & b^c \pmod{n}
\end{eqnarray*}

Multiplying both sides by $a$ gives:

\begin{eqnarray*}
a^{c+1} & \equiv & a b^c \pmod{n}
\end{eqnarray*}

Since $a \equiv b \pmod{n}$, we can replaced the $a$ on the right side
by $b$:

\begin{eqnarray*}
a^{c+1} & \equiv & b^{c+1} \pmod{n}
\end{eqnarray*}

Therefore, the claim holds by induction.
}

\ppart $c^a \equiv c^b \pmod{n}$ where $a, b, \geq 0$

\solution{The claim is false.  For example:

\begin{eqnarray}
2^0 \not\equiv 2^3 \pmod{3}
\end{eqnarray}
}

\eparts

\end{problem}

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

\begin{problem} Suppose that $p$ is a prime and $k$ is not a multiple of $p$.
Then we have seen that $k$ has a unique multiplicative inverse $k^{-1}
\in \set{1, 2, \ldots, p-1}$ such that $k^{-1} \cdot k \equiv 1
\pmod{p}$.

\bparts

\ppart A integer $k$ is {\em self-inverse} if $k = k^{-1}$.  Prove
that $k$ is self-inverse iff either $k = 1$ or $k = p - 1$.

\solution{
To prove this, we consider all $k$ between 1 and $p-1$ such that:
\[
k \cdot k  \equiv  1 \pmod{p}.
\]
This is equivalent to the assertion that $p \divides k^2 - 1$.  But $k^2-1
= (k-1)(k+1)$, and since $p$ is a prime, we conclude that either $p
\divides k-1$ or $p \divides k+1$.  But $1 \le k < p$, so $p \divides k-1$
iff $k-1=0$, and $p \divides k+1$ iff $k+1 = p$, so we must have $k = 1$
or $k = p - 1$.

Conversely, $1 \cdot 1 \equiv 1 \pmod{p}$ and $(p-1)\cdot (p-1) = p^2+2p+1
\equiv 1 \pmod{p}$.
}

\ppart Prove the following theorem.

\begin{theorem}[Wilson's Theorem]
If $p$ is a prime, then

\begin{eqnarray*}
(p - 1)! & \equiv & -1 \pmod{p}
\end{eqnarray*}

\end{theorem}

The English mathematician Edward Waring said that this theorem would
probably be very difficult to prove because there was no adequate
notation for primes.  Gauss proved it while standing.  He suggested
that Waring failed for lack of notions, not notations.  Stand up and
try pairing each term in $(p-1)!$ with its multiplicative inverse.

\solution{If $p = 2$, then the theorem holds, because $1 \equiv -1
\pmod{2}$.  If $p > 2$, then $p - 1$ and $1$ are distinct terms in the
product $1 \cdot 2 \cdot \cdots (p - 1)$, and these are the only
self-inverses.  Consequently, we can pair each of the remaining terms
with its multiplicative inverse.  Since the product of a number and
its inverse is congruent to 1, all of these remaining terms cancel.
Therefore, we have:

\begin{eqnarray*}
(p-1)!
	& \equiv & 1 \cdot (p - 1) \pmod{p} \\
	& \equiv & -1 \pmod{p}
\end{eqnarray*}
}

\eparts

\end{problem}

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

\begin{problem} Two straight, nonparallel lines in the real plane intersect
at a point.  Algebraically, this means that the equations:

\begin{eqnarray*}
y & = & m_1 x + b_1 \\
y & = & m_2 x + b_2
\end{eqnarray*}

\noindent have a unique solution $(x, y)$, provided $m_1 \neq m_2$.  A
similar statement holds over the integers, if we work modulo a prime.
The problem parts below lead up to this conclusion.  Throughout,
assume that $p$ is a prime.

\bparts

\ppart As a warmup, solve the equations above for $x$ and $y$ over the
real numbers, assuming that $m_1 \neq m_2$.

\solution{
Subtracting the second equation from the first, we have

\begin{eqnarray*}
0 & = & m_1 x + b_1 - (m_2 x + b_2) \\
(m_1 - m_2) x & = & b_2 - b_1 \\
x &= & \frac{b_2 - b_1}{m_1 - m_2}
\end{eqnarray*}

Substituting this value of $x$ into the first equation, we have

\begin{eqnarray*}
y & = & m_1 \cdot \frac{b_2 - b_1}{m_1 - m_2} + b_1
\end{eqnarray*}
}

\ppart Congruences are the analogue to equations.  Let's start by
solving a congruence in a single variable:

\begin{eqnarray*}
a x & \equiv & b \pmod{p}
\end{eqnarray*}

Solve for $x$, assuming that $a \not\equiv 0 \pmod{p}$.  Your answer
should be of the form $x \equiv\ ? \pmod{p}$, where ? is some
expression involving $a$ and $b$.

\solution{
Multiplying both sides by $a^{-1}$ gives $x \equiv b a^{-1} \pmod{p}$.
}

\ppart Now suppose that we have two linear congruences:

\begin{eqnarray*}
y & \equiv & m_1 x + b_1 \pmod{p} \\
y & \equiv & m_2 x + b_2 \pmod{p}
\end{eqnarray*}

Solve for $x$ and $y$, assuming that $m_1 \not\equiv m_2 \pmod{p}$.
Your answer should be of the form $x \equiv\ ? \pmod{p}, y \equiv\ ?
\pmod{p}$, where the ?'s denote expressions involving $m_1$, $m_2$,
$b_1$, and $b_2$.

\solution{
Subtracting the second congruence from the first, we have:

\begin{eqnarray*}
0 & \equiv & m_1 x+b_1 - (m_2 x + b_2)  \pmod{p} \\
(m_1 - m_2)x & \equiv & b_2 - b_1 \pmod{p} \\
x & \equiv & (m_1 - m_2)^{-1} \cdot (b_2 - b_1) \pmod{p}
\end{eqnarray*}

Substituting this value of $x$ into the first congruence, we have

\begin{eqnarray*}
y & \equiv & m_1 \cdot (m_1 - m_2)^{-1} \cdot (b_2 - b_1) + b_1 \pmod{p}
\end{eqnarray*}
}

\eparts

\end{problem}

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

\begin{problem} Solve the following counting problems.

\bparts

\ppart A committee is formed containing either the governor or one of
the two senators of each of the 50 states.  How many ways are there to
form this committee?

\solution{$3^{50}$.  For each of 50 states, we have 3 choices for the 
representative from that state.  Three choices for 50 states means multiplying
3 by itself 50 times.}

\ppart Karen Kohl, a 6.042 TA, is about to run a race.  If there are
100 people in the race, how many different ``top 5 finishers'' lists
are possible?

\solution{$100! / (100 - 5)!$.  This is an {\em r-permutation} problem
where we have $n=100$ elements in the set and we need to find the number of
ordered arrangements of $r=5$ elements, $P(100,5)$.}

\ppart If Karen is certain to finish in the top 3, then how many
different ``top 5 finishers'' lists are possible?

\solution{
\[
\frac{3 \cdot 99!}{(99 - 4)!}
\]
We know that Karen will be one of the top 5 finishers so we need to
find the number of ways to arrange the other 4 top 5 finishers.
This is just the number of 4-permutations of a set of 99 elements
since we have removed Karen from the list of 100 runners, $P(99,4)$.
For each of these 4-permutations, Karen can finish in any of 3 ways
(first, second, or third place).

}

\ppart A {\em palindrome} is a integer whose revsersal is equal to
itself.  For example, 1771 and 12321 are palindromes.  How many of the
numbers in $\{1, 2, \ldots, 1000000\}$ are palindromes?

\solution{
There are several cases to consider.

\begin{itemize}

\item All 9 of the one-digit numbers are palindromes.

\item There are 9 two-digits palindromes, since the first digit
determines the whole number.  For example, if the first digit of a
two-digit palindrome is 7, then the number must be 77.

\item There are $9 \cdot 10$ three digit palindromes, since the first
two digits determine the whole number.  For example, if the first two
digits are 92, then the palindrome must be 929.

\item Similarly, there are $9 \cdot 10$ four-digit palindromes, $9
\cdot 10 \cdot 10$ five-digits palindromes, and $9 \cdot 10 \cdot 10$
six-digit palindromes.

\end{itemize}

By the Sum Rule, the number of palindromes is:

\begin{eqnarray*}
9 + 9 + 9 \cdot 10 + 9 \cdot 10 + 9 \cdot 10 \cdot 10 + 9 \cdot 10 \cdot 10
	& = &	1998
\end{eqnarray*}
}

\ppart In how many ways can $n$ couples be seated around a circular
table, if the two people in each couple must be seated next to each
other?  (Note that circular order matters here: 1234 is the same as
3412.)

\solution{$(n-1)! \cdot 2^n$.  First we will arrange the $n$ couples around 
the table.  There are $n!/n=(n-1)!$ ways to do this.  We have $n!$ ways to 
arrange $n$ couples in general, but we want to divide by $n$ since there are
$n$ different ``first positions'' for each of these arrangements 
and we do not want to count these as different.  Finally, we must determine
the order of the people within the couples.  We have 2 ways of ordering each
couple, and $n$ couples, so for each of the couple arrangements above, 
we have $2^n$ ways of ordering the members of the couples, giving us a total
of $(n-1)! \cdot 2^n$ ways to arrange people so that the two people in each
couple must sit next to each other.}

\ppart How many permutations of the string 0123456789 contain 6042 as
a substring?

\solution{Regard 6042 as a single symbol.  Then the permutations of
the string 0123456789 containing 6042 are in bijection with the
permutations of the set:

\[
\{ 1, 3, 5, 7, 8, 9, 6042 \}
\]

Since this set has 7 elements, there are $7!$ permutations.
}

\eparts

\end{problem}

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

\begin{problem}
Use the pigeonhole principle to prove that every simple graph has two
vertices of the same degree.
\end{problem}

\solution{
If G is a graph with $n$ vertices, the possible degrees of its
vertices are $0,1,...,n-1$.  If the graph contains a vertex of degree
$n-1$, it is connected to all other vertices, meaning that a vertex of
degree $0$ cannot exist.  So there are $n-1$ possible values for the
degrees.  If the graph does not have a vertex of degree $n-1$, there
are $n-1$ possible values for the degrees.  In either case, we have
$n$ vertices and $n-1$ possible degree values.  By the Pigeonhole
Principle, two of the vertices must have the same degree.
}

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

\begin{problem}
Min Wu, noted 6.042 TA, has written two remarkable computer programs:

\begin{description}

\item[WuCompress] takes a 5-megabyte file as input and outputs a
1-megabyte file.

\item[WuExpand] takes a 1-megabyte file as input and outputs a
5-megabyte file.

\end{description}

Min claims that for every 5-megabyte file $X$:

\begin{eqnarray*}
\textbf{WuExpand}(\textbf{WuCompress}(X)) & = & X
\end{eqnarray*}

(Using these two programs, Min plans to compress his massive
collection of illegal MP3s down to $1/5$ the size and then expand a
song whenever he wants to listen to it.)  Use the pigeonhole principle
to prove that Min's claim is false.

If you follow news in the computing world, you'll hear claims about a
fantastic new ``breakthrough'' in data compression--- much like
Min's--- every year or so.

\solution{Let $N = 8 \cdot 2^{20}$, the number of bits in a megabyte.
WuCompress maps a file with $5N$ bits to a file with only $N$ bits.
Thus, WuCompress is a function mapping the set of $2^{5N}$ possible
input files to the set of $2^{N}$ possible output files.  By the
pigeonhole principle, there must be two distinct inputs files $X_1$
and $X_2$ such that:

\begin{eqnarray*}
\textbf{WuCompress}(X_1) & = & \textbf{WuCompress}(X_2)
\end{eqnarray*}

Therefore, we must have:

\begin{eqnarray*}
\textbf{WuExpand}(\textbf{WuCompress}(X_1))
	& = & \textbf{WuExpand}(\textbf{WuCompress}(X_2))
\end{eqnarray*}

Since $X_1 \neq X_2$, it can not be that the left side is equal to
$X_1$ and the right side is equal to $X_2$.  Therefore, Min's claim is
false for either $X_1$, $X_2$, or both.
}
\end{problem}

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

\end{document}                            
