\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}
\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\newcommand{\funcs}[2]{[#1 \to #2]}
\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\BN}{\funcs{\naturals}{\set{0,1}}}
\def\onetwo{}
\begin{document}

\tutprobn{6}{9/30/99}{September 30,  1999}

\begin{problems}

\problem

\bparts

\ppart

In lecture we demonstrated how to ``guess'' the fifth card in a poker hand
when a collaborator reveals the other four cards.  Describe a method for
guessing two hidden cards in a hand of nine cards, when your collaborator
reveals the other seven cards.

\solution{There must be $\ceil{9/4} = 3$ cards with the same suit, so our
collaborator chooses to hide two of them and then use the third one as the
first card to be revealed.  So this first revealed card fixes the suit of
the two hidden cards; it will also be used as the origin for the offset
position of the first hidden card.  This first hidden card will in turn be
used as the origin for the offset of the other hidden card.  There are six
cards to code the two offset positions.  These suffice to code two offsets
of size from one to six.  That is, our collaborator can choose one of the
$3! = 6$ orders in which to reveal the first three cards and thereby tell
us the offset position of the first hidden card.  Our collaborator can
then choose the order of the final three cards to describe the offset
position of the second hidden card from the first.  Note that the first
revealed card must be chosen so that both offsets are less $\leq 6$; since
the sum of the offsets between successive cars ordered in a cycle from Ace
to King is 13, it is not possible for more than one offset between
successive cards to exceed seven, so this is always possible.}

\ppart Show that there is no procedure for ``guessing'' a hidden card
among four when your collaborator reveals three. \hint Compare the number
of hands to the number of revealed three-card sequences.
~
\solution{
There are $\binom{52}{4}$ possible four-card hands.  There are $P(52,3)$
three-card sequences that can ever be revealed.  Since
\[
\frac{\binom{52}{4}}{P(52,3)}=
\frac{52\cdot 51\cdot 50 \cdot 49/4!}{52 \cdot 51 \cdot 50} = 49/24 > 1,
\]
there must, by pigeonholing, be two (actually three) hands for which the
collaborator reveals the same three cards.  Therefore the magician cannot
determine the hidden card, since these hands must have different hidden
cards.}

\eparts

\subsection{Chessboard numbering}
Consider the following problem: we are to number the squares of a
chessboard from 1 to 64.  Is it possible to do this so that the difference
between the numbers of any pair of adjacent squares (horizontally,
vertically or diagonally) is no more than 8 ?

The answer is NO.  Consider the square numbered 1 and the square numbered
64. We know that no matter where they are placed, there is a path of
length at most 7 between them (i.e., in at most 7 hops to adjacent
squares, we can go from the 1-square to the 64-square).  To go from 1 to
64, there is a difference of 63 to be covered in 7 hops.  Let us think of
this difference as 63 pigeons and they have to each be placed in one of 7
holes.  The holes represent which hop the step is taken in.  Now by the
strong PP there must be a hole with at least 63/7 = 9 pigeons.  This means
that there must be a hop which covers a difference of 9 or greater.  That
is there are a pair of adjacent squares that differ by at least 9.


\problem

In a city with more then one road, prove that there must be at least two
roads which are crossed by the same number of other roads.

\solution{
A straightforward application of the pigeonhole principle.  Say that there
are $n$ roads in this city.  Since no road can cross itself, the number of
roads which cross any given road must be an integer from $0$ to $n-1$.  If
no two roads had the same number of crossings, then every one of these $n$
numbers from $0$ to $n-1$ must equal the number of times some road is
crossed.  But that would mean that some road crosses $0$, i.e. no roads,
while some road crosses $n-1$, i.e. all the other roads.  This is a
contradiction.
}


\problem

We observe that an integer strictly between 1 and n is prime if and only if either
\begin{enumerate}
\item\label{a} it is a prime less than $\sqrt{n}$, or
\item\label{b} no prime less than $\sqrt{n}$ divides it.

\end{enumerate}

\bparts

\ppart Explain why is the above observation true.

\solution{
Let $m$ be the integer strictly between 1 and $n$.

If Condition~\ref{a} holds then $m$ is a prime, trivially.

Condition~\ref{b} also implies that $m$ is prime.  To prove this, suppose
$m$ is not prime; then it must be the product of two natural numbers $>
1$.  Since their product equals $m < n$, both factors can't be $\geq
\sqrt{n}$.  Whichever of the factors is $< \sqrt{n}$ must also have a
prime divisor (possibly itself) which is $< \sqrt{n}$, and this small
prime is a divisor of $m$, contradicting Condition~\ref{b}.

Conversely, if $m$ is prime, Condition~\ref{a} immediately holds when $m <
\sqrt{n}$ and Condition~\ref{b} immediately holds otherwise.}

\ppart Use the observation above along with the Inclusion-Exclusion
Principle to compute the number of primes less than $n=25$.  (You may know
other methods that will answer this question faster, but if we replaced 25
by 1,000,000, this method would win.)

\solution{
Consider the following sets:
\begin{eqnarray*}
S_0 & ::= & \set{\mbox{primes less than } \sqrt{25}} = \set{2,3},\\
S_1 & ::= & \set{\mbox{even numbers strictly between 1 and 25}},\\
S_2 & ::= & \set{\mbox{numbers divisible by 3 strictly between 1 and 25}}.
\end{eqnarray*}
There are $24/2 = 12$ numbers in $S_1$, $24/3 = 8$ numbers
in $S_2$, and $24/(2 \cdot 3) = 4$ numbers in $S_1 \cap S_2$.
Now, by Inclusion-Exclusion, the number of integers strictly between 1 and
25 which are divisible by either 2 \emph{or} 3 is
\[
\card{S_1 \cup S_2} = \card{S_1} + \card{S_2} - \card{S_1\cap S_2} = 12
+ 8 - 4 = 16.
\]

So, the number of integers strictly between 1 and 25 which are divisible
by neither 2 nor 3 is $23-16=7$.  Finally, according to the observation
above, the total number of primes less than 25 is:
\[
\card{S_0} + \mbox{those not divisible by 2 or 3} = 2 + 7 = 9.
\]
}
\eparts



\problem 
Let $n$ be a positive integer.

\bparts

\ppart Show that any subset of $\onetwo{2n}$ with $n+1$ elements
contains two numbers that sum to $2n+1$.  

\solution{
Combine the elements of $\onetwo{2n}$ in pairs as follows
\[\mbox{holes}::= \set{(1,2n), (2,2n-1),..., (n,n+1)}.
\]
Note that every number in $\onetwo{2n}$ appears in exactly one hole, and the
sum of the numbers in each of the $n$ holes is $2n+1$.  Now consider any
subset, $\mbox{pigeons} \subseteq \onetwo{2n}$ of size at least $n+1$.
Assign each pigeon to the hole in which it appears.  Since there are more
pigeons than holes, at least two pigeons $i,j$ with $i < j$ must share a
hole.  That is, $(i,j)$ is a hole, so $i$ and $j$ are two pigeons whose
sum is $2n+1$.}

\ppart Show that any subset of $\onetwo{4n}$ with $3n+1$ elements
contains four numbers that sum to $8n+2$.  

\solution{
As in the solution of the previous part, combine the elements of
$\onetwo{4n}$ in pairs as follows:
\[
\mbox{holes}::= \set{(1,4n), (2,4n-1,),..., (2n,2n+1)}.
\]
Note that every number in $\onetwo{4n}$ appears in exactly one hole, and the
sum of the numbers in each of the $2n$ holes is $4n+1$.  Now consider any
subset, $\mbox{pigeons} \subseteq \onetwo{4n}$ of size at least $3n+1$.
Assign each pigeon to the hole in which it appears.  Since there are $n+1$ more
pigeons than holes, and at most two pigeons appear in any hole, there must
be $n+1 \geq 2$ holes fully occupied by two pigeons.  Take the four
elements in two of the fully occupied holes.  Since the sum of the two in
each hole is $4n+1$, the sum of the four is $8n+2$.}

\ppart State and prove a general theorem along these lines.

\solution{
We will prove the following:
\begin{theorem*}
For all positive integers $n,k$, every subset of $\onetwo{2kn}$ with
$kn+k$ elements contains $2k$ numbers that sum to $2k^2n+k$.
\end{theorem*}

The results of the two previous parts of this problem are special cases of
this theorem for $k=1,2$.  In fact, for $k=2$, the theorem actually gives
a better bound: $2n+2$ rather than $3n+1$.

\pf
As in the solution of the previous part, combine the elements of
$\onetwo{2kn}$ in pairs as follows:
\[
\mbox{holes}::= \set{(1,2kn), (2,2kn-1,),..., (kn,kn+1)}.
\]
Note that every number in $\onetwo{2kn}$ appears in exactly one hole, and the
sum of the numbers in each of the $kn$ holes is $2kn+1$.  Now consider any
subset, $\mbox{pigeons} \subseteq \onetwo{2kn}$ of size at least $kn+k$.
Assign each pigeon to the hole in which it appears.  Since there are $k$ more
pigeons than holes, and at most two pigeons appear in any hole, there must
be $k$ holes fully occupied by two pigeons.  Take the $2k$
elements in $k$ of the fully occupied holes.  Since the sum of the two in
each hole is $2kn+1$, the sum of the $k$ is $k(2nk+1)$.
\end{proof}
}

\eparts

\problem 

Let $\{0,1\}^n$ be the set of all bit strings of length $n$.

\bparts

\ppart

How many functions are there with domain $\{0,1\}^m$ and codomain
$\{0,1\}^n$?


\solution{

There are $2^m$ elements in the domain.  There are $2^n$
elements in the codomain.  For every element in the domain, we thus have
$2^n$ choices for what we can map it to.  Therefore, by the product rule,
there are $(2^n)^{2^m}$ possible functions with domain $\{0,1\}^m$ and
codomain $\{0,1\}^n$.}

\ppart

A value $x$ is called a {\em fixed point} of a function $f$ if $f(x) = x$.
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em no} fixed
points?

\solution{
We have $2^n$ elements in the domain, and each of them can
possibly be mapped to $2^n - 1$ elements in the codomain---to any element
but itself.  Therefore, there are $(2^n-1)^{2^n}$ such functions with no
fixed points.}

\ppart 
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em at least one} 
fixed point?

\solution{
There are $(2^n)^{2^n}$ functions, and $(2^n-1)^{2^n}$ have no
fixed points.  Therefore, the remaining $(2^n)^{2^n} - (2^n-1)^{2^n}$ have
at least one fixed point.}

\ppart
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em exactly one} 
fixed point?

\solution{
Let's fix a particular point for our fixed point.  Now let's
consider where the remaining $2^n - 1$ points can be mapped.  Each one can
be mapped to any spot but itself---thus it can be mapped to exactly $2^n
- 1$ possible spots.  So there are $(2^n - 1)^{2^n - 1}$ functions with
exactly this particular fixed point and no other.  Now there are $2^n$
possible choices for the particular fixed point, so the total number of
functions with exactly one fixed point is $2^n(2^n - 1)^{2^n - 1}$.}

\eparts

\end{problems}

\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
