\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\reading}{Rosen sections 4.1 - 4.5 and sections
6.5 and 6.6.}

\begin{document}
\problemset{9}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\rem}{\text{ rem }}

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

\begin{problem}
Learning to count takes practice and here is your chance--- in
thirteen parts!  Briefly justify your answers to the following
questions.  Not every problem can be solved with a cute formula; you
may have to fall back on case analysis, explicit enumeration, or ad
hoc methods.

You may leave factorials and binomial coefficients in your answers.

\bparts

\ppart How many different arrangements are there of the letters in
$BANANA$?

\solution{
\begin{eqnarray*}
\frac{6!}{1! \ 3! \ 2!}	& = & 60
\end{eqnarray*}

For further explanation, see ``Permutations with Indistinguishable
Objects'' in Rosen.}

\problempart How many different paths are there from point $(0, 0, 0)$
to point $(10, 20, 30)$ if every step increments one coordinate and
leaves the other two unchanged?

\solution{ There is a bijection between the set of all such paths and
the set of strings containing 10 X's, 20 Y's, and 30 Z's.  In
particular, we obtain a path by working through a string from left to
right.  An $X$ corresponds to a step that increments the first
coordinate, a $Y$ increments the second coordinate, and a $Z$
increments the third.  The number of such strings is:

\[
\frac{60!}{10!\ 20!\ 30!}
\]

\noindent Therefore, this is also the number of paths.
}

\ppart In how many different ways can $2n$ students be paired
up?

\solution{Pair up students by the following procedure.  Line up the
students and pair the first and second, the third and fourth, the
fifth and sixth, etc.  The students can be lined up in $(2n)!$ ways.
However, this overcounts by a factor of $2^n$, because we would get
the same pairing if the first and second students were swapped, the
third and fourth were swapped, etc.  Furthermore, we are still
overcounting by a factor of $n!$, because we would get the same
pairing even if pairs of students were permuted, e.g. the first and
second were swapped with the ninth and tenth.  Therefore, the number
of pairings is:

\[
\frac{(2n)!}{2^n \cdot n!}
\]
}

\problempart How many different solutions over the natural numbers are
there to the following equation?

\beqn
x_1 + x_2 + x_3 + \ldots + x_{10} & = & 1000
\eeqn

A solution is a specification of the value of each variable $x_i$.
Two solutions are different if different values are specified for some
variable $x_i$.

\solution{There is a bijection between strings containing 1000 stars
and 9 bars and solutions to this equation.  The 9 bars divide the
stars into 10 segments.  Let $x_i$ be the number of stars in the
$i$-th segment.  Therefore, the number of solutions is:

\[
\binom{1000+9}{9}
\]
}

\problempart In how many different ways can one choose $n$ out of $2n$
objects, given that $n$ of the $2n$ objects are identical and the
other $n$ are all unique?

\solution{We can select $n$ objects as follows.  First, take a subset
of the unique objects.  Then take however many identical elements are
needed to bring the total to $n$.  The first step can be done in $2^n$
ways, and the second can be done in only 1 way.  Therefore, there are
$2^n$ ways to choose $n$ objects.}

\problempart How many undirected graphs without self-loops are there
with vertices $v_1, v_2, \ldots, v_n$?

\solution{There are $\binom{n}{2}$ potential edges, each of which may
or may not appear in a given graph.  Therefore, the number of graphs is:

\[
2^{\binom{n}{2}}
\]
}

\ppart In how many different ways can 10 indistinguishable balls be
placed in four distinguishable boxes, such that every box gets 1, 2,
3, or 4 balls?

\solution{First, we might as well put 1 ball in every box.  Now the
problem is to put the remaining 6 balls into 4 boxes so that no box
gets more than 3 balls.  Now we turn to case analysis.  For example,
we could put 3 balls in two boxes and 0 balls in the other two boxes.
There are $\frac{4!}{2!\ 2!} = 6$ ways to do this.  All cases are
listed below:

\[
\begin{array}{cc}
\text{distribution of balls} & \text{\# of ways} \\
3, 3, 0, 0 & \frac{4!}{2!\ 2!} = 6\\
3, 2, 1, 0 & \frac{4!}{1!\ 1!\ 1!\ 1!} = 24 \\
3, 1, 1, 1 & \frac{4!}{3!\ 1!} = 4 \\
2, 2, 2, 0 & \frac{4!}{3!\ 1!} = 4 \\
2, 2, 1, 1 & \frac{4!}{2!\ 2!} = 6\\
\end{array}
\]

Thus, there are $6 + 24 + 4 + 4 + 6 = 44$ ways in all.
}

\ppart A shelf holds 12 books in a row.  How many ways are there to
choose five books so that no two adjacent books are chosen?

\solution{There exists a bijection from 8-bit sequences with exactly
five 1's to valid book selections.  Map each zero to a non-chosen
book, each of the first four 1's to a chosen book followed by a
non-chosen book, and the last 1 to a chosen book.  For example, the
8-bit sequence:

\[
(1, 0, 1, 1, 0, 1, 0, 1)
\]

maps to the book selection:

\[
\underbrace{c\ n}_{1}\ 
\underbrace{n}_{0}\ 
\underbrace{c\ n}_{1}\ 
\underbrace{c\ n}_{1}\ 
\underbrace{n}_{0}\ 
\underbrace{c\ n}_{1}\ 
\underbrace{n}_{0}\ 
\underbrace{c}_{1}
\]

where $c$ denotes a chosen book and $n$ denotes a non-chosen book.
Therefore, the number of valid book selections is $\binom{8}{5}$.}

\ppart Find the number of 5-card hands with exactly three aces.

\solution{ We can choose the three aces in $\binom{4}{3}$ ways, and
we can choose the remaining two cards in $\binom{48}{2}$ ways.  Thus,
there are $\binom{4}{3} \binom{48}{2}$ such hands.}

\ppart Find the number of 5-card hands in which every suit
appears at most twice.

\solution{There are two cases.  Either one suit appears twice or else
two suits appear twice.  The number of hands in which one suit appears
twice is $\binom{13}{2} \cdot 13^3 \cdot 4$, since there are 4 ways to
choose the doubly-represented suit, $\binom{13}{2}$ ways to choose two
values from this suit, and $13^3$ ways to choose values for cards in
the three remaining suits.  Similarly, the number of hands in which
two suits appear twice is $\binom{13}{2}^2 \cdot 13 \cdot $.
Therefore, there are a total of

\[
\binom{13}{2} \cdot 13^3 \cdot 4 + \binom{13}{2}^2 \cdot 13 \cdot 12
\]

such hands.}

\ppart There are 15 sidewalk squares.  Suppose that a ball can be
thrown so that it bounces on 0, 1, 2, or 3 distinct sidewalk squares.
How many different throws are possible?

\solution{
\[
\binom{15}{0} + \binom{15}{1} + \binom{15}{2} + \binom{15}{3}
\]
}

\ppart Find the number of 7-card hands with three pairs and no three-
or four-of-a-kind.

\solution{We can select the values of the three pairs in
$\binom{13}{3}$ ways, the suits for the three pairs in
$\binom{4}{2}^3$ ways, and the final card in 40 ways.  This gives:

\[
40 \binom{13}{3} \binom{4}{2}^3
\]

hands in all.}

\ppart In how many different ways can the numbers shown on a red
die, a green die, and a blue die total up to 15?  Assume that these
are ordinary, 6-sided dice.

\solution{We fall back on explicit enumeration.  Let $R$, $G$, and $B$
be the values shown on the three dice.

\begin{eqnarray*}
R = 1, B + G = 14 & \rightarrow & 0 \ \text{ways} \\
R = 2, B + G = 13 & \rightarrow & 0 \ \text{ways} \\
R = 3, B + G = 12 & \rightarrow & 1 \ \text{way} \\
R = 4, B + G = 11 & \rightarrow & 2 \ \text{ways} \\
R = 5, B + G = 10 & \rightarrow & 3 \ \text{ways} \\
R = 6, B + G = 9 & \rightarrow & 4 \ \text{ways} \\
\end{eqnarray*}
}

\eparts

\end{problem}

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

\begin{problem}
Joe and Adam play a round of golf, which consists of 18 holes.  A
player's score on each hole is a positive integer, which is recorded
on a scorecard.  A player's total score for the round is the sum of
these 18 positive integers.

\bparts

\ppart Joe's total score is 81, but his score is at least 3 on every
hole.  How many different scorecards could Joe have?

\solution{This is equal to the number of ways to distribute the
remaining $81 - 3 \cdot 18 = 27$ strokes among 18 holes, which is
equal to the number of $(27 + 17)$-bit sequences with exactly 17 ones,
which gives

\[
\binom{44}{17}
\]

different scorecards.
}

\ppart Adam's total score is 88, but he gets a score of 1 on exactly
one hole (a hole-in-one).  How many different scorecords could Adam
have?

\solution{Adam could have scored the hole-in-one at 18 different
holes.  His remaining 87 shots were distributed among 17 holes, and we
know he did not get another hole in one. So all other holes must have
taken at least 2 shots.  This leaves $87 - 2 \cdot 17 = 53$ strokes
across 17 holes, which can be done in $\binom{53 + 17 - 1}{17 - 1}$
ways.  Therefore, there are:

\[
18 \cdot \binom{69}{16}
\]

different scorecards.
}

\eparts

\end{problem}

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

\begin{problem}
Use the pigeonhole principle to solve the following problems.

\bparts

\ppart Show that for some integer $n$, every set of $n$ hundred-digit,
nonnegative integers contains two distinct subsets with the same sum.

\solution{Every hundred-digit number is less than $10^{100}$.
Therefore, a sum of $n$ such numbers must be in the set $\set{0, 1,
\ldots, n \cdot 10^{100}}$, which has size $n \cdot 10^{100} + 1$.  On
the other hand, a set of $n$ numbers has $2^n$ different subsets.
Therefore, by the pigeonhole principle, two different subsets have the
same sum provided:

\beqn
2^n & > & n \cdot 10^{100} + 1
\eeqn

Since $2^{10} = 1024 > 10^3$, we have:

\beqn
2^{350} & > & 1000 \cdot 10^{102} \\
        & > & 350 \cdot 10^{100} + 1
\eeqn

Thus, the inequality holds for $n = 350$.
}

\ppart Prove that among every set of 20 integers, there exist two
whose difference or sum is a multiple of 31.

\solution{Regard the integers as pigeons.  Regard the sixteen sets
$\set{0}$, $\set{1, 30}$, $\set{2, 29}$, $\ldots$, $\set{15, 16}$ as
pigeonholes.  Map integer $n$ to the set containing $n \rem 31$.  By
the pigeonhole principle, two pigeons (integers $a$ and $b$) are
mapped to the same pigeonhole.  Thus, either:

\begin{itemize}

\item $a \rem 31 = b \rem 31$ and so the difference of $a$ and $b$ is
a multiple of 31.

\item $a \rem 31 + b \rem 31$ is either 0 or 31 and so the sum of $a$
and $b$ is a multiple of 31.

\end{itemize}

}

\ppart Jellybeans of 8 different flavors are stored in 6 jars.  There
are 20 jellybeans of each flavor.  Prove that some jar contains at
least two jellybeans of one flavor and also at least two jellybeans of
some other flavor.

\solution{Since there are 20 beans of a given flavor and there are
only 6 jars, some jar must get a pair of same-flavored beans.  Since
there are 8 flavors and only 6 jars, some jar must get two pairs of
same-flavored beans.}

\eparts
\end{problem}

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

\begin{problem}
A positive integer is called {\em cubish} if it is divisible by the
cube of any positive integer greater than 1.  For example, 54 is
cubish (since it is divisible by $3^3 = 27$), but 175 is not cubish.
Use the inclusion-exclusion formula to compute the number of cubish
integers in the set $\set{1, 2, 3, \ldots, 1000}$.
\end{problem}

\solution{Every cubish number less than 1000 must be a multiple of
$2^3$, $3^3$, $5^3$, or $7^3$.  The number of integers in $\set{1, 2,
3, \ldots, 1000}$ that are multiples of $c^3$ is $\lfloor 1000 / c^3
\rfloor$, which is equal to 0 if $c > 10$.  Therefore, by the
inclusion-exclusion formula, the number of cubish numbers is:

\[
\left\lfloor\frac{1000}{2^3}\right\rfloor
+ \left\lfloor\frac{1000}{3^3}\right\rfloor
+ \left\lfloor\frac{1000}{5^3}\right\rfloor
+ \left\lfloor\frac{1000}{7^3}\right\rfloor
- \left\lfloor\frac{1000}{2^3 \ 3^3}\right\rfloor
- \left\lfloor\frac{1000}{2^3 \ 5^3}\right\rfloor
\]

All other terms are 0.  This expression simplifies to 167.}

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

\begin{problem}
Give combinatorial proofs of the identities below.  Use the following
structure for each proof.  First, define an appropriate set $S$.
Next, show that the left side of the equation counts the number of
elements in $S$.  Then show that, from another perspective, the right
side of the equation also counts the number of elements in set $S$.
Conclude that the left side must be equal to the right, since both are
equal to $|S|$.

\bparts

\ppart

\beqn
\binom{2n}{n} & = & \sum_{k=0}^n \binom{n}{k} \cdot \binom{n}{n-k}
\eeqn

A similar identity is proved in Rosen as a corollary of Vandermonde's
Identity, but your proof should be ``from scratch''.

\solution{We are counting the number of $2n$-bit strings with an equal
number of zeros and ones.  On one hand, the number of such strings is
equal to $\binom{2n}{n}$, since we must choose $n$ of the $2n$ bits to
be 1's.  This gives the expression on the left side of the equation.
On the other hand, the number of 1's in the first half of the string
must be equal to some number $k$ between 0 and $n$.  The number of
$2n$-bit strings with exactly $k$ ones in the first half and,
consequently, $n-k$ ones in the second half is equal to $\binom{n}{k}
\cdot \binom{n}{n-k}$.  Summing over all possible values of $k$ gives
the expression on the right side of the equation above.  Since the two
sides of this equation count the elements of the same set in two
different ways, the two sides must be equal.  }

\ppart

\beqn
\sum_{i=0}^r \binom{n+i}{i} & = & \binom{n+r+1}{r}
\eeqn

\solution{Let $S$ be the set of all $(n + r + 1)$-bit sequences with
exactly $r$ ones.  Clearly, the right side is equal to $|S|$.  On the
other hand, we can partition the sequences in $S$ based on the
position of the last zero.  In particular, the last zero must appear
in position $n + i + 1$ for some $i \in \set{0, \ldots, r}$.  The
number of sequences with a zero in position $n + i + 1$ is $\binom{n +
i}{i}$, since such a sequence consists of $i$ ones distributed
arbitrarily in the first $n + i$ positions followed by a 0 and an
unbroken run of 1's.  Therefore, $|S|$ is equal to the left side as
well.  Thus, the right side must equal the left side.}

\eparts

\end{problem}

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

\end{document}


