\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}
\begin{document}

\renewcommand{\pset}[3]
{%\setcounter{problemsetnum}{#1}
\handout{ps#1}{Problem Set #1}{#2}
\centerline{{\bf Due: #3.}}
\bigskip
}

%
%  WARNING:
%
%  There was some trouble with a verbatim environment inside one solution.
%  So I just commented out the /solution for that problem.
%

%\newcommand{\solution}[1]{}
%\pset{7.5}{October 27, 1998}{Never}

\newcommand{\solution}[1]{\bigskip #1}
\psol{7}{October 30, 1998}

\centerline{\bf Read section 4.3 in Rosen.}

%\vspace{1cm}
%
%{\bf This is a ``fake'' problem set intended for midterm preparation
%only.  Do not turn in solutions.}

\begin{problems}

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

\problem A liscence plate has three digits followed by three letters.
However, there are 11 three-letter sequences that the state deems
offensive and never uses.  These sequences are... never mind.  How
many inoffensive liscence plates are there?

\solution{The number of three-letter sequences is $26^3 = 17576$ by
the product rule.  Therefore, there are $17576 - 11 = 17565$
inoffensive three-letter sequences.  The number of three-digit
sequences is $10^3 = 1000$ by the product rule.  Therefore, the number
of inoffensive liscence plates is 17565000, again by the product
rule.}

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

\problem How many binary strings $b_1 b_2 \ldots b_{2n}$ are there
such that for all $1 \leq k \leq n$, one of $b_{2k-1}$ and $b_{2k}$ is
a zero and the other is a one?

\solution{This is the set of binary strings that can be formed by
concatenating $n$ pairs of binary digits, where each pair is either 01
or 10.  Therefore, the number of such strings is $2^n$ by the product
rule.
}

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

\problem Use inclusion-exclusion to prove that at most a quarter of
the numbers less than one million are prime.

\solution{

We will find a lower bound on the number of composite numbers less
than one million.  This will give an upper bound on the number of
primes less than one million.  Define the following sets:

\begin{eqnarray*}
S_2 & = & \{ 4, 6, 8, 10, \ldots, 1000000 \} \\
S_3 & = & \{ 6, 9, 12, 15, \ldots, 999999 \} \\
S_5 & = & \{ 10, 15, 20, 25, \ldots, 1000000 \} \\
S_7 & = & \{ 14, 21, 28, 35, \ldots, 999999 \}
\end{eqnarray*}

The union of these sets is a subset of the composite numbers less than
one million.  Therefore, the size of the union of these sets is a
lower bound on the number of composite numbers less than 1000000.  By
the inclusion-exclusion principle,

\begin{eqnarray*}
|S_2 \cup S_3 \cup S_5 \cup s_7| & = &
	|S_2| + |S_3| + |S_5| + |S_7| \\
&&	- |S_2 \cup S_3| - |S_2 \cup S_5| - |S_2 \cup S_7|
	- |S_3 \cup S_5| - |S_3 \cup S_7| - |S_5 \cup S_7| \\
&&	+ |S_2 \cup S_3 \cup S_5| + |S_2 \cup S_3 \cup S_7|
	+ |S_2 \cup S_5 \cup S_7| + |S_3 \cup S_5 \cup S_7| \\
&&	- |S_2 \cup S_3 \cup S_5 \cup S_7|
\end{eqnarray*}

We can compute the sizes of all the above sets using simple, if
tedious arithmetic.  For example:

\begin{eqnarray*}
|S_3 \cup S_5 \cup S_7|
	& = &	| \{ 105, 210, 315, \ldots, 999915 \} | \\
	& = &	\left\lfloor \frac{1000000}{105} \right\rfloor \\
	& = &	9523
\end{eqnarray*}

Plugging the set sizes into the inclusion-exclusion formula gives:

\begin{eqnarray*}
|S_2 \cup S_3 \cup S_5 \cup s_7| & = &
	499999 + 333332 + 199999 + 142856 \\
&&	- 166666 - 100000 - 71428 - 66666 - 47619 - 28571 \\
&&	+ 33333 + 23809 + 14285 + 9523 \\
&&	- 4761 \\
	& = &	771425
\end{eqnarray*}

Among numbers less than one million, the number 1 is neither prime nor
composite, and at least 771425 numbers are composite.  Therefore,
there are at most $1000000 - 1 - 771425 = 228574$ primes.  Thus, at
most a quarter of the numbers less than one million are prime.

The actual number of primes less than one million is only 78498, so
our upper bound is quite loose.
}

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

\problem Suppose that two teams play a series of games against each
other until one team is ahead by two games or one team wins a total of
three games.  How many series are possible?

%\solution{
We can compute the solution with a tree diagram.  We have created an
equivalent outline of the possibilities below.

\begin{verbatim}
  Team A beats team B.
    Team A beats team B.  Team A wins.  (Case 1.)
    Team B beats team A.
      Team A beats team B.
        Team A beats team B.  Team A wins.  (Case 2.)
        Team B beats team A.
          Team A beats team B.  Team A wins.  (Case 3.)
          Team B beats team A.  Team B wins.  (Case 4.)
      Team B beats team A.
        Team A beats team B.
          Team A beats team B.  Team A wins.  (Case 5.)
          Team B beats team A.  Team B wins.  (Case 6.)
        Team B beats team A.  Team B wins.  (Case 7.)
  Team B beats team A.
    Team A beats team B.
      Team A beats team B.
        Team A beats team B.  Team A wins.  (Case 8.)
        Team B beats team A.
          Team A beats team B.  Team A wins.  (Case 9.)
          Team B beats team A.  Team B wins.  (Case 10.)
      Team B beats team A.
        Team A beats team B.
          Team A beats team B.  Team A wins.  (Case 11.)
          Team B beats team A.  Team B wins.  (Case 12.)
        Team B beats team A.  Team B wins.  (Case 13.)
    Team B beats team A.  Team B wins.  (Case 14.)
\end{verbatim}

There are 14 possible series.
%}

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

\problem Determine the cardinality of each of the following sets.

\begin{problemparts}

\problempart The set of bijective functions from the set of $n$-bit
strings to itself.

\solution{By the product rule, the number of $n$-bit strings is $2^n$.
Order these strings in an arbitrary way.  Some string maps to the
first binary string, some string maps to the second binary string, and
so forth.  Thus, there is a one-to-one correspondence between
bijective functions and permutations of the $n$-bit strings.
Therefore, the number of such functions is $2^n!$.
}

\problempart The set of $n \times n$ matrices such that each of the
numbers $1$ to $2n$ appears at most once in each column.

\solution{We first compute the number of possible columns.  The top
entry in a column can be chosen in $2n$ ways, the next entry can be
chosen in $2n-1$ ways, and so forth.  Thus, overall, a column can be
chosen in $(2n)!/n!$ ways.  Since the matrix consists of $n$ columns,
the number of matrices is given by the product rule:

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

\end{problemparts}

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

\end{problems}
\end{document}
