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

\instatements{\newpage}

\begin{problem}

Recall that $\phi(n)$ is defined to be the number of integers in
$\set{1, \ldots, n}$ that are relatively prime to $n$.  We gave you a
theorem (without proof) to help you compute $\phi(n)$ from the prime
factorization of $n$.  But you can also do this by
inclusion-exclusion.

\bparts

\ppart Use the inclusion-exclusion formula for two sets to
compute $\phi(1000)$.

\hint Let $S_i$ be the set of all multiples of $i$ in $\set{1,
\ldots, n}$.

\solution[\vspace{2in}]{
Every number {\em not} relatively prime to 1000 is a multiple of
either 2 or 5.  Let $S_2$ be all multiples of 2 in $\set{1, \ldots,
1000}$, and let $S_5$ be a multiples of 5 in that range.  Thus, $S_2
\cup S_5$ is the set of all numbers in $\set{1, \ldots, 1000}$ that
are {\em not} relatively prime to 1000.  We can count these with the
inclusion-exclusion formula:

\begin{eqnarray*}
\card{S_2 \cup S_5}
    & = & \card{S_2} + \card{S_5} - \card{S_2 \cap S_5} \\
    & = & \frac{1000}{2} + \frac{1000}{5} - \frac{1000}{2 \cdot 5} \\
    & = & 500 + 200 - 100 \\
    & = & 600
\end{eqnarray*}

Therefore, $\phi(1000) = 1000 - 600 = 400$.}

\ppart Use the general inclusion-exclusion formula and some algebra to
prove that:
\[
\phi(n) = n \cdot \prod_{i = 1}^k \paren{1 - \frac{1}{p_i}}
\]
where $p_1, \ldots, p_k$ are all the distinct primes that divide $n$.

\hint Let $T_i$ be the set of all multiples of $p_i$ in $\set{1,
\ldots, n}$.

\solution{
Let $T_i$ be the set of all multiples of $p_i$ in $\set{1,
\ldots, n}$.  Then there are $\card{T_1 \cup \ldots \cup T_k}$ numbers in
$\set{1, \ldots, n}$ that are \em{not} relatively prime to $n$.  Thus, we
have:

\begin{eqnarray*}
\phi(n)
    & = & n - \card{T_1 \cup \ldots \cup T_k} \\
    & = & n
          - \left( \sum_{i \in \set{1, \ldots, k}}
              \frac{n}{p_i} \right)
          + \left( \sum_{i < j \in \set{1, \ldots, k}}
              \frac{n}{p_i \cdot p_j} \right)
          - \ldots \\
    & = & n \cdot \left(
          1
          - \left( \sum_{i \in \set{1, \ldots, k}}
              \frac{1}{p_i} \right)
          + \left( \sum_{i < j \in \set{1, \ldots, k}}
              \frac{1}{p_i \cdot p_j} \right)
          - \ldots \right) \\
    & = & n \cdot \prod_{i = 1}^k \left( 1 - \frac{1}{p_i} \right)
\end{eqnarray*}
}

\eparts

\end{problem}

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

\instatements{\newpage}

\begin{problem}
This is a selection of challenging counting problems.

\bparts

\ppart How many 5-card hands have a single pair and no 3-of-a-kind or
4-of-a-kind?

\solution[\vspace{1.25in}]{
There is a bijection with sequence of the form:

\[
\begin{array}{l}
(\text{value of pair}, \text{suits of pair}, \\
\text{value 3rd card}, \text{suit 3rd card},
\text{value 4th card}, \text{suit 4th card},
\text{value 5th card}, \text{suit 5th card})
\end{array}
\]

Thus, the number of hands with a single pair is:

\[
13 \cdot \binom{4}{2} \cdot 12 \cdot 4 \cdot 11 \cdot 4 \cdot 10 \cdot 4
\]
}

\ppart How many 5-card hands have two or more kings?

\solution[\vspace{1.25in}]{This is the set of all hands minus the hands
with no kings:

\[
\binom{52}{5} - \binom{48}{5}
\]
}

\ppart How many 5-card hands contain the ace of spades, the ace of
clubs, or both?

\solution[\vspace{1.25in}]{
There are $\binom{51}{4}$ hands containing the ace of spades, an equal
number containing the ace of clubs and $\binom{50}{3}$ containing
both.  By the inclusion-exclusion formula:

\[
\binom{51}{4} + \binom{51}{4} - \binom{50}{3}
\]

hands contain one or the other or both.}

\ppart A committee has 15 Republicans and 10 Democrats.  How many
different 5-person subcommittees with a majority of Republicans are
possible?

\solution[\vspace{1.25in}]{We can choose a committee with $k$ Republicans
and $j$ Democrats in $\binom{15}{k} \cdot \binom{15}{j}$ different
ways.  Therefore, the number of 5-person subcommittees with a majority
of Republicans is:

\[
\binom{15}{5}\binom{10}{0} + 
\binom{15}{4}\binom{10}{1} + 
\binom{15}{3}\binom{10}{2}
\]
}

\ppart In how many different ways can Blockbuster arrange 64 copies of
{\em Cat in the Hat}, 96 copies of {\em Matrix Revolutions}, and 1
copy of {\em Amelie} on 5 shelves?

\solution[\newpage]{This is the number of ways to arrange 64 $C$'s
(Cat in the Hat), 96 $M$'s (Matrix), 1 $A$'s (Amelie), and 4 $X$'s
(dividers between shelves).  This is equal to:

\[
\frac{(64 + 96 + 1 + 4)!}{64!\ 96!\ 1!\ 4!}
\]
}

\ppart I want two large pizzas.  Dominos Pizza offers 11 different
toppings.  At first, I thought this gave me $(2^{11})^2$ options.
What's wrong with this answer, and what is the right answer?

\solution[\vspace{1.5in}]{There are $2^{11}$ pizzas.  The number of
sequences consisting of two pizzas is indeed $(2^{11})^2$.  However,
this double-counts certain orders; for example, the two sequences:

\[
\begin{array}{c}
(\text{mushroom and pepperoni}, \text{pineapple}) \\
(\text{pineapple}, \text{mushroom and pepperoni})
\end{array}
\]

correspond to the same order.

There are $\binom{2^{11}}{2}$ ways to select two {\em different} kinds
of pizza, and $2^{11}$ ways to select two pizzas of the same kind.
Therefore, the number of possibilities is:

\[
\binom{2^{11}}{2} + 2^{11}
\]

Alternatively, we can analyze this in the same way that we considered
orders of donuts.  In this case, there is a bijection between pizza
orders and the number of bit-sequences with $2^{11} - 1$ ones and 2
zeros, which is:

\[
\binom{2^{11} + 1}{2}
\]
}

\ppart In No Limit Texas Hold 'Em poker, each player's hand consists
of five face-up cards and two face-down cards.  Suppose that these
five cards are dealt face up:

\[
\fbox{$A \spadesuit$} \quad
\fbox{$7 \diamondsuit$} \quad
\fbox{$Q \heartsuit$} \quad
\fbox{$7 \heartsuit$} \quad
\fbox{$2 \clubsuit$}
\]

In how many ways can the two face-down cards be chosen so as to form a
3-of-a-kind, but not a 4-of-a-kind?

\solution[\vspace{1.5in}]{There are several cases to consider.  We can
get three aces in $\binom{3}{2} = 3$ ways, since the face-down cards
could be any 2 of the 3 remaining aces.  Similary, we can get three
queens in 3 ways and three 2's in 3 ways.  Otherwise, one of the cards
must be a 7 and the other must not.  We can chose the 7 in 4 ways and
the remaining card in 45 ways.  All of these possibilities are
disjoint, so this gives $3 + 3 + 3 + 7 \cdot 45$ pairs.}

\ppart Suppose that we leave two jokers--- a red one and a black
one--- in a deck of cards and treat them as a {\em wildcards}, which
can serve as any ordinary card.  How many different hands have a
4-of-a-kind, but no 5-of-a-kind?

\solution[\vspace{1.5in}]{There are three possibilities.

\begin{itemize}

\item We get a 4-of-a-kind with no wildcard.  This can happen in $13
\cdot 48$ ways.

\item We get a 3-of-a-kind and one wildcard.  This can happen in $13
\cdot \binom{13}{3} \cdot 48 \cdot 2$ ways.

\item We get a pair and both wildcards.  This can happen in $13 \cdot
\binom{13}{2} \cdot 48$ ways.

\end{itemize}

Thus, the total number of hand with a 4-of-a-kind is:

\[
13 \cdot 48 +
13 \cdot \binom{13}{3} \cdot 48 \cdot 2 +
13 \cdot \binom{13}{2} \cdot 48
\]
}

\ppart How many nonnegative integers less than 1,000,000 have exactly
one digit equal to 9 and have a sum of digits equal to 17?

\solution[\vspace{2in}]{There is a bijection with pairs:

\[
(\text{position of the 9}, \text{values of other 5 digits})
\]

The sum of the other 5 digits is equal to 8, so the number of ways to
choose their values is equal to the number of solutions over the
nonnegative integers to:

\begin{eqnarray*}
x_1 + x_2 + x_3 + x_4 + x_5 & = & 8
\end{eqnarray*}

This is equal to the number of binary sequences with 8 zeros and 4
ones, which is $\binom{12}{4}$.  Therefore, by the general product
rule, there are:

\[
6 \cdot \binom{12}{4}
\]

such integers.
}

\eparts

\end{problem}

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