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

%\backwardscompatibility	% !! use for backwards compatibility
%\showsolutions	 		% !! use to force solutions & skip query
%\hidesolutions			% !! use to force no solutions & skip query


\def\brule#1{\instatements{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% exampreamble %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\instatements{
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llllllll}
  Adrian & Georgi & Josh  & Karen & Lee & Min  & Nikos & Tina   
  \end{tabular}
  \end{center}
  \begin{itemize}

  \item 
  The final is \textbf{closed book}.  There is an \textbf{Appendix} 
  with standard definitions.

  \item 
  There are 12 problems totaling 150 points. Total time is 170 minutes. 
  %% Problems are labeled with their point values.

  \item 
  Put your name on the top of {\bf every} page -- \emph{these
  pages may be separated for grading}.

  \item 
  Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.

 \iffalse
 \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.\fi

  \item 
  GOOD LUCK!
  \end{itemize}
}}

\begin{document} 
\final

\iffalse
{\bf TOPICS:
\begin{enumerate}
 \item Logic, Induction, Strong Induction
 \item Relations (Equivalence, Partial Orders, Paths)
 \item Graphs (Coloring, Connectivity, Paths)
 \item Computational Processes (State Machines, Invariants, Termination)
 \item Annuities, Series, Orders of Growth, Stirlings Formula
 \item Counting: Sum rule, Product Rule, Trees, Pigeonhole
 \item Counting: Permutations, Combinations, Binomial Theorem,
 Combinatorial arguments, Multinomial Coefficients, Stars n Bars
 \item Probability: Probability space, Trees, Conditional probability,
 Independence
 \item Random Vars, Probability Distribution Functions, Expectations,
 Linearity of Expectation, Wald's Theorem, Infinite Expectations
 \item Deviation from the Mean: Markov, Chebyshev, Variance, Variance
 of Sums, Pairwise Independence Sampling Theorem, Polling, Weak Law
 \item More Deviation: Random Walks, Chernoff, Poisson and Central Limit
\end{enumerate}
}
\fi


\instatements{\newpage}

\begin{examproblem}{10}

For each of the following logical formulas with domain of
discourse the natural numbers, $\naturals$, indicate whether it
is a possible formulation of
\begin{itemize}
\item[I:] the \textbf{I}nduction Axiom, 
\item[S:] the \textbf{S}trong Induction Axiom,
\item[L:] the \textbf{L}east Number Principle (called the
  Well-ordering Principle by Rosen), or
\item[N:] \textbf{N}one of these.
\end{itemize}

For example, the Rule for the Least Number Principle in the appendix could
be expressed with the following formula, so it gets
labelled ``L''.
\[
[\exists n P(n)] \implies \exists m\  [P(m)
\land \forall n\ [P(n) \implies m \leq n]]
\qquad\text{\underline{\quad \textbf{L} \quad}}
\]

This is a multiple choice problem: do not explain your answer.

\begin{problemparts}

\ppart[2] $[P(b) \land [\forall k\ge b\ P(k) \implies P(k+1)]]
\implies \forall k\ge b\ P(k)$ \hfill\brule{2em} \solution{\textbf{I.}
This is a formulation of the Induction Axiom with base case
$b$ instead of zero.  $P(k) \implies P(k+1)$ for $k \geq b$ describes
the induction step.}

\ppart[2] $[P(0) \land \forall k\; [\forall m \leq k\ P(m)]
\implies P(k+1)] \implies \forall k\ P(k)$ \hfill\brule{2em}
\solution{\textbf{S.}  Strong Induction with base case 0.}

\ppart[2] $[\forall n\; [\forall m < n\ P(m)] \implies P(n)] \implies \forall
n\ P(n)$ \hfill\brule{2em} \solution{\textbf{S.}  This is the formulation
of Strong Induction with no base case.}

\ppart[2] $[\exists n\ P(n)] \implies \exists n\ [P(n) \land \forall k < n\;
\bar{P(k)}]$ \hfill\brule{2em} \solution{\textbf{L.}}

\ppart[2] $\forall n\; [P(n) \implies \exists n\ [P(n) \land \forall
k\ P(k) \implies n \leq k]]$ \hfill\brule{2em} \solution{\textbf{L.}
This is an equivalent way of expressing the example formula from the
appendix.}

\eparts

\end{examproblem}

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

\iffalse
{\bf INDUCTION: False, strong induction (inclass cp2F)}
\fi

\begin{examproblem}{10} 
An integer, $m$, \emph{divides} an integer, $n$, in symbols, $m
\divides n$, iff there is an integer $k$ such that $km=n$.

\begin{claim*}
For any prime, $p$, and positive integers $x_1, x_2,\dots, x_n$, if $p \divides
x_1x_2\cdots x_n$, then $p \divides x_i$ for some $i$ between 1 and $n$.
\end{claim*}

Underline the sentence where the following proof goes wrong and
explain.

\begin{quote}

\begin{falseproof}
[By strong induction on $n$.]

The induction hypothesis is the Claim itself.

Base case ($n = 1$): When $n=1$, we have $p\divides x_1$,
therefore we can let $i=1$ and conclude $p\divides x_i$.

Induction step: Now assuming the claim holds for all $k\leq n$,
we must prove it for $n+1$.

So suppose $p\divides x_1x_2\cdots x_{n+1}$.  Let $y_n = x_n x_{n+1}$, so
$x_1x_2\cdots x_{n+1} = x_1x_2\cdots x_{n-1}y_n$.  Since the righthand
side of this equality is a product of $n$ terms, we have by induction that
$p$ divides one of them.  If $p\divides x_i$ for some $i < n$, then we
have the desired $i$.  Otherwise $p\divides y_n$.  But $y_n$ is a product
of the two terms $x_n, x_{n+1}$.  Therefore, we have by strong induction
that $p$ divides one of them.  So in this case $p \divides x_i$ for $i =
n$ or $i = n+1$.
\end{falseproof}

\end{quote}

\solution[\newpage]{Notice that the proof above never uses the fact that
$p$ is prime, indicating that something is wrong, since the claim is false
when $p$ is not prime.

The statement ``we have by strong induction that $p$ divides one
of them'' is the place where the proof breaks down: it appeals to strong
induction to justify applying the induction hypothesis for $2=k\leq n$.
But the base case was $n=1$, so we can't assume $2 \leq n$.

Note that the reasoning above is fine for every $n \neq 2$, so the whole
proof would be fine if we had an argument to prove the claim for $n=2$.
This case is indeed true and can be proved as follows: if $p$ does not
divide $x_1$, then, because $p$ is prime, $\gcd(p,x_1)=1$ and so
\begin{equation}\label{mx1}
kp+mx_1=1
\end{equation}
for some integers $k$ and $m$.  Multiplying both sides of~(\ref{mx1}) by
$x_2$ yields
\begin{equation}\label{x2}
kpx_2+mx_1x_2=x_2.
\end{equation}
But when $n=2$, we are given that $p \divides x_1 x_2$.  Hence, we have
that $p$ divides both terms in the sum on the lefthand side of~(\ref{x2})
and therefore divides the righthand side.  That is, $p \divides x_2$.}

\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage} 

\iffalse
{\bf STATE MACHINES, DERIVED VARS,
GRAPHS/TREES (inclass 5W); CP 5W, problem 1, Fall 2002}
\fi


\begin{examproblem}{20}

Given a simple graph $G$, we apply the following operation to the
graph: pick two vertices $u \neq v$ such that either
\begin{enumerate}
\item there is an edge of $G$ between $u$ and $v$ and there is
also a path from $u$ to $v$ which does \emph{not} include this edge;
in this case, delete the edge $\set{u,v}$.

\item or, there is no path from $u$ to $v$; in which case, add the edge
$\set{u,v}$.
\end{enumerate}

We keep repeating these operations until it is no longer possible to
find two vertices $u \neq v$ to which an operation applies.

Assume the vertices of $G$ are the integers $1,2,\dots,n$ for some $n \geq
2$.  This procedure can be modelled as a state machine whose states are
all possible simple graphs with vertices $1,2,\dots,n$.  The start state
is $G$, and the final states are the graphs on which no operation is
possible.
\vspace{0.2in}

\bparts

\ppart[10] \label{derived} For any state, $G'$, let $e$ be the number of
edges in $G'$, $c$ be the number of connected components it has, and $s$
be the number of simple cycles.  For each of the derived variables below,
indicate the \emph{strongest} of the properties that it is guaranteed to
satisfy, no matter what the starting graph $G$ is.  The choices for
properties are: \emph{constant}, \emph{strictly increasing},
\emph{strictly decreasing}, \emph{weakly increasing}, \emph{weakly
decreasing}, \emph{none of these}.  The derived variables are
 
\begin{enumerate}
%%\item[(i)] $e$ \hfill\brule{2in}\solution{none of these}
%%\item[(ii)] $c$ \hfill\brule{2in} \solution{weakly decreasing}
%%\item[(iii)] $s$ \hfill\brule{2in} \solution{weakly decreasing}

\item[(i)] $e-s$  \hfill\brule{2in} \solution{weakly increasing}

%\item[(i)] $c+e$ \hfill\brule{2in} \solution{weakly decreasing}

\item[(ii)] $3c/2 + e$ \hfill\brule{2in} \solution{strictly decreasing}

\item[(iii)] $c+s$ \hfill\brule{2in} \solution{strictly decreasing}

\item[(iv)] $(c,e)$, partially ordered coordinatewise \hfill\brule{2in}
\solution{weakly decreasing}

\item[(v)] $(c,e)$, ordered lexicographically \hfill\brule{2in}
\solution{strictly decreasing}

\end{enumerate}

\vspace{0.2in}

\ppart[6] Choose a derived variable from above and prove that it is
strictly decreasing in some well-founded partial order.  Conclude that the
procedure terminates.

\solution[\vspace{3in}]{

REDO THE SOLUTIONS:

To show that the variable (iii) decreases, note that the rule for
deleting an edge ensures that the connectedness relation does not
change, so neither does the number of connected components; therefore
the variable decreases by one when an edge is deleted.  The rule for
adding an edge ensures that the number of connected components
decreases by one, so the variable changes by $-2$ for the reduced
number of components and $+1$ for the added edge, for a net decrease
of 1.}

\ppart[4] Prove that any final state must be a tree on the vertices.

\solution[\vspace{3in}]{We use the characterization of a tree as a
cycle-free, connected, simple graph.

A final state must be connected, because otherwise there would be two
vertices with no path between them, and then a transition adding the edge
between them would be possible, contradicting finality of the state.

A final state can't have a cycle, because deleting any edge on the
cycle would be a possible transition.
}

\eparts
\end{examproblem}

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

\iffalse
{\bf GAME TREE: True/False Questions on Game Trees.}
\fi



\begin{examproblem}{10} % F01, tut5
This problem is about game trees for two-player games of perfect
information.  Player 1 is the player who plays first.  Player 1 wins
iff Player 2 loses, but the game may end in a draw, or may continue
forever.

For each of the parts below, indicate whether the statement is {\em
true} or {\em false}.  If the claim is false, briefly describe a
counter-example.

\bparts 

\ppart[2] If Player 1 has a winning strategy, then the game cannot
continue forever.

\solution[\vspace{1in}]{False.  The game may not end if Player 1 plays
stupidly---not using his winning strategy.  INSERT COUNTEREXAMPLE.}

\ppart[2] If the game tree is finite-path, then the game cannot
continue forever.
\solution[\vspace{1in}]{True.}

\ppart[2] One of the players must have a non-losing strategy.

\solution[\vspace{1in}]{False.  Consider a game in which the players
have only one move at each step, but the game never ends.}

\eparts

For the remaining parts, we only consider games with finite-path game trees.

\bparts

\ppart[2] If player 1 has a non-losing strategy, then so must player
2.

\solution[\vspace{1in}]{False.  Player 1's non-losing strategy might
be a winning strategy.}

\ppart[2] If the game can only end after an odd number of moves, then
Player 1 has an advantage.

\solution[\vspace{1in}]{False.  It's perfectly possible for Player 2
to have a winning strategy in an odd-number-of-move-game.}


\iffalse

\ppart[3] Player 2 has a winning strategy iff player 1 does not have a
 winning to have a winning strategy in a game with a finite path tree
 $T$ it is sufficient to have at least one subtree of $T$ where player
 1 has a losing strategy.

\solution[\vspace{1in}]{False. It is not sufficient. All subtrees must
have a losing strategy for player 1.}
\fi

\eparts

\end{examproblem}

\iffalse  NIKOS' EARLY DRAFT

\begin{examproblem}{15} % F01, tut5
In this problem Game trees are assumed to be two-player games with
perfect information. Player 1 is the player that plays first and
player 2 is the player that plays second.

For each of the parts below, say whether the statement is {\em true}
or {\em false}. If the claim is false, explain why and provide a
counter-example if possible.

{\bf EDIT: KEEP 5 PARTS?}

\bparts 

\ppart[3] If a Game Tree $T$ has a a finite number of nodes, then there
is a winning strategy for one of the players.\brule{0.5in}

\solution[\vspace{1in}]{True. Finite size implies finite-path
games. From fundamental theorem, we know that since $T$ will have
finite-path games, so there is a winning strategy.}

\ppart[3] If there is a winning strategy for a Game Tree $T$, then $T$
has a finite number of nodes.

\solution[\vspace{1in}]{False. All finite-path, infinite width trees are a
counter-example.}

\ppart[3] If $T_1$ is the Game Tree for player 1 and $T_2$ is the Game
Tree for player 2 of a win-lose game, then $T_1$ is identical to $T_2$
(i.e. the trees are isomorphic and have the same labels from the set
\{$win$, $lose$\}.

\solution[\vspace{1in}]{False. Wins on $T_1$ are labelled Loss on $T_2$.}

%\ppart There are finite Game Trees that neither player has a winning strategy.
%\solution{True. Win, Lose, Draw games.}

\ppart[3] For every win-lose-draw game where player 1 has a non-losing
strategy, we can construct a win-lose game where player 1 has a
winning strategy.

\solution[\vspace{1in}]{True. We group wins and draws in wins for
player 1.}

\ppart[3] For any two-player win-lose-draw game with a finite path game
tree if neither player has a non-losing strategy not have a winning
strategy, then one of the players must have a winning strategy.

\solution[\vspace{1in}]{True. Otherwise both must have a losing
strategy and we know that we can have either one with a winning
strategy or both non-losing strategy.}

\ppart[3]
If player 1 has a winning strategy in a game with a finite path tree $T$,
then player 2 has a losing strategy no matter to which subtree player 1
moves.

\solution[\vspace{1in}]{False. Player 1 must move to a subtree that he
knows he will win.}

\ppart[3]
In order for player 2 to have a winning strategy in a game
with a finite path tree $T$ it is sufficient to have at least one subtree
of $T$ where player 1 has a losing strategy.

\solution[\vspace{1in}]{False. It is not sufficient. All subtrees must
have a losing strategy for player 1.}

\eparts

\end{examproblem}
\fi

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

%{\bf COUNTING: MULTINOMIAL COEFFICIENTS, INCLUSION-EXCLUSION}

\begin{examproblem}{10}

% \problemdata
% {}           
% {MULTINOMIAL COEFFICIENTS, AND INCLUSION-EXCLUSION}              
% {parts (a) (b) F99, Practice Final} 		
% {}
% {}

Consider the seven letter word \emph{armeyer}.
\begin{problemparts}

\problempart[3] How many different sequences of these seven letters
are there? \brule{1in}

\solution[\vspace{1in}]{$\binom{7}{1,1,1,2,2,1} = 7!/2!2!$}


\problempart[7] How many such sequences are there that do not contain
either of the words \emph{eye} or \emph{ram}? \brule{1.5in}. Explain
your answer.

\solution[\vspace{1in}]{Inclusion-Exclusion.
\begin{eqnarray*}
\mbox{Arrangements with eye: use} \set{eye,a,r,m,r} & = & 5!/2!\\
\mbox{Arrangements with ram: use} \set{ram,r,e,y,e} & = & 5!/2!\\
\mbox{Arrangements with ram and eye: use} \set{ram,eye,r} & = & 3!\\
\mbox{Arrangements with neither ram nor eye}
      & = & 7!/2!2! - 5!/2! - 5!/2! + 3! = 1146.
\end{eqnarray*}
}

\iffalse
\problempart[7]
Clearly explain your counting argument for part (b)

\solution{
\begin{eqnarray*}
\mbox{Arrangements with eye: use} \set{eye,a,l,m,r} & = & 5!\\
\mbox{Arrangements with ram: use} \set{ram,l,e,y,e} & = & 5!/2!\\
\mbox{Arrangements with ram and eye: use} \set{ram,eye,l} & = & 3!\\
\mbox{Arrangements with neither ram nor eye}
      & = & 7!/2! - 5! - 5!/2! + 3! = 2346.
\end{eqnarray*}
}
\fi

\end{problemparts}
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}


%{\bf COUNTING: False Argument}

%-FALSE COUNTING
% source: spring00 ps7-5
% source: spring95 ps7
% topic: basic combinatorics, stars and bars

\begin{examproblem}{15}

A pizza house is having a promotional sale. Their commercial reads:
\begin{quotation}\noindent
Buy $2$ large pizzas at the regular price, and for each pizza get up
to $11$ different toppings from $11$ possible absolutely free (no
double toppings). That's $4,194,304$ different ways to design your
order!
\end{quotation}

%%$\displaystyle \left( \sum_{k=0}^{11}\binom{11}{k} \right)^2 =
%%\displaystyle \left(2048 \right)^2 = 4,194,304$\fi

The ad writer was a former Harvard student who had figured out that
$(2^{11})^2 = 4,194,304$. He came up with this number by reasoning
that the number of ways to choose different toppings for one pizza is
all the possible subsets of the set of 11 toppings, which is
$2^{11}$. Since there are two pizzas, the total possible combinations
of pizzas are $(2^{11})^2$.

Unfortunately, the number $(2^{11})^2$ is actually wrong.

\begin{problemparts}
\problempart[5] Explain what is wrong with the Harvard student's
counting.

\solution[\vspace{1.5in}]{The number of ways to choose different
toppings for one pizza is all the possible subsets of the set of 11
toppings, which is $2^{11}$.

However, when the student says that there are $(2^{11})^2$ different
ways to choose toppings for two pizzas, he is making the mistake of
counting the combination ``one mushroom and anchovy pizza, and one
green-pepper pizza'' as different from the combination ``one
green-pepper pizza and one mushroom and anchovy pizza .''  (At least
he knew enough not to count a mushroom and anchovy pizza as different
from an anchovy and mushroom pizza).}

\problempart[3] In how many ways can you choose toppings for the two
pizzas?\brule{1in}

\solution[\vspace{1.5in}]{
The right solution is
\[
2^{11}+\binom{2^{11}}{2} = 2,098,176,
\]
namely, the number of ways to choose two pizzas with the same topping,
plus the number of ways to choose $2$ pizzas with different sets of
toppings.
}

\problempart[7] In how many ways can you choose toppings for $n$
pizzas?\brule{1in}

\solution[\vspace{2in}]{
\[\binom{2^{11}-1+n}{n}.\]

This formula is an instance of the ``stars and bars'' formula.  There are
$(2^{11})$ urns (different types of pizza) and $n$ balls (pizzas).  How
many different ways can you place the balls into the urns.
}

\end{problemparts}
\end{examproblem}

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

\iffalse

{\bf PROBABILITY: Monty Hall, pset 10}
{\bf EDIT: Update solutions!! Changed game}

%% Fall 01, final exam (Jaime Teevan)
\fi


\begin{examproblem}{15}
We consider a variation of Monty Hall's game.  The contestant must pick
one of \emph{four} doors, with a prize randomly placed behind one door and
goats behind the other three.  Then, instead of always opening a door to
reveal a goat, Carol \emph{randomly} opens two of the three doors that the
contestant hasn't picked.  This means she may reveal two goats, or she may
reveal the prize and a goat.  If she reveals the prize, then the entire
game is \emph{restarted}, that is, the prize is again randomly placed
behind some door, the contestant again picks a door, and so on until Carol
finally reveals two goats.  Then the contestant can choose to \emph{stick}
with his original choice of door or \emph{switch} to the remaining
unopened door.  He wins if the prize is behind the door he last
chooses.

\iffalse
To analyze this setup, we define two events:
\begin{description}
\item[$GP$:] The event that the contestant \textbf{g}uesses the door with
the \textbf{p}rize behind it on his first guess.

\item[$OP$:] The event that the game is restarted at least once.  Another
way to describe this is as the event that the door Carol first
\textbf{o}pens has a \textbf{p}rize behind it.
\end{description}

\bparts

\ppart[4] What is $\pr{GP}$?
\brule{0.5in}. $\prcond{OP}{\bar{GP}}$?\brule{0.5in}.  \solution{1/3,
1/2}

\ppart[4] What is $\pr{OP}$? \brule{0.5in} \solution[\vspace*{0.7in}]{
\[
\prcond{OP}{GP}\pr{GP} + \prcond{OP}{\bar{GP}}\pr{\bar{GP}} = 0\cdot 1/3 +
1/2 \cdot 2/3 = 1/3.
\]
}
\fi

\bparts

\ppart[6] Let $R$ be the number of times the game is restarted before
Carol picks two goats.  What is $\expect{R}$?\brule{0.8in}

%% (You may express the answer as a simple closed form in terms of $p
%% \eqdef \pr{OP}$.)

\solution[\vspace*{2in}]{ $1/(1-p) - 1 = 3/2 -1 = 1/2$.

Think of \emph{not} having to restart as a failure.  So
$\pr{\text{failure}} = 1-p$, and $\expect{R}$ is mean time to failure
minus one---because we are only counting the number of
``successes''---namely, $1/\pr{\text{failure}} - 1$.}

\iffalse
\ppart What is the probability the game will continue
forever?\brule{0.5in}

\solution[\vspace*{0.7in}]{0. In terms of the previous problem part,
this is the probability of \emph{never} failing.}

\newpage
\fi

\ppart[5] When Carol finally reveals two goats, the contestant has
the choice of sticking or switching.  Let's say that the contestant
adopts the strategy of sticking. What is the probability that the
contestant wins with this strategy? \brule{0.5in}

\solution[\vspace{4in}]{REVISE:

1/2, because
\[\begin{array}{rcll}
w & = & \prcond{W}{GP}\pr{GP} 
        & +\ \prcond{W}{\bar{GP}\intersect OP}\pr{\bar{GP}\intersect OP}\\
  &   & & +\ \prcond{W}{\bar{GP}\intersect \bar{OP}}\pr{\bar{GP}\intersect \bar{OP}}\\
  & = & 1 \cdot 1/3 & +\ w \cdot 2/3 \cdot 1/2 + 0 \cdot 2/3 \cdot 1/2\\
  & = & 1/3 + w/3.
\end{array}\]
So $w(1- 1/3) = 1/3$.}


\iffalse
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}

\item $\prcond{W}{GP} = $ \brule{0.5in}
\solution{1}

\item $\prcond{W}{\bar{GP}\intersect OP} = $ \brule{0.5in}
\solution{ $w$}

\item $\prcond{W}{\bar{GP}\intersect \bar{OP}} = $ \brule{0.5in}
\solution[\vspace{0.5in}]{0}
\end{enumerate}
\ppart[5] What is $\pr{W}$? \brule{0.5in}
\fi

\ppart[4] For any final outcome where the contestant wins with a ``stick''
strategy, he would lose if he had used a ``switch'' strategy, and vice
versa.  In the original Monty Hall game, we concluded immediately that the
probability that he would win with a ``switch'' strategy was
$1-\pr{\text{win with stick}}$.  Why isn't this conclusion quite as
obvious for this new, restartable game?  Briefly explain why this
conclusion still sound.

\solution{
Switching strategies turns wins to losses for \emph{terminated}
games.  So the probability of win with switch is $t-\pr{W}$ where $t$ is
the probability of termination.  In original Monty Hall, the game obviously
terminated after one door-opening, so $t$ was 1.

The extra complication here is that it is possible for the game to run
forever, but this event has probability 0, so $t$ is still 1, and the
conclusion is still sound.}

\iffalse

\ppart Ben Bitdiddle claims that we didn't need all this analysis to
determine a good strategy.  He says that sticking will be a losing
strategy for the contestant, just as in the original Monty Hall game.  His
reasoning is that, because it is more likely than not that the prize is
behind one of the doors the contestant didn't pick, it's to the
contestant's advantage to switch whenever he has the opportunity.  How
would you explain to Ben, briefly, what the fallacy is in his reasoning?
\fi

\eparts
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}


%{\bf COUNTING EXPECTATIONS GRAPHS}


\begin{examproblem}{10}
A \emph{simple $k$-cycle} in a simple graph is an undirected path
going through each of $k$ distinct vertices exactly once and ending
where it started (where $k>2$).  A simple $k$-cycle can be represented
by the sequence of $k$ distinct vertices $v_1, v_2, \ldots, v_k$ along
the path.

Note that every simple $k$-cycle can be represented by many sequences.
For example, the 4-cycle represented by $1234$ is as the same cycle
represented by $2341$ or $3412$ because a cycle does not have to start
at any particular vertex.  It is also represented by $4321$, because
the cycle is undirected.

\bparts

\ppart[3] How many different sequences of vertices represent a given
simple $k$-cycle?\brule{0.7in}

\solution[\vspace{0.5in}]{$2k$}


\ppart[2] In a complete graph on $n$ vertices (i.e. all possible edges
are present), how many simple $k$-cycles are there?\brule{0.7in}

\solution[\vspace{0.5in}]{ $P(n,k)/2k$.

The number of ways of choosing a ordered sequence of $k$ vertices is
$P(n,k)$, but each simple $k$-cycle is represented by $2k$ such sequences.}

\eparts

%%\instatements{\newpage}

Suppose we construct a simple $n$-node graph, $G=(V,E)$, randomly as
follows: For every set of two distinct vertices $\set{v,v'}$, toss a
biased coin whose probability of coming up heads is $p$.  The
undirected edge between $v$ and $v'$ is included in $E$ iff the coin
comes up heads. Assume that all coin tosses are mutually independent.

\bparts

\ppart[5] What is the expected number of simple $k$-cycles in $G$?
(Note: If you were not able to solve part (b), you may let $b$ denote
the answer to part (b) and express your answer in terms of $b$, $k$,
and $p$). \brule{0.7in}

\solution[\vspace{2in}]{A particular simple $k$-cycle (call it $e$)
will occur only if all of the edges in that cycle exist in the
randomly constructed $G=(V,E)$.  Since each edge is independently
added with probability $p$, we have $\pr{e \text{ occurs in } G} =
p^k$.

Let $I_e$ be the indicator random variable of the event that a
particular $k$-cycle, $e$, occurs.  So the number, $N$, of $k$-cycles
is $\sum_e I_e$ where $e$ ranges over all possible $k$-cycles, \ie all
$k$-cycles in the complete graph on $V$.

We know from a previous part that $\pr{I_e = 1} = p^k$, which means that
$\expect{I_e} = p^k$.  Also, the total number of distinct possible
$k$-cycles is $X \eqdef P(n,k)/2k$.

Therefore
\[
\expect{N} = \sum_e \expect{I_e} = X p^k.
\]
}
                                                          
\eparts 
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

%{\bf EXPECTATION, INFINITE VARIANCE, SERIES}

\begin{examproblem}{10}
Let $R$ be a positive integer valued random variable such that
\[
f_R(n)  = \frac{1}{cn^3},
\]
where
\[
c \eqdef \sum_{n=1}^{\infty} \frac{1}{n^3}.
\]

\begin{problemparts}

\problempart[5] \label{exf} Prove that $\expect{R}$ is finite.

\solution[\vspace{3in}]{
\begin{align*}
\expect{R} \eqdef & \sum_{n \in \naturals^{+}} n \cdot \frac{1}{cn^3}\\
 = & \sum_{n \in \naturals^{+}} \frac{1}{cn^2}\\
 < &\ 1+\int_{1}^{\infty} \frac{1}{cn^2}\\
 = &\ 1 + \frac{1}{2c}\\
< &\ \infty.
\end{align*}

Note that $\sum_{n \in \naturals^{+}} 1/cn^2 < \infty$ was also shown in
Class Problem 1 of Week 7, Friday.}

\problempart[5] Prove that $\variance{R}$ is infinite.

\solution[\vspace{3in}]{
Since
\[
\variance{R} = \expect{R^2} - \expectsq{R},
\]
and $\expectsq{R} < \infty$ by part~(\ref{exf}), we need only show
that $\expect{R^2} = \infty$.  But
\begin{align*}
\expect{R^2} \eqdef & \sum_{n \in \naturals^{+}} n^2\frac{1}{cn^3}\\
 = & \sum_{n \in \naturals^{+}} \frac{1}{cn}\\
 = & \lim_{n \to \infty} \frac{1}{c} \cdot H_n\\
 = &\ \infty.
\end{align*}

Note that $\sum_{n \in \naturals^{+}} 1/cn = \infty$ was
also shown in Class Problem 1 of Week 7, Friday.}

\end{problemparts}
\end{examproblem}

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}


%{\bf EXPECTATIONS, WALD'S THEOREM, OTHER}\\



\begin{examproblem}{20}

Suppose that you are given two biased coins $C_p$ and $C_r$.  Coin
$C_p$ flips a head with probability $p$ and coin $C_r$ flips a head
with probability $r$.

The game is to flip $C_p$ and then $C_r$ and keep alternating between
coins until you get $2l$ heads in a row, where $l$ is a given positive
integer.  However, as soon as you get a tail, then you start over again by
first flipping $C_p$ and then alternating between coins\footnote{For
example, if $l=2$ and the sequence of flips was $HTTHHTHHHH$, then the
game took 10 flips and the sequence of coins used was $C_p C_r C_p C_p C_r
C_p C_p C_r C_p C_r$}.  Assume that coin flips are mutually independent of
each other.

\begin{problemparts}
\problempart[10] For $l=3$, write an expression in $p$ and $r$ for the
the expected number of coin flips to see $2l$ heads in a row.

\hint It may be more convenient to use the special expectation formula
for natural number valued variables (in the Appendix).

\solution{

Solve using Wald's theorem

\[
\expect{\text{number of flips}} = \expect{\text{number of trials}} \cdot
\expect{\text{length of trial}}
\]

\[
\pr{\text{Success of a trial}} = p \cdot r \cdot p \cdot r \cdot p \cdot r
          = {(pr)}^{3}
\]
because we need 6 heads in a row.

\[
\expect{\text{number of trials}} = \frac{1}{\pr{\text{Success}}} =
\frac{1}{(pr)^{3}}.
\]

Let $Q$ be the length of the try.
\begin{align}
\expect{Q} = & \sum_{i=0}^{5} \pr{Q > i}\notag\\
  =& 1 + p + p \cdot r + p \cdot r \cdot p + p \cdot r \cdot p \cdot r + p
  \cdot r \cdot p \cdot r \cdot p \notag\\
= & 1 + p + p r + p^2r + p^2r^2 + p^3 r^2\label{EQ 1}
\end{align}
Therefore, the {\bf ANSWER} is:
\[
\expect{\text{number of flips}} = \frac{1 + p + p r + p^2r + p^2r^2 + p^3 r^2}{(pr)^{3}}
\]

{\bf Alternate solution:}

You can also compute $\expect{Q}$ directly from the normal expectation
formula
\begin{align}
\expect{Q} \eqdef & 1 \cdot (1-p) \notag \\
& + 2 \cdot p \cdot (1-r) \notag\\  
& + 3 \cdot p \cdot r \cdot (1-p) \notag\\
& + 4 \cdot p \cdot r \cdot p \cdot (1-r) \notag\\ 
& + 5 \cdot p \cdot r \cdot p \cdot r \cdot (1-p) \notag\\
& + 6 \cdot p \cdot r \cdot p \cdot r \cdot p \cdot (1-r) \notag\\
& + 6 \cdot p \cdot r \cdot p \cdot r \cdot p \cdot r \notag\\
=  & (1-p) + 2p(1-r) + 3pr(1-p) + 4p^2r(1-r) + 5p^2r^2(1-r) +
6p^3r^2\label{EQ 2}
\end{align}
When you simplify~(\ref{EQ 2}) you get~(\ref{EQ 1}). %(confirmed by RAD)
}

\instatements{\newpage}

\problempart[10] What is the expected number of coin flips to see $2L$
heads in a row?

{\em Note:} You may express your answer using summations determined by
$L$, but if you do, you should briefly indicate how results from the
course imply that there are closed forms for your summations.

\solution{

\begin{align*}
\pr{\text{Success of a trial}} = & {(pr)}^{L}\\
\expect{\text{number of trials}} = & \dfrac{1}{\pr{\text{Success}}} =
               \dfrac{1}{(pr)^L}
\end{align*}
Let $Q$ be the length of the try.
\[
\expect{Q} = \sum_{i=0}^{2L-1} \pr{Q > i}.
\]

If $i$ is even ($i=2k$), then $\pr{Q > i} = (pr)^{k}$; if $i$ is odd
($i=2k+1$) then $\pr{Q > i} = (pr)^{k}p$.  Therefore
\[
\expect{Q} = \sum_{k=0}^{L-1} (pr)^{k} + \sum_{k=0}^{L-1} (pr)^{k}p.
\]

Both of these sums are simple geometric series so it is possible to
find closed forms.
}

\iffalse
\problempart What is the expected number of coin flips to see the
pattern $THH$?

\solution{
Model the process as a state machine with three states.  Let $S$ be
the start state where no progress as been made towards the THH
goal. Let $V1$ is the state after flipping tails from $S$. Let $V2$ be
the state after flipping heads from $V1$.

$S$ transitions to $V1$ with probability $1-p$, the probability of
flipping tails. $S$ transitions back to itself with probability $p$,
the probability of flipping heads.  Therefore, if $E_s$ is the
expected number of flips before reaching the goal,

$E_s =  1 + E_v1 * (1-p) + E_s * p $ 

$V1$ transitions to $V2$ with probability $p$. $V1$ transitions back
to itself with probability $1-p$, because flipping tails does not
require trying again from the beginning.  Thefore, $E_v1$ is,

$E_v1 =  1 + E_v1 * (1-p) + E_v2 * p $ 

$V2$ transitions back to $V1$ with probability $1-p$, because flipping
the sequence THT requires starting back at $V1$.

$E_v2 =  1 + E_v1 * (1-p) + 0 * p $ 

Using the three equations to solve for $E_s$, we get,

$E_s =  \frac{1}{1-p} + \frac{1+p}{p^2}$
}
\fi

\end{problemparts} 
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}
\begin{examproblem}{10}

\begin{problemparts}

\problempart[5] Let $R$ be an indicator variable for getting a head on a
flip of a fair coin.  Calculate the bound on $\pr{R \geq 1}$ using

\begin{enumerate}
\item[(i)] Markov Bound \brule{1in}
\item[(ii)] Chebyshev Bound \brule{1in}
\item[(iii)] Chernoff Bound \brule{1in}
\end{enumerate}

{\em Note:} $e^{\ln 2} \approx 2$

\solution[\vspace{0.5in}]{ In this case $\mu_R = 1/2$ and $\sigma_R^2
= 1/4$, so

\begin{itemize}

\item Markov gives $\mu_R/y = 1/2$ which is exactly right,

\item The bound from the Chebyshev is
\[
\frac{\sigma_R^2}{(y - \mu_R)^2} = \frac{1/4}{(1-(1/2))^2} = 1
\]

However if we assume that the distribution is symmetric about the
mean, then Chebyshev bound gives us 1/2 and so is exactly tight.

\item the bound from the Chernoff result is
\[
\text{exp}(- (2 \ln 2 - 2 + 1)/2) = e^{1/2 - \ln 2} = \sqrt{e}/2 > 0.83,
\]
and so is a large overestimate.

\end{itemize}
}


\problempart[5] Prove that $\variance{X+Y} = \variance{X} + \variance{Y}$,
if $X,Y$ are independent.  Be sure to justify each step in your proof.

\solution{
We will transform the left side into the right side.  We begin by
applying the alternate definition of variance:
\begin{equation}\label{altvar}
\variance{X + Y} = \expect{(X + Y)^2} - \expectsq{X + Y}.
\end{equation}

We will work on the first term and second terms on the righthand side
of~(\ref{altvar}) separately.  For the first term,
\begin{align}
\expect{(X+Y)^2}
 = &   \expect{X^2 + 2 X Y + Y^2} \notag\\
 = &   \expect{X^2} + 2\expect{X Y} + \expect{Y^2} & \text{(linearity of $\expect{}$)}\notag\\
 = &   \expect{X^2} + 2 \expect{X} \expect{Y} +
 \expect{Y^2}.
& \text{(independent multiplicativity of $\expect{}$)}\label{eY2}
\end{align}

Now we work on the second term on the righthand side of~(\ref{altvar}).
\begin{align}
\expectsq{X+Y}  = & (\expect{X} + \expect{Y})^2
                  & \text{(linearity of $\expect{}$)} \notag\\
 = & \expectsq{X} + 2 \expect{X} \expect{Y} + \expectsq{Y}.\label{esX}
\end{align}

Subtracting~(\ref{esX}) from~(\ref{eY2}), we have
\begin{align*}
\variance{X + Y}  = &  (\expect{X^2} + 2 \expect{X} \expect{Y} + \expect{Y^2})
        - (\expectsq{X} + 2 \expect{X} \expect{Y} + \expectsq{Y})\\
 = & (\expect{X^2} - \expectsq{X}) + (\expect{Y^2}) - \expectsq{Y}) \\
 = &   \variance{X} + \variance{Y}.
\end{align*}

\iffalse

Let $R = X + Y $.  We can compute $\expectsq{R}$ as follows:
\begin{eqnarray*}
\expectsq{R}
& = & \left(\expect{X+Y+Z}\right)^2 \\
& = & (\expect{X} + \expect{Y} + \expect{Z})^2 \\
& = & \expectsq{X} + \expectsq{Y} + \expectsq{Z} + 2\expect{X}\expect{Y} + 
       2\expect{X}\expect{Z} + 2\expect{Y}\expect{Z}
\end{eqnarray*}

Computing $\expect{R^2}$ we get:
\begin{eqnarray*}
\expect{R^2} 
& = & \expect{(X+Y+Z)^2}\\
& = & \expect{X^2 + Y^2 + Z^2 + 2XY + 2XZ + 2YZ} \\
& = & \expect{X^2} + \expect{Y^2} + \expect{Z^2} + 2\expect{XY}
      + 2\expect{XZ} + 2\expect{YZ}\\
& = & \expect{X^2}  + \expect{Y^2} + \expect{Z^2} + 2\expect{X}\expect{Y} + 
       2\expect{X}\expect{Z} + 2\expect{Y}\expect{Z}
\end{eqnarray*}

Notice that the last step is only valid because the random variables are
pairwise independent. Finally, we can compute $\variance{R}$.  We can
begin immediately by cancelling out the cross terms leaving us with:

\begin{eqnarray*}
\variance{R}
& = & \expect{R^2} - \expectsq{R}\\
& = & \expect{X^2} + \expect{Y^2} + \expect{Z^2}
        - (\expectsq{X} + \expectsq{Y} + \expectsq{Z}) \\
& = & \expect{X^2} - \expectsq{X} + \expect{Y^2}
      - \expectsq{Y} + \expect{Z^2} - \expectsq{Z} \\
& = & \variance{X} + \variance{Y} + \variance{Z},
\end{eqnarray*}
thus concluding the proof.
\fi

}

\end{problemparts}
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

\iffalse

{\bf SAMPLING: Pairwise Independent Sampling Theorem, cp14M
+ second part}

from cp14M; used both parts

{\bf EDIT: To have two test tubes with 1:2 ratio of sampling so that
can not directly use binomila approximation}
 \fi

\begin{examproblem}{10}

A test tube with a bacterial culture is delivered to a Lab technician
at a hospital.  Her task is to estimate the percentage of bacteria in
the culture that are resistant to penicillin.  She will do this by
sampling a certain number of bacteria and testing them.  Assume her
sampling technique is good, \ie the bacteria are sampled randomly and
independently with replacement.  Let the percentage of
antibiotic-resistant bacteria be $b$.

\begin{problemparts}

\problempart[6] Write a formula for a number, $n$, of samples she
could take in order to be C\% confident that her estimation was no
more than $d$ away from the actual value $b$.  The formula for $n$
must not, of course, involve the unknown quantity, $b$.

\solution[\vspace{3in}]{Let $p$ be the probability that the
estimation is within $d$ of the actual value $b$. The Pairwise
Sampling Theorem tells us that

\[
p \eqdef \pr{\abs{\frac{S_n}{n} - b} \geq d}
\leq 
\frac{\sigma^2}{nd^2}
\]

In this case, we are modelling sampling bacteria as $n$ coin flips, and
the variance of a flip is $b(1-b)$.  This is maximized when $b=1/2$.  This
gives us the bound $p \leq 1/4nd^2$.  Our percent confidence level is
$100(1 - p) \geq 100(1 - 1/(4nd^2))$, so in order to be at least 95\%
confident, we need
\[
100(1 - \frac{1}{4nd^2}) \geq 95.
\]
Solving for $n$, we get
\begin{eqnarray*}
0.05 & \geq & \frac{1}{4nd^2}\\
n & \geq & \frac{1}{4 \cdot 0.05 c^2} = \frac{5}{c^2}.
\end{eqnarray*}
}

\ppart[4] The lab technician is supposed to perform her task daily.
She is instructed to warn the medical staff whenever her tests show
with 99\% confidence that the percentage of penicillin-resistant
bacteria in that day's tube exceeds a specified danger threshold.

In early April, the staff receives its first warning of the year from her,
and a new resident on the staff orders the nurses to review the medication
of all patients taking penicillin, because he realizes there is a very
high probability of a dangerous level of penicillin-resistance bacteria in
the hospital.  When a more senior physician arrives, he overrules the
residents' order.

Briefly indicate how you would justify the senior physician's decision
to the resident.

\solution{Based on the technician's warning, the resident thought it was a
good bet that there were dangerous levels of penicillin-resistance in the
hospital.  He was exhibiting the common confusion between probability and
confidence level.

With 99\% confidence level of reporting, we \emph{expect} the technician
to get mistaken results about 1\% of the time.  So after the 100 days to
mid-April of reporting no danger, we could expect her to report a
dangerous threshold when there isn't any.  The resident shouldn't order
extra work for the nursing staff when in this situation, he can expect
that the danger report will usually be a ``false positive.''.  So the
senior physician's decision not to order a full scale review of medication
is a sound one.

On the other hand, if the physician is never going to pay attention to the
technician's warning, it's silly to waste her time doing estimates.  In
the face of the technician's warning, a sensible action to take would be
to ask her to repeat her estimation.  There is only a 1\% chance she would
report danger again if there was none, so if she does report it after the
repeat estimate, it would be prudent to order the medication review.
}

\eparts


\end{examproblem}


\end{document}


\iffalse


%% NEWPAGE--------------------------------------------------


{\large BACKUP QUESTIONS: MOST OF THEM STILL NEED WORK}




%% NEWPAGE--------------------------------------------------
\instatements{\newpage} 

{\bf GRAPHS, TRUE FALSE, edit to remove stuff we didn't do and add
other questions?}



%% FALL 97
\begin{examproblem}{0} For each of the statements below circle the
correct answer.



\begin{list}{{\bf T\ \ F\ \ \ }}
	     {\setlength{\leftmargin}{40pt}%
              \setlength{\labelwidth}{\leftmargin}%
              }
\item[T F]
Adding $k$ edges to an undirected graph increases its chromatic
       number (the number of colors needed to color the vertices)
       by at most $k$.
\item[T F]
The number of shortest paths in an $n$-vertex undirected graph is
       $O(n^2)$. (Note: there may be more than one shortest path between
       two vertices.)
\item[T F] The number of length-$3$ paths in an $n$-vertex undirected graph is
       $O(n^2)$.
\item[T F] The number of length-$3$ paths in an $n$ vertex tree is $O(n)$
\item[T F] Reversing the directions of all edges in a directed graph leaves
       the number of simple directed cycles unchanged.
\item[T F] If an undirected graph has the degree of every vertex
divisible by a prime $p$, then $p$ must evenly divide the number of
edges.
\end{list}

\solution{ true, false, false, false, true, false }

\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}
{\bf COUNTING: False argument (Rudich)}

%% FALSE COUNTING
%% Counting at least 3 ACES,
%% source: Rudich lectures.
\begin{examproblem}{0}
Theory Hippo has been playing poker for a long time now. REMIND HOW
MANY SUITS AND VALUES THERE ARE. Given a hand of 5 cards, how many
hands have at least 3 aces?

ARGUMENT 1: There are $\choose{4,3}=4$ ways of picking 3 of the 4
aces. And there are $\choose{49,2}=1176$ ways of picking 2 cards from
the remaining 49 cards. This gives $4 \times 1176 = 4704$ possible
hands.

ARGUMENT 2: The number of hands with exactly three cards is
$\choose{4,3}=4$ ways of picking 3 of the 4 aces and then
$\choose{48,2}=1128$ ways of picking two non ace cards. This gives us
$4 \times 1128 = 4512$ hands. Similarly, the number of hands with
exactly 4 aces is $\choose{4,4}=1$ ways of picking all 4 aces, and 
$\choose{48,1}=48$ ways of picking the last card. In other words there
are 48 hands with exactly 4 aces. Therefore the number of hands with
at least 3 aces is $4512 + 48 = 4560$.

Something is not right....

\begin{problemparts}
\problempart Which counting argument is incorrect?

\problempart{ARGUMENT 1}

\problempart Explain how the counting argument goes wrong.

\solution{Overcounts. Best way is to give an example. 
Consider the hand AAA 7 A. This gets counted several times over}

\end{problemparts} 
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

\begin{verbatim}

TA SUGGESTIONS:

recycle the class problem on the Magic Trick:

(a) prove that $\max\set{degree(v) \suchthat v \in V_1}
\le \min\set{degree(v) \suchthat v \in V_2}$ is sufficient to satisfy the
Hall Theorem ``no bottleneck'' condition.

(b) Conclude the Magic Trick is possible with a deck of up to 124 cards.

%%%

Karen
13M #2--graduating students with number of credits--various bounds
8F #3--set of n elements--count different kinds of relations (binary,
       symmetric, etc)

Lee
My two favorites are:

Week 5, Wed, Problem 1:  Proving that a procedure on a graph terminates 
and that the resulting graph is a tree

Week 7, Wed, Problem 2:  Give a formula for the contents of wine and 
water after deterministic mixing.

My only concern is that using such problems on a problem set could take 
a long time to grade.

Min
In-class Problem Week12 Wed. Problems 1 and 2 can be merged as a final
problem. Problem 1 is about probabilities of failures with n independent
bernoulli trials. Problem 2 is an application (stickers in Doritos) of
problem 1. When students did this problem, some of them had difficulties
to change it as problem 1's format and used problem 1's results.

In-class Problem Week14 Mon. Problem 2 is about the sampling
theorem. During my office hours, some students asked about the polling
size of the sampling theorem. It seems to me that some of them do not
quite understand about the theorem.

Tina:

Hi,

Sorry this is late -- here are a couple of in-class problems that I
liked:

Cp9W -- problem 2 on counting graph coloring
Cp5F -- problem 1 on the picking coordinates game

Nikos:


my choices are:

cp10F Prob. 1 : Boys and Girls and Concensus
cp10F Prob. 3: HTT vs HHT
cp6F  Prob. 3: PayTrees (was moved to pset, so not sure whether it counts
for inclass).
cp4F Prob. 1: Line graphs false proof.

Other:

Waiting Time:

Making independent flips of an (un?)fair coin, what is the expected
time to flip \texttt{THH}?

Review Question:
>    We actually had an interesting question on asymptotics:
>    Are there functions f and g such that f=O(g) but not Theta(g) and not
>    o(g)?
> Did you answer the question?  standard example would be
>                         f(n) ::= g(n)*sin^2(n pi/2),
> (for most g, for example, if log* n = O(g))
>
> Regards, A.




\end{verbatim}



%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

% \problemdata                                                             
% {Pigenhole/Counting} % latex-friendly label for the prob.
% {STARS \& BARS, PIGEONHOLE} % The topic(s) of the problem content.  
% {stimulated by S01 Final, 4, suggested F02 Q2 by Tina Wang} 
% {F02 Q2, prob 5} % Usage (list ones you are aware of). 
% {ARM, 11/19/02} % Last revision info (author, date).   

\begin{examproblem}{0} 

Let $S \eqdef \set{0,1,\dots,9}^{90}$ be the set of all sequences of
length 90 consisting of digits $\set{0,1,\dots,9}$.  Two
sequences, $s_1,s_2 \in S$ are said to have the \emph{same digit
distribution} iff $s_1$ has the same of number of occurrences of digit
$j$ as $s_2$, for each $j \in \set{0,\dots,9}$.

\begin{problemparts}

\iffalse

\ppart[7] Describe a bijection between digits distributions and arrangements
of ``stars \& bars.''

\solution[\vspace{3in}]{There is a bijection between digit distributions
and permutations of 90 stars and 9 bars.  The 9 bars divide the 90 stars
into 10 blocks, with the number of stars in the $i$th block equal to the
number of occurrences of digit $i$ in the distribution.}


\ppart[7]\label{digita} Give a closed formula, possibly also involving
factorials and binomial coefficents, for the number, $g$, of possible
digit distributions.

\solution[\vspace{0.5in}]{the number of permutations of 90 stars and 9 bars is
\[
g = \binom{99}{9}.
\]
}

\ppart[6]

\fi

\problempart Let $n$ be the smallest number such that any set of $n$
sequences in $S$ is sure to contain 1,000,000 different sequences with
the same digit distribution.  Give a closed formula, possibly also
involving factorials and binomial coefficents, for $n$.  \hint
$C(90,3) < 10^6 < C(90,4)6$.

\iffalse
You may write your formula in terms of $g$ in part~(\ref{digita}).
\fi


\solution[\vspace{0.5in}]{


The correct answer, which a few students got and most of the staff did
not, is $n = 3g-19$.

This is a problem about the Generalized Pigeonhole Principle.  Here the
pigeons are the $10^{90}$ possible sequences of 90 digits and the holes
are the $g$ possible digit distributions.  However, for any digit $d$,
there is only one possible sequence with digit distribution specifying 90
$d$'s.  That is, each of these 10 \emph{special} holes (digit
distributions of 90 $d$'s, for each digit $d$), can hold a single, unique
pigeon (the sequence $d^{90}$).  There are at least 90 pigeons eligible
for assignment to each of the other $g-10$ holes.

So we can put 3 pigeons in each of the other $g-10$ holes and 1 pigeon in
each of these special 10 holes, without putting 4 pigeons in any hole.
But one more pigeon will force us to put a 4th pigeon in one of the $g-10$
holes.  Hence, once we have $n = 3(g-10) +10 + 1 = 3g-19$ pigeons, there
will have to be 4 pigeons in some hole, and this is the minimum $n$ with
this property.

This would have been a nice problem for class or problem set, but is
trickier than we intended for a Quiz.  The intended answer was $n = 3g+1$,
which would be correct if we allowed the same sequence to occur several
times, \viz if we had asked for the smallest $n$ ensuring that any
\emph{multiset} of $n$ sequences had four elements with the same
distribution.  By the Generalized Pigeonhole Principle, in any multiset of
$m \ge 3g+1$ occurrences of sequences in $S$, there will be at least
$\ceil{m/g} \ge \ceil{(3g+1)/g} = 4$ occurrences of sequences with same
distribution.  Moreover, there is a multiset of $3g$ occurrences in which
no distribution occurs 4 times, namely, choose a multiset in which each
distribution occurs exactly 3 times.

We decided to leave full credit for the intended answer, since students
could easily overlook the trickiness and wind up with the ``wrong'' $3g+1$
answer---as almost all did---even though they clearly understood the
Generalized Pigeonhole Principle.

Actually, for either of these answers to be correct, it's also obviously
necessary that $\card{S} \ge 3g-19$ or $3g+1$, respectively.  But it's
easy to check that $\card{S} = 10^{90}$ is indeed much larger than
$3C(99,9)+1$.}

{\bf extra parts for the FINAL??:  }

\ppart Suppose instead of 4 sequences with the same distribution, we
wanted to guarantee $10^{100}$ sequences with the same distribution.
Show that $n = 10^{90} + 1$.

\solution{
The number of sequences is $10^{90} < 10^{100}$, so there aren't enough
sequences to yield the required number of digit distributions.  Hence only
sets of more than the number of sequences, of which there are none of
course, will, vacuously, have the required number of distributions.
}

\ppart Suppose instead of 4 sequences with the same distribution, we
wanted to guarantee $10^{9}$ sequences with the same distribution.  Show
that there is such an $n < 10^{90}$.

\solution{Just need to show that
\[
10^{9} (\text{\# of digit distributions}) + 1 \le (\text{\# of
sequences}).
\]

Can verify this using Stirling's approximation to estimate $\binom{99}{9}$;
somewhat extended but routine approximate calculation.  Probably also not
hard to verify w/o Stirling.}

\end{problemparts}
\end{examproblem}

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

\problemdata     
{}           
{counting, errors}              
{Friend of CEL} 		
{}
{}
%% 6.042 staffers,
%% I received the attached email message from a friend.  Locating the
%% error might make a good homework or classroom problem when we do
%% combinatorics.
%% Cheers,
%% Charles
\begin{examproblem}{0} 

FALSE COUNTING: NEED TO REWORD and FIGURE OUT THE SOLUTION!

I'm trying to calculate the number of possible combinations of hands
containing one pair.  I have two methods for doing this.  If I use
both methods where the hands have three cards (as you do in a poker
variant called "guts"), I get the same answer.  If i use both methods
for a standard 5-card poker hand, I get two different answers.  My
question is what error am I making and why aren't both methods right.

In my notation, choose(N, K) = N choose K = N! / ( (N-K)! * K! )


Method 1

A 5 card hand with only one pair consists of four ranks.  There are
choose(13,4) combos of ranks. Each of these ranks could be any of 4
suits, so 3 ranks have choose(4,1) different cards, and the fourth
rank has choose(4,2) different combos of cards.  Any of the 4 ranks
could be the pair, so multiply by 4.

\begin{verbatim}
total combos = choose(13,4) * choose(4,1) * choose(4,1) * choose(4,1)
* choose(4,2) * 4
total combos = 13!/(9! * 4!) * 4 * 4 * 4 * 6 * 4
total combos = (13 * 12 * 11 * 10)/(4 * 3 * 2) * 4 * 4 * 4 * 6 * 4
total combos = 13 * 12 * 11 * 10 * 4 * 4 * 4
total combos = 1,098,240
\end{verbatim}

Method 2

The pair could be any of 13 ranks. Each rank has choose(4,2) combos of
suits.  The third card could be any of 12 remaining ranks.  Each rank
has choose(4,1) different suits.  The fourth card could be any of 11
remaining ranks.  Each rank has choose(4,1) different suits.  The
fifth card could be any of 10 remaining ranks.  Each rank has
choose(4,1) different suits.

\begin{verbatim}
total combos = 13 * choose(4,2) * 12 * choose(4,1) * 11 * choose(4,1)
* 10 * choose(4,1)
total combos = 13 * 6 * 12 * 4 * 11 * 4 * 10 * 4
total combos = 13 * 12 * 11 * 10 * 4 * 4 * 4 * 6  <-- rearranging the
factors -- I am off by a factor of 6
total combos = 6,589,440
\end{verbatim}

OFF BY A FACTOR OF 6.

Which one is wrong? And what is wrong?

\solution{good question..}

\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

{\bf SERIES, in-class 7W }

\begin{examproblem}{0} 
We begin with two large glasses. The first glass contains a pint of
water, and the second contains a pint of wine. We pour 1/3 of a pint
from the first glass into the second, stir up the wine/water mixture
in the second glass, and then pour 1/3 of a pint of the mix back into
the first glass and repeat this pouring back-and-forth process a total
of $n$ times.

\begin{problemparts}
\problempart[10]
Describe a closed form formula for the amount of wine in the first glass
after $n$ back-and-forth pourings.

\solution[\vspace{4in}]{The state of the system of glasses/wine/water
at the beginning of a round of pouring and pouring back is determined
by the total amount of wine in the first glass.  Suppose at the
beginning of some round, the first glass contains $w$ pints of wine,
$0\leq w \leq 1$ and $1-w$ pints of water.  The second glass contains
the rest of the wine and water.

Pouring 1/3 pint from first glass to second leaves 2/3 pints of liquid and
$(2/3)w$ wine in the first glass, and 4/3 pints of liquid and 
$1 - (2/3)w$ wine 
in the second glass.  Pouring 1/3 pint back from second into first
transfers a proportion of (1/3)/(4/3) of the wine in the second glass into
the first.  So the round completes with both glasses containing a pint of
liquid, and the first glass containing
\[
(2/3)w + (1/4)(1- (2/3)w) = 1/4 + w/2
\]
pints of wine.  After one more round, the first glass contains
\[1/4 + (1/4 + w/2)/2 = 1/4 + 1/8 + w/2^2\]
pints of wine, and after $n$ more rounds
\[
\begin{array}{lll}
w/2^n + \Sigma_{i=1}^n (1/2)^{i+1} &=  w/2^n + (1/2)\Sigma_{i=1}^n
(1/2)^{i}\\
& = w/2^n + (1/2)(-1 + \Sigma_{i=0}^n (1/2)^{i})\\
& = w/2^n + (1/2)(-1 + (1 - (1/2)^{n+1})/(1 - 1/2))\\
& = w/2^n - 1/2 + 1 - (1/2)^{n+1}\\
& = w/2^n + 1/2 - (1/2)^{n+1}.
\end{array}
\]
Since $w=0$ initially, the pints of wine in the first glass
after $n$ rounds is
\[
1/2 - (1/2)^{n+1}.
\]
}

\problempart[5] What is the limit of the amount of wine in each glass as
$n$ approaches infinity?
\end{problemparts}

\solution[\vspace{2in}]{ The limiting amount of wine in the first
glass approaches 1/2 from below as $n$ approaches infinity.  In fact,
it approaches 1/2 no matter how the wine was initially distributed.
This of course is what you would expect: after a thorough mixing the
glasses should contain essentially the same amount of wine.  }
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}
\begin{examproblem}{0}

Eight men and seven women, all single, happen randomly to have
purchased single seats in the same 15-seat row of a theater.

\begin{problemparts} 

\ppart[5] What is the probability that the first two seats contain a
marriageable couple, i.e., a single man next to a single woman?

\solution[\vspace{3in}]{ Here's one way to do it.  There are
$\binom{15}{2} = 105$ possible pairs that could occupy the first two
seats, but only $8\cdot7 = 56$ of them are marriageable couples.  So
the probability is $56/105 = 8/15$.}

\ppart[5] What is the expected number of pairs of adjacent seats which
contain marriageable couples?  (For example, if the sequence of men
and women in the seats is
\begin{center}
MMMWMMMMWWWWWWM,
\end{center}
then there are four possible couples sitting in the pairs of adjacent
seats that start at the 3rd, 4th, 7th and 14th seats, respectively.)

\solution[\vspace{3in}]{Assign an indicator random variable
(i.e. value 0 or 1) to each event that we want to count, and then use
the expectation of sum formula to compute the expected number of
events that occur.

Let the random variable S be the number of pairs of seats
containing a marriageble couple; we want to find $\expect{S}$.  We can
solve this problem by introducing an indicator random variable $S_i$,
where $S_i = 1$ if there is a marriageable couple in seats $i$ and
$i+1$, and $S_i = 0$ otherwise.  So we have $S = \sum_{i=1}^{14} S_i$.

Since each seat is like any other, the probability that seats $i$ and
$i+1$ contain a marriageable couple is the same as in the first
part, $8/15$.  Thus
\[
\expect{S_i} = 1\cdot\Pr(S_i=1) + 0\cdot\Pr(S_i=0) = \frac{8}{15}.
\]
Finally, because expectation is linear,
\[
\expect{S} =  \sum_{i=1}^{14} \expect{S_i}  =  14\cdot \frac{8}{15}.
\]

Note that this approach works despite the fact that the indicator random
variables $S_i$ are not independent.  That's the beauty of linearity of
expectation!

}

\end{problemparts} 
\end{examproblem}
\fi


\iffalse
\textbf{EARLY DRAFT}

A Lab technician's job includes making a daily estimate of the percentage
of infected patients in her hospital whose infections are from bacteria
that have become penicillin-resistant.  For each strain of infecting
bacteria found in a day, the nursing staff will deliver a test tube
containing a culture of that strain and report that fraction of patients
infected with that strain.  The number of patients infected with more than
one of the kinds of bacteria is neglible.

One a typical day, the staff might deliver three tubes, and report to the
technician that the fraction of patients infected with each of the three
strains was 1/6, 1/20, and 1/11.  Suppose a fraction of
penicillin-resistant bacteria in the first strain

The technicians procedure is to 

She will do this by sampling a certain number of bacteria and testing
them.  Assume her sampling technique is good, \ie the bacteria are
sampled randomly and independently with replacement.  Let the
percentage of antibiotic-resistant bacteria be $b$.
\fi



\end{document}
