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

\askaboutsolutions

\begin{document}

\ifshowsolutions
  \psetsol{8}{October 31, 2001}{\stamp}
\else
  \pset{8}{October 22, 2001}{Monday 10/29, beginning of lecture}{\stamp}
  \collaborationnote
\fi

\reading \href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l8.pdf}
{Week 8 Notes}.  Rosen \S 4.1-2, \S 4.3 pp.250-1, \S5.5, \S 5.6 to
bottom of p.363.

\begin{problems}

\problem {\bf Towers of Hanoi} 

The Towers of Hanoi game involves stacking $32$ disks onto three vertical
pegs, \cf Rosen \S 5.1, Example 5.  Each disk has a hole in the middle
through which a peg can slide, and all the disks have different diameters.
An arrangement of the disks on the pegs is allowed only if no disk rests
on a smaller disk.  How many different such arrangements are allowed?
  
\solnospace{There are $3^{32}$ different configurations by the product
rule: 3 choices of peg for the largest disk, 3 choices for the second
largest disk, and so on.}

\problem {\bf In a Bostonian field of dreams...}

In some imaginary world, the Boston Red Sox are playing the New York Yankees
for the World Series Championship title.  In fact, they've already won the first
game of the series, and there is great enthusiasm in Beantown at the prospect
of winning the whole thing.  People in the sports bars talk excitedly about 
the different ways Boston could win (will they sweep it?  will they lose the 
second game but come back and take the next three? ...), but they are all a 
little too inebriated
to figure out all the possibilities.  Wielding your tree diagram method and
your smart MIT brainpower, 
calculate for them
the many many different ways the Red Sox could actually take home the title!  
(For those
of you unfamiliar with baseball, the World Series is a best of seven tournament, 
i.e. the first team to win four games wins the title.)

\solnospace{The required
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/figures/tree-psol8.jpg}{tree
diagram} is attached.

Alternatively, one can
count the number of ways the Red Sox could win using the combinatorics we have
covered since last week.  We need to choose three games out of six remaining for
the Red Sox to win.  After each third game is played in which the Red Sox win, 
the series is considered over.  Thus, there are $C(6,3) = 20$ possibilities.
}


\problem 

\bparts
\ppart Rosen \S 4.2, Exercise 10.

\solnospace{The midpoint of the segment whose endpoints are $(a,b)$ and
$(c,d)$ is $\left(\cfrac{a+c}{2},\cfrac{b+d}{2}\right)$.  Clearly the
coordinates of these fractions will be integers as well if and only if
$a$ and $c$ share parity (both odd or even) and $b$ and $d$ also share
parity.  Thus, there are four possible pairs of parities: (odd,odd),
(odd,even), (even,odd), (even,even).  Since we are given five points,
the pigeonhole principle guarantees that at least two of them will
have the same pair of parities; therefore, the midpoint of the line
segment joining those two points will have integral coordinates.}

\ppart Rosen \S 4.2, Exercise 30.

\solnospace{At a party with $n$ people, there are $n$ possibilities
for the number of ``other people'' a person can know ($0$ through
$n-1$), so we cannot apply the pigeonhole principle directly; however,
note that there cannot exist a party in which some person (say, Lars)
knows no one and another (say, Kirk) knows all $n-1$ other people,
because ``know'' is a symmetric relation: if Kirk knows Lars, then
Lars knows Kirk, contradicting the assumption that Lars knows no one.
Thus, there are in reality only $n-1$ possiblities, whereupon we can
apply the pigeonhole principle.}

\eparts

%%Bijection mapping

\problem {\bf The Pig Walk}

Suppose that Theory Pig wants to take a walk on his neighborhood grid to location
$(n, n)$.  He starts at position $(0, 0)$.  At any
time, he can step North (incrementing the first coordinate) or step East
(incrementing the second coordinate).  In this problem, we'll use the Division
Rule to count how many different ways he can reach position $(n, n)$, for
$n \in \nats$.

\begin{problemparts}

\problempart Let's take a mapping that maps a length $2n$ sequence, $p$, 
of the integers $1, 2,
\ldots, 2n$, into a sequence, $p'$, in which odd numbers remain in the same
positions and even numbers remain in the same positions, but the odd and
even numbers are each sorted into increasing order.  This map is $k$ to
one for what $k$?  Explain.

\solnospace{$k=n!^2$.  Let's look at the even numbers in $p'$ first.  
How many different
ways can we re-order them so as to get strings $p$?  
Take the first even number and consider the
locations we can put it in.  There are $n$ choices, corresponding to the locations
where even numbers occur in string $p'$.  The next even number in $p'$ has $n-1$
choices, etc... so we have $n \times n-1 \times \cdots \times 1 = n!$ possible
re-orderings.  Similarly, there are $n!$ re-orderings for the odd numbers, and so
we have a total of $n!^2$ re-orderings for both the odd and even numbers together,
by the Product Rule.  Since each re-ordering corresponds to a $p$ that maps to
the same $p'$, the given map must be a $n!^2$ to 1 mapping. 
}

\ppart How many different ways are there to list the numbers $1, 2,
\ldots, 2n$ such that the even numbers appear in increasing order and the
odd numbers appear in decreasing order?

\solnospace{There are $(2n)!$ ways to list the numbers $1, 2, \ldots, n$.
Mapping any such list, $p$, into, $p'$, defines a $n!^2$-to-1 mapping that
takes an arbitrary listing to a listing in which the odd and even numbers
are sorted in increasing order.  Thus, by the Division Rule, there are
$(2n)!/n!^2$ listings in which the odd and even numbers appear in
increasing order.}

\problempart Explain why the number of paths Theory Pig can follow is the
same as the answer to part~(b).

\solnospace{Each time Theory Pig takes a step North, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step East, write down an odd number, starting with $2n-1$ and working down.

Note that if we use binomial coefficients, to be introduced next week,
then the solution is easy: Theory Pig must take $2n$ steps in total.  Of
these, he must choose a subset of $n$ to be North steps.  This gives
$\binom{2n}{n}$ different ways to reach $(n, n)$.}

\end{problemparts}


\problem {\bf The Pig Principle}

Having reached $(n,n)$ successfully but having been pooped on by a pigeon
along the way, Theory Pig now has a new beef.  He complains that the name
``Pigeonhole Principle'' is verbose and awkward and proposes the following
``Pig Principle'' that he finds much more relevant to his life:

Suppose that $m$ pigs are lined up, and each pig is given some number of
tasty treats.  Theory Pig asserts that there is always a sequence of one
or more consecutive pigs in the lineup who receive a total number of
treats which is a multiple of $m$.

For example, suppose there are $m = 5$ pigs, and that they
receive 1, 6, 2, 12, and 7 treats respectively.  Then the claim holds
in this case, because the second, third, and fourth pigs received $6 +
2 + 12 = 20$ treats altogether, and 20 is a multiple of 5.

Prove that Theory Pig's Pig Principle is correct.  In the process, you may
have to use the Pigeonhole Principle one last time.  \iffalse (Optionally,
you may want to think about whether the two principles are actually
equivalent, or whether Theory Pig has just proposed a weaker principle to
replace the Pigeonhole Principle.)\fi

\solnospace{Let $t_i$ be the total number of treats given out to the first
$i$ pigs in the lineup.  There are two cases.

In the first case, suppose that at least one of $t_1, t_2, \ldots, t_m$ is
congruent to 0 modulo $m$.  In particular, suppose that $t_j$ is congruent
to 0 modulo $m$.  This implies that the number of treats received by the
first $j$ pigs is a multiple of $m$, and so the claim holds.

In the second case, suppose that none of $t_1, t_2, \ldots, t_m$ is
congruent to 0 modulo $m$.  Then each of the $m$ terms $t_1, t_2, \ldots,
t_m$ is congruent to one of the $m-1$ values $1, 2, \ldots, m-1$ modulo
$m$.  By the Pigeonhole Principle, there are at least two terms $t_j$ and $t_k$
that are congruent to the same value modulo $m$.  Thus pigs $j+1, j+2,
\ldots, k$ received a total of $t_k - t_j$ treats, which is a multiple of
$m$.}


%%  Inclusion-Exclusion, s98 : ps7, prob 3; Spring '01, Tutorial 8

\problem {\bf Square-Free}

A positive integer is called {\em square-free} if it is not
divisible by the square of any positive integer greater than 1.  For
example $35 = 5 \cdot 7$ is square-free but $18 = 2 \cdot 3^2$ is
not.  $1$ is square-free.  Use inclusion-exclusion to find the
number of square-free positive integers strictly less than 151.

\solnospace{We use Inclusion-Exclusion as was done for
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l8.pdf}{rule}{count-primes}{counting
prime numbers} in Notes and Rosen.  So we compute the number of positive
integers less than 150 that are \emph{not} square-free.

Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) be the set of
multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$) less than
150.  The union of these sets is the set of all numbers less than 150
which are not square-free, \ie have some square divisor in them.
The reader should take a moment to think through why this assertion
is true (why only primes? why stop at 11?).

The cardinality of this set can be computed by the Inclusion-Exclusion
Principle.  Since $2^2 7^2 > 150$ and $3^25^2 > 150$, it follows that $A_i
\intersect A_j = \emptyset$ unless $\set{i,j}=\set{2,3}$ or $\set{2,5}$,
so

\begin {eqnarray*}
\card{A_2 \cup A_3 \cup A_5 \cup A_7} & = &
|A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
- |A_2 \cap A_3 | - |A_2 \cap A_5|\\
& = & \lfloor 150/2^2 \rfloor +  \lfloor 150/3^2 \rfloor + \lfloor 150/5^2 \rfloor
+ \lfloor 150/7^2 \rfloor + \lfloor 150/11^2 \rfloor\\
& &  - \lfloor 150/2^23^2 \rfloor
- \lfloor 150/2^25^2 \rfloor\\
& = & 37 + 16 + 6 + 3 + 1 - 4 - 1\\
& = & 58
\end {eqnarray*}
Therefore, the number of square-free positive integers less than
150 is
\[
150 - 58 = 92.
\]
}

\iffalse
% Fall 00, pset 8  from Tina
% product rule
\problem

How many bit strings of length 10 contain either five consecutive $0$'s
or five consecutive $1$'s?

\solnospace{There are $2^{10}$ bit strings of length 10. First, let's see
how many of those contain five consecutive $0$'s. The sequence of the 5
$0$'s can start at position $1,2,3,4,5$ or $6$. In each case, the
remaining $5$ bits are allowed to be anything, so, as a ``first
approximation'', we can say that there are $6*2^5$ different strings of
consecutive $0$'s. \par However, if we do this, we are \emph{overcounting}
since, for example, the string that has its first $8$ bits equal to $0$
and the last $2$ equal to $1$ (that is, $0000000011$) will be counted as a
valid string \emph{four times} by our method: \underline{00000}00011,
0\underline{00000}0011, 00\underline{00000}011 and
000\underline{00000}11. We need to eliminate these duplicates, which occur
whenever we are dealing with string s that have more than 5 consecutive
$0$'s. \par

We can do this by calculating the number of strings with $6$ or more
consecutive $0$'s using the same method as above. This will give us
$5*2^4$ such strings, and for each sequence of $0$'s, we will be
overcounting exactly one time less than we overcounted above: for example,
going back to the string of $8$ consecutive $0$'s that was counted 4 times
above, we see that this method will count it exactly $3$ times
\underline{000000}0011, 0\underline{000000}011, 00\underline{000000}11.
The same will hold for all strings of length $\geq 6$ because the number
of allowed starting positions for a sequence of $6$ $0$'s is exactly one
less than the number of allowed starting positions for a sequence of $5$
consecutive $0$'s. Thus, it suffices to subtract this number from the
number we got before to get rid of duplicates. Therefore, the number of
strings containing 5 or more consecutive $0$'s is
\[
6*2^5-5*2^4=112
\]
By symmetry, there are another 112 strings which contain five consecutive
$1$'s. The question was to determine the number of strings that have
either 5 $0$'s or 5 $1$'s. So, we are looking for the size of the union of
those two sets (the bit strings with 5 $0$'s and the bit strings with 5
$1$'s). The intersection of the 2 sets (i.e, sequences that contain
\emph{both} 5 $0$'s and 5 $1$'s) contains 2 elements: $0000011111$ and
$1111100000$. Therefore, by the inclusion-exclusion principle, the size of
the union of the two sets is $112+112-2=222$.
}

% spring 01, Tutorial 7, problem 5 from Tina
% Pigeon-hole principle

\problem \textbf{Pigeonhole Principle}

\begin{problemparts}

\problempart 
Let $A$ be any set of $n+1$ numbers from the set $\set{1, 2, \ldots,
2 n}$.  Prove that there are always two numbers in $A$ such that
one divides the other.

\solnospace{%Ref. ``Proofs from THE BOOK''.

We use the pigeonhole principle as follows: Let any number of $A$,
$a$, be represented in the form $a = 2^k m$, where $m$ is an odd
number between $1$ and $2n-1$.  Since there are $n+1$ numbers in
$A$k but only $n$ different odd parts, there must be two numbers
in $A$ with the same odd part.  Hence, one is a multiple of the
other.}

\problempart  Let $A$ be any set of $n$ numbers from the set $\set{1,
2, \ldots, 2n}$.  Prove that there are \textbf{not} always two numbers
in $A$ such that one divides the other.

\solnospace{%Ref. ``Proofs from THE BOOK''.

Consider the set $A = \set{n+1, n+2, \ldots, 2n}$.  In this case,
the smallest number $n+1$ could not possibly divide the others
because it can not divide even the largest number $2n$ (unless $2n
= n+1$, which is only true for $n = 1$), since $2(n+1) > 2n$.  It
follows, that none of the numbers can divide any of the other
numbers.
}
\end{problemparts}
\fi

\end{problems}

\end{document}                            
