\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{graphics}
\usepackage[pdflatex]{graphicx}
\usepackage{psfig}

\input{../handouts/macros-course}

\newcommand{\tinyspace}{\ifshowsolutions\else\vspace{1in}\fi}
\newcommand{\smallspace}{\ifshowsolutions\else\vspace{2in}\fi}
\newcommand{\mediumspace}{\ifshowsolutions\else\vspace{3in}\fi}
\newcommand{\largespace}{\ifshowsolutions\else\vspace{4in}\fi}
\newcommand{\hugespace}{\ifshowsolutions\else\vspace{5in}\fi}
\newcommand{\pagespace}{\ifshowsolutions\else\newpage\fi}
\newcommand{\nextproblem}{\newpage}


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

\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

%\newcommand{\problem}{\newpage\textbf{Problem.\ }}
%\newcommand{\bparts}{}
%\newcommand{\eparts}{}
%\newcommand{\ppart}{\textbf{Part.\ }}
%\newcommand{\solution}[1]{\textbf{Solution.\ } #1}
\newcommand{\ksource}[1]{\ifshowsolutions\textsc{Source: #1}\par\else\fi}
\newcommand{\ktopics}[1]{\ifshowsolutions\textbf{Topics: #1}\par\else\fi}
\newcommand{\kparen}[1]{\ensuremath{\left( #1 \right)}}
\newcommand{\kbrack}[1]{\ensuremath{\left[ #1 \right]}}
%\newcommand{\floor}[1]{\ensuremath{\left\lfloor #1\right\rfloor}}
\newcommand{\kth}{\ensuremath{^{\textrm{th}}}}
\newcommand{\pts}[1]{\ensuremath{[#1\mathrm{\ points}]}}

\renewcommand{\hint}[1]{\par\textbf{Hint:} #1}

%\newcommand{\set}[1]{\ensuremath{\{#1\}}}

\newcommand{\kproblem}[1]{\newpage\ifshowsolutions[#1]\fi\problem}

\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}
\newcommand{\mquote}[1]{\mathify{\textrm{``$#1$''}}}
\newcommand{\mdash}{\mathify{\textrm{-}}}
\newcommand{\where}{{\ \mid \ }}
\newcommand{\size}[1]{\mathify{\left| #1 \right|}}
\newcommand{\equivalent}{\mathify{\ \Longleftrightarrow \ }}
\newcommand{\ifandonlyif}{\equivalent}
\renewcommand{\prob}[1]{\mathify{\textrm{Pr}\left[\, #1 \,\right]}}
\newcommand{\compliment}[1]{\overline{#1}}
\newcommand{\Ex}{\text{Ex}}

\newcommand{\fmod}{\ensuremath{~\mathrm{mod}~}}

\newcommand{\ssol}[2]{\ifshowsolutions #1 \else #2 \fi}

\newcommand{\kignore}[1]{}


\begin{document}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\newcommand{\coverpage}[1]{\ifshowsolutions \else #1 \fi}

\def\ps@myheadings{%
\let\@oddfoot\@empty\let\@evenfoot\@empty
\def\@evenhead{\thepage\hfil\slshape\leftmark}%
\def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
\let\@mkboth\@gobbletwo
\let\sectionmark\@gobble
\let\subsectionmark\@gobble
}

\makeatother

\askaboutsolutions


\ifshowsolutions
\pfinalsol{1}{December, 2000}
\else
\pfinal{1}{December 12, 2000}
\fi

%% \exam{ Practice Final Exam}{December 12, 2000}



%\titlebar

\coverpage{
\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{c@{\hskip 3em}c@{\hskip 3em}c@{\hskip 3em}c}
Andrej & Wes & Dwaine & Andrew \\
\ &&& \\
Moses & Zulfikar & George & Nitin
\end{tabular}
\end{center}

\medskip

\noindent Write the hour at which your Friday tutorial began \brule{3em}

\medskip

\begin{closeitemize}
\item This quiz is open book/notes.  
  
\item This quiz is 18 pages long; please check that you have all
  pages.
  
\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.

\item You may assume any of the results presented in class or in the
  lecture notes, but you must \textit{explicitly} cite which results
  you are using and how you are using them.
  
\item Show your work, as partial credit will be given.  You will be
  graded not only on the correctness of your answer, but also on the
  clarity with which you express it.

\item {\bf Be neat and write legibly}.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\medskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  12 & & \\ & & & \\\hline & & &\\
2 &  8 & & \\ & & & \\\hline & & &\\
3 &  10 & & \\ & & & \\\hline & & &\\
4 &  10 & & \\ & & & \\\hline & & &\\
5 &  12 & & \\ & & & \\\hline & & &\\
6 &  12 & & \\ & & & \\\hline & & &\\
7 &  10 & & \\ & & & \\\hline & & &\\
8 &  12 & & \\ & & & \\\hline & & &\\
9 &  10 & & \\ & & & \\\hline & & &\\
10 &  12 & & \\ & & & \\\hline & & &\\
11 &  14 & & \\ & & & \\\hline & & &\\
12 &  12 & & \\ & & & \\\hline & & &\\
13 &  10 & & \\ & & & \\\hline & & &\\
14 &  12 & & \\ & & &\\
\hline
\hline
& & &\\
Total & 156 & & \\
& & &\\
\hline
\end{tabular}
\end{center}


\newpage
}

\setcounter{page}{1}

\begin{problems}


%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/spring99sol.tex
% Topic: Graphs, Recursive Definitions

\kproblem{induction2} 
\pts{12}
\ksource{s99 ps3}
\ktopics{Induction, Graphs, Recursive Definitions}
This problem concerns Hamiltonian paths
in $n$-cubes.  A {\em Hamiltonian path} in a graph is a path
traversing every vertex in the graph exactly once.  The $n$-cube is
defined on page 448 of Rosen (p. 441 in ed. 3).  (Rosen also uses the
name $Q_n$ for an $n$-cube.)  However, the following recursive
definition of an $n$-cube is equivalent to the one given in Rosen, but
may simplify your solutions.  A 0-cube is a single vertex.  An
$(n+1)$-cube consists of two $n$-cubes with corresponding vertices
joined by edges.  For example, a standard cube (here, called a 3-cube) is two squares with
corresponding corners joined.

\begin{problemparts}
\ppart Draw a 4-cube.
\pts{2}

\smallspace
\solution{
\bigskip
\centerline{\resizebox{!}{2.0in}{\mbox{\includegraphics{figures/fourcube}}}}
\bigskip
}

\ppart In your drawing, highlight a Hamiltonian path.
\pts{2}

\solution{
}

\ppart Use induction on $n$ to prove that an $n$-cube has a
Hamiltonian path for all $n \geq 2$.
\pts{8}

\largespace
\solution{
The proof is by induction.  Let $P(n)$ be the proposition
that an $n$-cube has a Hamiltonian path.  In the base case, $P(2)$
is true, because a 2-cube is itself a cycle.

In the inductive step, assume that an $n$-cube has a Hamiltonian
path to prove that an $(n+1)$-cube has a Hamiltonian path.
Regard an $(n+1)$-cube as two $n$-cubes with corresponding vertices
joined.  The first $n$-cube has a Hamiltonian path $H$ by
induction, and there is a matching Hamiltonian path $H'$ in the
second $n$-cube.

Consider the Hamiltonian path in $H$ in the first $n$-cube.  
Say it traverses the vertices
of the first cube in the order $u, v, ... ,f$.  Then, to construct the 
Hamiltonian path in the $(n+1)$-cube, start out at $u$, and traverse the path
$H$ all the way through to $f$.  Then cross edge $(f,f')$ from the first
$n$ cube to the second.  Now traverse the path $(f',...,v',u')$ in $H'$.  The
path we have just traed out hit every node in the $(n+1)$-cube, and thus it
is a Hamiltonian path.
}
\end{problemparts}



\kignore{
%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: ? pset3/spring97.tex
% Topic: Fibonnacci Numbers, Strong Induction

\kproblem{induction5}
\pts{10}
\ksource{s97 ps3}
\ktopics{Fibonnacci Numbers, Strong Induction}
%
Show that the Fibonnacci number $f_n$ satisfy $f_n \leq 2^n$ using
strong induction by filling in the blanks below in the proof
reasoning.

E.g.:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=\=\=    \kill
Let $P(n) = F_n \leq 2^n$ \\
Prove: $\forall n \geq 0 (P(n))$\\
1. (Base) $P(0)$
\> \> \> \> \>  $F_0 = 0 \leq 2^0$ \\ %[[[students can do this]]]
2. (Base) $P(1)$ 
\> \> \> \> \>  $F_1 = 1 \leq 2^1$ \\ %[[[students]]]
3. (Inductive step) $\forall n \geq 1 [(\forall  i, 0 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$\\
\> 1. Fix $n \geq 1$ \\
\> 2. $(\forall  i, 0 \leq i \leq n (P(i))) \Rightarrow P(n+1)$ \\
\> \> 1. Assume $\forall  i, 0 \leq i \leq n (P(i))$ \\
\> \> 2. $P(n+1)$ \\
\> \> \> 1. $F_n \leq 2^n$
         \> \> \ssol{Inductive hypothesis 3.2.1}{\underline{\vbox{\vskip 1.5em\hbox{\hskip 2in}}}} \\ 
\> \> \> 2. $F_{n-1} \leq 2^{n-1}$
         \> \> \ssol{Inductive hypothesis 3.2.1}{\underline{\vbox{\vskip 1.5em\hbox{\hskip 2in}}}} \\ %[[[students]]]
\> \> \> 3. $F_{n+1} = F_n + F_{n-1}$
         \> \> \ssol{Definition of Fibonacci numbers}{\underline{\vbox{\vskip 1.5em\hbox{\hskip 2in}}}} \\ %[[[students]]]
\> \> \> 4. $F_{n+1}\leq 2^n + 2^{n-1}$ 
         \> \> \ssol{Plug the inequalities into the equation}{\underline{\vbox{\vskip 1.5em\hbox{\hskip 2in}}}} \\ %[[[students]]]
\> \> \> 5. $F_{n+1} \leq 2^{n+1}$ \\
\> \> \> \> 1. $2^{n-1} \leq 2^n$
            \> Algebra \\ 
\> \> \> \> 2. $2^n + 2^{n-1} \leq 2^{n+1}$
            \> Algebra \\ 
\> \> \> \> 3. QED 
            \> \ssol{Algebra (3.3.4 and 3.3.5.2)}{\underline{\vbox{\vskip 1.5em\hbox{\hskip 2in}}}} \\ %[[[students]]]
\> \> \> 6. QED
         \> \> Definition of $P(n+1)$ \\ 
\> \> 3. QED
       \> \> \> \ssol{Implication}{\underline{\vbox{\vskip 1.5em\hbox{\hskip 2in}}}} \\ %[[[students]]]
\> 3. QED
    \> \> \> \> \ssol{UG}{\underline{\vbox{\vskip 1.5em\hbox{\hskip 2in}}}} \\ %[[[students]]]
4. QED
\> \> \> \> \> \ssol{Strong induction}{\underline{\vbox{\vskip 1.5em\hbox{\hskip 2in}}}} %[[[students]]]
\end{tabbing}
]]]
}



%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/spring97.tex, pset3/spring97sol.tex
% Topic: False Proofs, Well Ordering, Induction, 

\kproblem{induction7}
\pts{8}
\ksource{s97 ps3}
\ktopics{False Proofs, Well Ordering, Induction}
%
Find the flaws in the following ``proofs;'' circle the step in which
an error was made, and explain the problem.

\begin{problemparts}

\ppart\pts{4}
CLAIM: $a^n = 1$ for all nonnegative
integers $n$, whenever $a$ is a nonzero real number. 

BASIS STEP: $a^0 = 1$ is true by the definition of $a^0$.

INDUCTIVE STEP: Assume that $a^k = 1$ for all nonnegative integers k with 
$ k \leq n$.  Then note that 
\( a^{n+1} = \frac{a^n \cdot a^n}{a^{n-1}} = \frac{1 \cdot 1}{1} = 1.
\)

\smallspace
\solution{
The flaw is that we should prove both $n=0$ and $n=1$ 
as bases cases because the inductive step uses the 
previous two values of $n$.
Clearly $a^1=1$ is not true, unless $a=1$,
and therefore the proof is wrong.
}

\ppart\pts{4} CLAIM: $\sqrt{2}$ is rational.

PROOF: Well-ordering.  Let $S$ be the set of all rational numbers
greater than or equal to $\sqrt{2}$.  This set contains a least
element $r$ by well-ordering.  If this element is not $\sqrt{2}$, then
there is another rational element between $\sqrt{2}$ and $r$ (by
denseness of the rationals), implying $r$ is not the smallest, a
contradiction.  Thus we must have $r=\sqrt{2}$.

\solution{
The flaw is that the well-ordering principle does not 
hold for the rationals, so we cannot use it to conclude 
that the above set has a minimum.
}

\kignore{
\newpage
\ppart\pts{4} CLAIM: every number can be described in a phrase of less
than eighty characters.  

PROOF: Well-ordering.  Let $S$ be the set of numbers that
cannot be described in a phrase of less than eighty characters.  If it
is nonempty, it contains a smallest element.  This is ``The smallest
number that cannot be described in less than eighty chracters.''  This
is a description of that number in less than eighty characters, a
contradiction.  Since the assumption that $S$ was nonempty yields a
contradiction, $S$ must be empty and the claim is proved.

\smallspace
\solution{
The flaw in the above proof is that the set of numbers that 
can be described in less than eighty characters, 
is not a well-defined set.
}
}

\end{problemparts}



\kignore{
%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset4/fall99.tex, pset4/fall99sol.tex
% Topic: Posets, Well Ordering

\kproblem{induction8}\pts{12}
\ksource{f99 ps4}
\ktopics{Posets, well ordering}

\textbf{I think they may have seen this one. - Kyle}

Let $R$ be the lexicographic ordering of strings of symbols
from a totally ordered alphabet as defined in Rosen p. 417.

\begin{problemparts}

\ppart\pts{8} Prove that $R$ is a total order.

\largespace
\solution{
We first show that $R$ is a partial order.
Reflexivity is clear from the definition. To show antisymmetry,
suppose that $a_1\ldots a_m<b_1\ldots b_n$, and let $t=\min(m,n)$. This
means that either $a_1\ldots a_t = b_1\ldots b_t$ and $m<n$, so that
$b_1\ldots b_n \not <a_1\ldots a_m$, or else $a_1\ldots a_t<b_1\ldots b_t$,
so that $b_1\ldots b_t \not < a_1\ldots a_t$ and hence again 
$b_1\ldots b_n\not < a_1\ldots a_m$. Finally for transitivity, suppose that
$a_1\ldots a_m<b_1\ldots b_n<c_1\ldots c_p$
. Let $t=\min(m,n)$, $r=\min(n,p)$,
$s=\min(m,p)$, and $l=\min(m,n,p)$. Now if 
$a_1\ldots a_l<b_1\ldots b_l<c_1\ldots c_l$
then clearly $a_1\ldots a_m<c_1\ldots c_p$. Otherwise, without loss
of generality we may assume that $a_1\ldots a_l=b_1\ldots b_l$. If $l=t$
then $m<n$ and $m\le p$. Furthermore, either $b_1\ldots b_r<c_1\ldots c_r$
or $b_1\ldots b_r=c_1\ldots c_r$ and $n<p$. In the former case, if 
$r>l$, then since $p>m$ we have $a_1\ldots a_m<c_1\ldots c_p$, whereas if 
$r=l$ then $a_1\ldots a_l<c_1\ldots c_l$. In the latter case, 
$a_1\ldots a_s=c_1\ldots c_s$ and $m<p$, so again 
$a_1\ldots a_m<c_1\ldots c_p$. If $l<t$, then we must have 
$b_1\ldots b_l<c_1\ldots c_l$, whence $a_1\ldots a_l<c_1\ldots c_l$.
Finally, the fact that $R$ is a total order follows trivially from the 
definition of a lexicographic order and noticing
that the strings of symbols are taken from a totally ordered alphabet.
}

\ppart\pts{4} Prove that neither $R$ nor $R^{-1}$ is a well-ordering.

\mediumspace
\solution{
Consider the alphabet $\{a,b\}$ with $a\preceq b$. Then $R$ is not
a well ordering since $\{b,ab,aab,aaab,aaaab,\ldots\}$ has no least element.
Moreover, $R^{-1}$ is not a well-ordering since $\{a,aa,aaa,aaaa,\ldots\}$
has no least element. 
%Consider the alphabet 
%$\{\ldots,a_{-2},a_{-1},a_0,a_1,a_2,\ldots\}$, 
%with the ordering 
%$\ldots\preceq a_{-1}\preceq a_0\preceq a_1\preceq\ldots$. 
%Then $R$ is not a well-ordering, since the set of strings, 
%$\{a_{-1},a_{-2},a_{-3},\ldots\}$ does not have a least element.
%Moreover, the set of strings $\{a_0,a_1,a_2,\ldots\}$ 
%does not have a least element under the ordering $R^{-1}$, and
%therefore $R^{-1}$ is not a well-ordering either.
}
\end{problemparts}
}



%\endinput

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/fall95.tex, pset3/fall95sol.tex
% Topic: Well Ordering (gcd, lcm)

\kproblem{wellordering1}\pts{10}
\ksource{f95 ps3}
\ktopics{Well Ordering (gcd, lcm)}
The least common multiple of two natural numbers, $m$ and $n$ is
defined to be the smallest natural number $k$ such that $m|k$ and
$n|k$. It is denoted by $lcm(m,n)$.


\bparts

\ppart\pts{5} Using well-ordering, prove that every pair of natural
numbers has a least common multiple.

% kdmc: Should we include a definition of gcd here?  I don't think so.

\mediumspace
\solution{
Let $m$ and $n$ be any two natural numbers.  Let $M$ be the set of
multiples of $m$ and $N$ the multiples of $n$. Consider $M \cap N$.
It is nonempty since it contains $mn$. By the well-ordering principle
it contains a least element which is the least common multiple of $m$
and $n$. Hence every pair of natural numbers has a least common
multiple.
}


\ppart\pts{5} Say $a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots
p_n^{\alpha_n}$ and $b=p_1^{\beta_1}p_2^{\beta_2}\cdots p_n^{\beta_n}$
where the $p_i$ are prime and the $\alpha_i$ and $\beta_i$ are
non-negative (i.e., possibly zero).  Express the least common multiple
of $a$ and $b$ in terms of these prime factorizations of $a$ and $b$.

\mediumspace
\solution{
Let $a = {\displaystyle \prod}_i p_i^{\alpha_i}$ and $b =
{\displaystyle \prod}_i p_i^{\beta_i}$ where $p_1, p_2 \ldots$ are the
primes in increasing order. Following Theorem 7.12 in Handout 13, Notes 4, it was shown that $gcd(a,b) =  {\displaystyle \prod}_i p_i^{\min(\alpha_i,\beta_i)}$. By an identical argument it can be seen that $lcm(a,b) =  {\displaystyle \prod}_i p_i^{\max(\alpha_i,\beta_i)}$. Now, from the fact that for any $\alpha$ and $\beta$, $\alpha + \beta = \max(\alpha,\beta) +  \min(\alpha,\beta)$, it follows that  $a\cdot b=gcd(a,b)\cdot lcm(a,b)$.
}

\eparts



%%% pigeonhole principle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{pigeonhole1}\pts{10}
\ksource{Kyle's brain, inspired by a trip to the
  Galleria}\ktopics{Pigeonhole principle}
%
For their annual convention, the members of the MIT Antisocial League
rent out the cafeteria at the CambridgeSide Galleria.  The cafeteria
is an $n\times n$ grid of cells, each cell containing exactly one
table and a \textit{single} associated chair.  A chair can be
positioned around its table to face in one of four directions,
corresponding to the axes of the grid.

Due to space considerations, every attendee must sit at a chair.  But,
since this is the Antisocial League, no seated person can directly
face another occupied table (i.e., there can be no one sitting at a
table in a person's direct line of sight).  Use the pigeonhole
principle to prove that this requirement cannot be satisfied if $4n+1$
members attend.

\mediumspace
\solution{We use the pigeonhole principle to prove the theorem.
  Orient a representation of the grid in some canonical way with one
  axis pointing left-right, and the other pointing up-down.
  
  There are four directions in which people can face.  As a result, by
  the generalized pigeonhole principle, at least $n+1$ people must be
  facing in some direction.  Without loss of generality, assume this
  is downwards.
  
  Create $n$ pigeonholes from the columns of the grid.  By the PP, if
  there are $n+1$ attendees facing downwards, at least two must be in
  the same column, so clearly one must be directly facing another
  occupied table.
  
  It is likely that equality is not achieved (which would be proved by
  demonstrating an arrangement of $4n$ people in which no one directly
  faced another occupied table).  This suggests a stronger theorem can
  be proven.  The best we can do so far is $4n-4$; try to figure out
  such a solution.}




\kignore{
\kproblem{counting1}\pts{5}
\ksource{Nancy/Carl/Victor}
\ktopics{Counting, Injections, Surjections}
Which of the following is the cardinality of the set of all
surjections from a set $A$, where $|A|=n$, and $B$, where $|B|=m$.
\begin{description}\itemsep 0\baselineskip
\item[(a)] $m^n$
\item[(b)] $\frac{m!}{(m-n)!}$
\item[(c)] ${n \choose m} m^{n-m} m!$
\item[(d)] None of the above.
\end{description}

\solution{%
  (d) None of the above.}
}



\kignore{
%%% summations, asymptotics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{summations1}\pts{16}
\ksource{Kyle's brain, modified from PS6 n4}
\ktopics{Summations, asymptotics}
Prove that the ``average''
number of perfect square\footnote{$x$ is a perfect square if there is
  some natural number $y$ such that $y^2=x$.} divisors of a number of
size $n$ is bounded from above by a constant.  More formally, let
$t(n)$ be the number of divisors of the number $n$ that are themselves
perfect squares, and let \[ T(n)=\frac{1}{n}\sum_{j=1}^n t(j) \] be
the average number of perfect square divisors of all numbers less than
or equal to $n$.  Show that there exists a constant $c$ such that for
all $n$, $T(n)\leq c$.  \hint{Let the function $f(i,j)=1$ if $i^2$ is
  a divisor of $j$, and 0 otherwise.  What do the row and column sums
  of $f(i,j)$ mean?}

\largespace
\solution{Consider the image of the function $f(i,j)$ as a matrix
  whose rows and columns correspond to values of $i$ and $j$
  respectively; that is, element $(i,j)$ of the matrix denotes whether
  or not $i^2$ divides $j$.
  \[
  \begin{array}{cc|ccccccccccccccccc}
    &&&&&&&&&&& j\\
    &f(i,j) & 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline
    &1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\
    i&2&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&\cdots\\
    &3&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\
    &4&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\\
    &\vdots &&&&&&&&&& \vdots
  \end{array}
  \]
  Notice that the sum of each column $j$ corresponds to the number of
  perfect square divisors of the number $j$ and the sum of each row
  $i$ corresponds to the number of multiples of the number $i^2$.  As
  a result, the number of multiples of $i^2$ between $1$ and $n$ can
  be compactly represented as $\lfloor n/i^2\rfloor$.
  
  It follows that
  \begin{eqnarray*}
    T(n)
    &=&\frac{1}{n}\sum_{j=1}^n t(j) \\
    &=&\frac{1}{n}\sum_{i=1}^{\floor{\sqrt{n}}} \sum_{j=1}^n f(i,j) \\
    &=&\frac{1}{n}\sum_{i=1}^{\floor{\sqrt{n}}} \floor{\frac{n}{i^2}}
  \end{eqnarray*}
  $T(n)$ can then be bounded from above as follows:
  \begin{eqnarray*}
    T(n)
    &\leq&\frac{1}{n}\sum_{i=1}^{\floor{\sqrt{n}}}\frac{n}{i^2} \\
    &=&\sum_{i=1}^{\floor{\sqrt{n}}}\frac{1}{i^2} \\
    &\leq&1+\int_{1}^{\sqrt{n}}\frac{1}{x^2}dx \\
    &=&1+\frac{\sqrt{n}-1}{\sqrt{n}}\leq 2
  \end{eqnarray*}
  }
}




\kignore{
\kproblem{recurrences2}
\pts{12}
\ksource{Kyle}
\ktopics{Recurrences}
\ppart 
\pts{6}
Iterate the following recurrence to find a pattern:
\[ T(n)=a_0 T(n/b_0) + a_1 T(n/b_1) + f(n) \]
where $T(n/(b_0^i b_1^{m-i}))=c$ for all $i\in\set{1,\ldots,m}$ with
$a_{\set{0,1}}$, $b_{\set{0,1}}$, and $c$ all constant.  Demonstrate a
non-recurrent formula that \textit{may} have summations in it.

\solution{Denote $g(x)=T(n/x)$, so $g(b_0^i b_1^{m-i})=c$.  Then:
\begin{eqnarray*}
T(n)
&=& a_0 g(b_0) + a_1 g(b_1) + f(n) \\
%
&=& a_0^2 g(b_0^2) + 2a_0 a_1 g(b_0 b_1) + a_1^2 g(b_1^2) \\
&& + f(n) + \kbrack{a_0 f(n/b_0) + a_1 f(n/b_1)} \\
%
&=& a_0^3 g(b_0^3) + 3a_0^2 a_1 g(b_0^2 b_1) + 3a_0 a_1^2 g(b_0 b_1^2)
 + a_1^3 g(b_1^3) \\
&& + f(n) + \kbrack{a_0 f(n/b_0) + a_1 f(n/b_1)} + \kbrack{a_0^2
f(n/a_0^2) + 2a_0 a_1 
f(n/(b_0b_1)) + a_1^2 f(n/a_1^2)} \\
%
&\vdots& \\
%
&=& \sum_{i=0}^m \kparen{\binom{m}{i} a_0^i a_1^{m-i} g(b_0^i
b_1^{m-i})} \\
%
&& + \sum_{j=0}^m \sum_{i=0}^j \kparen{\binom{j}{i} a_0^i a_1^{j-i}
f(n/(b_0^i b_1^{j-i}))} \\
%
&=& c(a_0+a_1)^m \\
&& + \sum_{j=0}^m \sum_{i=0}^j \kparen{\binom{j}{i} a_0^i a_1^{j-i}
f(n/(b_0^i b_1^{j-i}))}
%
\end{eqnarray*}}

\newpage
\ppart 
\pts{6}
Find asymptotically tight bounds for the following recurrence:
\[ T(n)=8T(n/2) + n^3\left(\log n\right)^2 \]
given that $T(1)=1$.  You may assume $n$ is a power of 2.  Note that
the master theorem \textit{does not apply} to this recurrence.

\solution{Use the first part, with $a_0=4$, $a_1=4$, $b_0=b_1=2$,
  $m=\log n$, $c=1$, and $f(n)=n^3\log^2 n$.  (Note that we can't take
  $a_0=0$ or $a_1=0$, since $0^0$ is indeterminate; we could, however,
  have used any other $a_0$ and $a_1$ such that $a_0+a_1=8$.)
  
  Plugging and chugging:
  \begin{eqnarray*}
    T(n)
    &=& 4T(n/2) + 4T(n/2) + n^3\log^2 n \\
    &=& 1(4+4)^{\log n} + \sum_{j=0}^{\log n} \sum_{i=0}^j \kparen{\binom{j}{i}
      4^j (n/2^j)^3\log^2 (n/2^j)} \\
    &=& n^3 + \sum_{j=0}^{\log n} \kparen{8^j (n/2^j)^3\log^2 (n/2^j)} \\
    &=& n^3 + n^3\sum_{j=0}^{\log n} \kparen{\log^2 (n/2^j)} \\
    &=& n^3 + n^3\sum_{j=0}^{\log n} \kparen{\log^2 n-2j\log n+j^2} \\
    &=& n^3 + n^3\kparen{\log^3 n+ \log^2 n} - 2n^3\log n\sum_{j=0}^{\log n} j
    + n^3 \sum_{j=0}^{\log n} j^2 \\
    &=& n^3 + n^3\kparen{\log^3 n+ \log^2 n} - n^3\kparen{\log^3 n+\log^2 n}
    + n^3 \sum_{j=0}^{\log n} j^2 \\
    &=& n^3 + n^3 \sum_{j=0}^{\log n} j^2 \\
  \end{eqnarray*}
  We must bound the last part, $\sum_{x=0}^{\log n} x^2$, by the integral method:
  \begin{eqnarray*}
    \sum_{x=0}^Y x^2
    &\leq& \int_0^Y (x+1)^2 dx \\
    &=& \frac{1}{3}(x+1)^3 \Big|_0^Y \\
    &=& \frac{1}{3}(Y+1)^3-\frac{1}{3}
  \end{eqnarray*}
  and
  \begin{eqnarray*}
    \sum_{x=0}^Y x^2
    &\geq& \int_0^Y x^2 dx \\
    &=& \frac{1}{3}x^3\Big|_0^Y \\
    &=& \frac{1}{3}Y^3
  \end{eqnarray*}
  so the last term is asymptotally bounded by $n^3\log^3 n$; thus, the
  entire summation is $\Theta(n^3\log^3 n)$.

  }
}




\kproblem{recurrences3}
\pts{12}
\ksource{Kyle}
\ktopics{Homogeneous/inhomogeneous LDE}
%[[[This is really funny.]]]
One of the top \textit{ore-cum-food} firms, Amalgamated Steel and
Spice, has been receiving complaints based on the spreading rumor that
one of its products---Happy-O's with Nuts---actually has rusting iron
filings instead of pecan shavings.

During the time in which the X-Files were closed, Mulder and Scully
were sent in to investigate.  With the help of (the suave) Langley and
(the mighty) Frohike, they were able to gather enormous amounts of
data concerning a conspiracy against the American people to hide the
Truth behind this supposed ``mistake.''

\bparts

\ppart\pts{2} Our heroes find that a new complaint on any particular
day generates one new complaint on the following day and six new
complaints on the day after that.  Write a recurrence $T(n)$ valid for
$n\geq 3$ that represents the number of new complaints on day $n$.

\tinyspace
\solution{$T(n)=T(n-1)+6T(n-2)$}

\ppart\pts{4} On day $1$, 0 complaints are generated; on day $2$, 30
complaints are generated (i.e., $T(1)=0$ and $T(2)=30$).  Find a
closed form for the recurrence in the previous part.

\largespace
\solution{The characteristic equation is $x^2-x-6=0$, whose roots are
  $3$ and $-2$.  The general solution is then of the form
  $T(n)=A3^n+B(-2)^n$.  Now we solve for the constants by plugging in
  the initial conditions: $0=3A-2B$ and $30=9A+4B$ imply that $A=2$ and
  $B=3$.  So, the final solution is $T(n)=2\cdot 3^n+3(-2)^n$.}

\newpage
\ppart\pts{6} Scully does some more digging and notices that $6n$
additional complaints are filed spontaneously on day $n$ for $n\geq
1$.  Find new initial conditions based on this new information, show
an inhomogeneous recurrence, and find a closed-form solution to it.

\largespace
\solution{The general solution to the inhomogeneous part remains as
  before; now, however, we have the initial conditions $T(1)=6$ and
  $T(2)=42$, and an inhomogeneous part $n$.  We guess a linear
  solution $an+b$, and plug in the initial conditions:
  \begin{eqnarray*}
    an+b
    &=&an+b+6(an+b)+6n  \\
    0
    &=&(6a+6)n+6b
  \end{eqnarray*}
  So $6a+1=0\Rightarrow a=-1$ and $6b=0\Rightarrow b=0$ for our
  particular solution $-n$.  So, we plug in and solve for the
  constants:
  \begin{eqnarray*}
    T(1) = 6 &=& 3A - 2B - 1 \\
    T(2) = 42 &=& 9A + 4B - 2
  \end{eqnarray*}
  The solutions to this system are $A=58/15$ and $B=23/10$.  So, our
  complete solution is $T(n)=(58/15)3^n + (23/10)(-2)^n - n$.}

\eparts




\kignore{
%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/fall96.tex, Rosen 6.5, Problem 32
% Topic: Equivalence Relations

\kproblem{relations4}
\pts{10}
\ksource{f96 ps3}
\ktopics{Equivalence Relations}
Each bead on a bracelet with three beads is either red, white, or
blue as illustrated in the example shown. Define the relation {\em R}
between bracelets as follows: $(B_1,B_2)$, where $B_1$ and $B_2$ are
bracelets, belongs to $R$ if and only if $B_2$ can be obtained from
$B_1$ by rotating it or rotating it and then reflecting it.

%\begin{figure}[h]
%\centerline{\psfig{figure=bead.ps,height=1in}}
%\end{figure}

\bparts

\ppart Show that $R$ is an equivalence relation.

\mediumspace

\ppart What are the equivalence classes of $R$?

\mediumspace

\eparts
}



\kignore{
%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: kdmc
% Topic: Relations

\kproblem{relations7}\pts{12}
\ksource{kdmc}
\ktopics{Relations}
Let $R$ be a binary relation on the set
$\naturals$ of natural numbers.  Define $R$ as follows: $\forall (a,
b) \in \naturals \times \naturals\ \ (a, b) \in R \iff a \equiv b
\fmod 4$.

\bparts
\ppart\pts{3} Prove that $R$ is $transitive$.
\mediumspace

\ppart\pts{3} Prove that $R$ is $symmetric$.
\mediumspace

\eparts
}



\kignore{
%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: kdmc
% Topic: Relations

\kproblem{relations7}\pts{12}
\ksource{kdmc}
\ktopics{Relations}
Let the relations $R$ and $S$ be binary relations on the set
$\naturals$ of natural numbers.  Define $R$ as follows: $\forall (a,
b) \in \naturals \times \naturals\ \ (a, b) \in R \iff a \equiv b
\fmod 4$.  Define $S$ as follows: $\forall (a, b) \in \naturals \times
\naturals\ \  (a, b) \in R \iff 2^{a} = b$.

\bparts
\ppart\pts{3} Prove that $R$ is $transitive$.
\smallspace

\ppart\pts{3} Prove that $R$ is $symmetric$.
\smallspace

\ppart\pts{3} Find $R \intersect S$.
\smallspace

\ppart\pts{3} Let $T = S \composition R$. \textbf{??? what is the rest
of the question?}
\smallspace

\eparts
}




\newcommand{\transto}[2]{\texttt{#1} \ensuremath{\longrightarrow} \texttt{#2}}
\newcommand{\transfrom}[2]{\texttt{#1} \ensuremath{\longleftarrow} \texttt{#2}}
\newcommand{\sm}[2]{\texttt{#1(#2)}}
\newcommand{\sms}[1]{\texttt{#1}}
\kproblem{statemachines1}\pts{12} 
\ksource{Nancy}
\ktopics{State machines, graphs}
%
Consider a state machine whose state is a directed graph with the
5-element vertex set $V=\set{1,2,3,4,5}$.  The transitions allowed by
the state machine are the following:
%
\begin{itemize}
\item \sm{add-out}{a,b} (\sms{a},\sms{b} distinct vertices):\par Can
  occur if \sms{a} has no incoming edges.\par Effect is to add the
  edge \transto{a}{b}.
\item \sm{add-in}{a,b} (\sms{a}, \sms{b} distinct vertices):\par Can
  occur if \sms{a} has no outgoing edges.\par Effect is to add the
  edge \transto{b}{a}.
\item \sm{trans}{a,b,c} (\sms{a}, \sms{b}, \sms{c} distinct
  vertices):\par Can occur if there is an edge from \sms{a} to \sms{b}
  and another from \sms{b} to \sms{c}.\par Effect is to add the edge
  \transto{a}{c}.
\end{itemize}
%
\bparts

\ppart\pts{6} We want to prove that, eventually, a transitively closed
graph is produced.  Assume that we are considering a ``live''
execution, i.e. one that does not stop as long as some transition is
possible.

Define a termination function that can be used to prove this
eventuality property.  Argue that it satisfies the properties of a
termination function.

\solution{$f(n)=n(n-1)-\#\textrm{edges}$ is such a termination
  function.  Without remove and reverse, every transition adds an edge
  to the graph, decreasing this function.  When no transition is
  possible, the graph must be transitively closed, because we have an
  explicit transitive-closure step.}

\kignore{
\ppart\pts{6} The line graph in the opposite direction ($1\longleftarrow
2\longleftarrow 3\longleftarrow 4\longleftarrow 5$).

\solution{Reachable: reverse(1), reverse(2), reverse(1), reverse(3),
  reverse(2), reverse(1), reverse(4), reverse(3), reverse(2),
  reverse(1).}
}

\newpage Consider adding the following transitions to our state
machine:
%
\begin{itemize}
\item \sm{remove}{a,b} (\sms{a}, \sms{b} vertices):\par Can occur if
  there is an edge from \sms{a} to \sms{b}.\par Effect is to remove
  the edge.
\item \sm{reverse}{a} (\sms{a} vertex):\par Can occur if either all
  the edges incident upon \sms{a} are incoming, or all are
  outgoing.\par Effect is to reverse the direction of all edges
  incident on \sms{a}.
\end{itemize}
%
Initially, the state is that of the ``linear graph''
($\sms{1}\longrightarrow \sms{2}\longrightarrow \sms{3}\longrightarrow
\sms{4}\longrightarrow \sms{5}$).
%
\ppart\pts{6} Consider the graph that is the same as the line graph
above, but with the additional edge \transto{5}{1}.  Is this state
reachable?  If it is, then describe an execution that reaches it;
otherwise, state an invariant that can be used to show that the state
cannot be reached.  Such an invariant must be provable by induction
(or the Invariant Theorem).  Instead of giving a proof of the
invariant, just state key reasons.

\tinyspace
\solution{Not reachable.  The invariant is that the graph in the state
  is always acyclic.}

\eparts


%%% combinatorics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{combinatorics1}\pts{10}
\ksource{Nancy's brain}
\ktopics{Combinatorics}
%
Prove \textit{combinatorially} that the number of even-sized subsets
of a set $S\not=\emptyset$ is equal to the number of odd-sized
subsets.  Formally, denoting by $E$ the even-sized subsets of $S$ and
by $O$ the odd-sized subsets of $S$, construct a bijection between $E$
and $O$.  An algebraic proof will not be accepted. \hint{Although
  there is a natural bijection that works for all $S$, you may find it
  clearer to divide the bijection into one that works for even-sized
  $S$ and one that works for odd-sized $S$.}

\solution{Our mapping $f:E\rightarrow O$ complements the presence of
  some arbitrary element in the input set; i.e., choose some element
  $e\in S$ so that $f(X)=X\cup\set{e}$ if $e\not\in X$, or
  $f(X)=X-\set{e}$ if $e\in X$.  We must prove the function is defined
  on its domain, is one-to-one, and is onto.
  
  \textit{$|X|$ even-sized $\Rightarrow |f(X)|$ odd-sized.}  Clearly
  $|f(X)|=|X|\pm 1$, so if $X$ is even-sized, then $f(X)$ is
  odd-sized.
  
  \textit{$f$ one-to-one.}  Assume $f(X)=f(Y)$.  If $e\not\in f(X)$
  and $e\not\in f(Y)$, then $X=f(X)\cup\set{e}$ and
  $Y=f(Y)\cup\set{e}$, so $X=Y$; otherwise, if $e\in f(X)$ and $e\in
  f(Y)$, then $X=f(X)-\set{e}$ and $Y=f(Y)-\set{e}$, so again $X=Y$.
  
  \textit{$f$ onto.}  Consider an odd-sized set $Y$: if $e\not\in
  Y$, then $|Y\cup\set{e}|$ is even-sized, so $f(Y\cup\set{e})=Y$;
  otherwise, if $e\in Y$, then $|Y-\set{e}|$ is even-sized, so
  $f(Y-\set{e})=Y$.}




\kignore{
%%% combinatorics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{combinatorics4}\pts{14}
\ksource{Kyle's brain}\ktopics{Combinatorics, basic
  probability, product rule} \textbf{Theorem.}  Let $0\leq p_i\leq 1$
for all $i\in\set{1,\ldots, n}$.  Then,
\[ \sum_{S\subseteq \set{1,\ldots,n}} \kparen{\kparen{\prod_{j\in S}
    p_j}\kparen{\prod_{j\not\in S} (1-p_j)}} = 1 \] Note that
$\sum_{S\subseteq T}$ means to sum over all possible subsets $S$ of
$T$.

\bparts

\ppart \pts{6} Give a combinatorial proof of the theorem.
\hint{Consider choosing an element from $\set{a_1,b_1}\times
  \set{a_2,b_2}\times \set{a_3,b_3}\times\cdots\times \set{a_n,b_n}$
  where we have probability $p_i$ of choosing $a_i$ and probability
  $1-p_i$ of choosing $b_i$ for the $i\kth$ element of the tuple.}

\smallspace
\solution{Use the hint given.  For a given subset $S$ of the indices
  $\set{1,\ldots,n}$, the summand is the probability of choosing $a_i$
  for the indices in $S$ and $b_i$ for the indices not in $S$.  Since
  this covers exactly the possible ways of choosing a tuple given
  these probabilities, the total probability must be 1.}

\ppart 
\pts{8}
Give an algebraic proof of the theorem.  \hint{Use induction.}

\solution{Base case: When $n=1$, we have
  \[ p_i+(1-p_i) = 1 \]
  
  Inductive case: Assume the theorem for all $n\leq N$.  Now we must
  prove it for $N+1$.
  %
  \begin{eqnarray*}
    \sum_{S\subseteq\set{1,\ldots, N+1}} \kparen{\kparen{\prod_{j\in S}
        p_j}\kparen{\prod_{j\not\in S} (1-p_j)}}
    &=& \sum_{S\subseteq\set{1,\ldots, N}}
    \kparen{\kparen{p_{N+1}\prod_{j\in S} 
        p_j}\kparen{\prod_{j\not\in S} (1-p_j)}} \\
    && +
    \sum_{S\subseteq\set{1,\ldots, N}} \kparen{\kparen{\prod_{j\in
          S} p_j}\kparen{(1-p_{N+1})\prod_{j\not\in S} (1-p_j)}} \\
    &=& p_{N+1}\sum_{S\subseteq\set{1,\ldots, N}}
    \kparen{\kparen{\prod_{j\in S} 
        p_j}\kparen{\prod_{j\not\in S} (1-p_j)}} \\
    && +
    (1-p_{N+1})\sum_{S\subseteq\set{1,\ldots, N}} \kparen{\kparen{\prod_{j\in
          S} p_j}\kparen{\prod_{j\not\in S} (1-p_j)}} \\
    &=& p_{N+1}\cdot 1 +
    (1-p_{N+1})\cdot 1 \\
    &=& 1
  \end{eqnarray*}}
}




\kignore{
\kproblem{combinatorics5}\pts{8}
\ksource{nancy}
Find a closed-form expression for
%
\[ \sum_{k=1}^n k^2 \binom{n}{k} \]
\hint{Consider committees with a chair and vice-chair, but in which
both offices \textit{can} be held by the same person.}

\solution{
Can break this down into two terms:
the number of such configurations having both officers the same:
  $n 2^{n-1}$ (same as above).
plus
the number of such configurations having different officers:
  $n(n-1)2^{n-2}$
}
}




%%% expectation %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{expectation1}\pts{12}
\ksource{Nancy's brain}
\ktopics{Expectation, linearity
of expectation, expected number of events that occur, binomial
distribution, counting permutations}
%
Each of 5 students in 6.042 chooses a natural number in the range
$[1,\ldots,5]$, randomly and independently, using the uniform
distribution on $[1,\ldots,5]$.

\bparts

\ppart\pts{3} What is the expected number of people who choose the
number that gives their position in alphabetical order?

\smallspace 
\solution{$1$}

\ppart\pts{3} Give an expression representing the probability that
exactly the expected number of people (as given by your answer to
the previous part) choose their correct positions.

\solution{$\underbrace{\binom{5}{1}\frac{1}{5}}_{\mathrm{Winner}}
\underbrace{\left(\frac{4}{5}\right)^4}_{\mathrm{Losers}}$}

\newpage
Now suppose the 5 students are all assigned numbers in the range
$[1,\ldots,5]$ by a course TA, who chooses randomly from the uniform
distribution on permutations of $[1,\ldots,5]$.

\ppart\pts{3} Now what is the expected number of people who are
assigned the number that gives their position in alphabetical order?

\smallspace
\solution{$1$}

\ppart\pts{3} Give an expression for the probability that exactly
the expected number of people (as given by your answer to the
previous part) are assigned their correct positions.

\solution{This is more complicated, and a little too ad hoc for my
taste.  Maybe need hints?

I calculate that there are 45 5-permutations in which exactly one
guy is a "fixed point", which gives a probability of $45/120$, or
$3/8$.  To get the 45, I figure 5 choices for the fixed point, then
9 4-perms with no fixed point.  But, to figure out that there are
exactly 9 4-perms with no fixed point, I used slightly ad hoc
arguments: 3 possibilities for who gets the number 1; then for
each of these, say the guy with rank $i$, three possibilities for
who gets the number $i$; after these two are assigned, it turns out
that the final assignments have only one possibility.

In trying to generalize this, I got a somewhat messy recurrence.
So I'm inclined just to leave it as an ad hoc calculation.  OK
since the numbers are very small.  Or, we can give them the 9 as a
hint.

I was hoping to get a comparison between these two experiments,
but don't see anything nice here.  Is it clear which of the two
kinds of experiments should yield the higher probability of
getting exactly one fixed point?  Here, the probability is higher
in the case of the first experiment ($.4096$ vs. $.375$).  In
general?}

\eparts




\kignore{
%%% expectation %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{expectation2}\pts{10}
\ksource{Nancy}
\ktopics{Expectation}
%
100 students enter a cafeteria with at least 100 very large tables,
one at a time.  As each students enters, he or she looks around to see
if any of his friends are already there.  If so, he/she joins one of
his friends' tables.  If not, he/she starts a new table.

Assume that, for each pair of students, the probability that they are
friends is $p$.  Moreover, all these pair probabilities are
independent.

\ppart\pts{5} For the $i\kth$ person to enter the cafeteria, what is
the probability he/she starts a new table?

\smallspace
\solution{$(1-p)^{i-1}$}

\ppart\pts{5} What is the expected number of occupied tables after
everyone has entered?

\smallspace
\solution{Add this from $i = 1$ to $n$.}
}




\kignore{
\kproblem{expectation3}\pts{15}
\ksource{David R's Brain}
\ktopics{Expectation, product rule}
There is a casino in St. Petersburg
where you have the choice of betting any portion of your wealth on
either of two games: in the first game, you either receive 3 times
what you bet or lose it all with equal probability.  In the second
game the casino gives you 1.4 times what you bet with probability 1
(this casino is understandably very popular).  Each trial of the two
games is played simultaneously.

\bparts

\ppart\pts{3} Call $S_1$ and $S_2$ the fraction of your wealth you bet
on the two games (notice $S_1+S_2\leq 1$).  What values of $S_1$ and
$S_2$ maximize the expected value of your wealth after 1 trial?  What
is the maximum expected value of your wealth?
\smallspace
\solution{$S_1=1$, max is 1.5}

\ppart\pts{3} What strategy maximizes your expected wealth after $n$
trials? 
\smallspace
\solution{Always have $S_1=1$}

\ppart\pts{3} Using that strategy, what is the probability that after
10 trials, you have more money than you started with? 
\smallspace
\solution{$1-2^{-10}$}

\newpage
\ppart\pts{3} After $2n$ trials, what is the {\em most likely} number
of trials in game one that are wins.  And what is the probability that
this occurs?
\smallspace
\solution{$n$, $f_{2n,0.5}(n)\approx $}

\ppart\pts{3} What fraction of your wealth should you bet on each
trial of the two games, if you want to maximize your wealth after $2n$
trials in the most likely case that you found above? (i.e. suppose
that there are that number of wins over the course of the $2n$
trials).  Assume that it is in your interest to have $S_1+S_2=1$.
\solution{Maximize $(1.4+1.6S_1)^{0.5}(1.4-1.4S_1)^{0.5}$ over $S_1$.  $S_1=0.0625$.}
\eparts
}



\kignore{
%%% wald's theorem %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{expectation4}\pts{10}
\ksource{Nancy}
\ktopics{Wald thm.}
The number of
students that will enter LaVerde's to buy junk food on Tuesday night
of finals week is a random variable taking on an integer value from
$\set{0,\ldots,100}$ uniformly.  Each student who enters picks at
least one kind of junk food.  After choosing each kind of junk food, a
student is equally likely to continue choosing more kinds of junk food
or to quit and go pay at the checkout register.  Students' decisions
to continue buying are mutually independent.

The checkout clerk throws a fair die for each item and then charges
the number of dollars that shows up.

What is the expected number of dollars spent by students on junk food
at LaVerde's on Tuesday night?
}




%% Wald's Theorem
% From Fall98 sample problems
\kproblem{wald1}\pts{10}
\ksource{victor}
\ktopics{Wald's theorem}
%
A miner, lost in some abandoned mine, finds himself in a room
containing three doors.  Door 1 leads him to freedom after two hours
travel; door 2 returns him to the same room after four hours travel,
and door 3 returns him to the room after eight hours travel.  Each
time he finds himself in the room, the miner picks a door with equal
probability.

Let $T$ denote the time until he finds the exit. \\

\bparts

\ppart\pts{5} Define a sequence of independent,
identically-distributed random variables $X_i$ and a non-negative,
integer-valued random variable $N$ such that
\[T = \sum_{i=1}^{N}{X_i}\]

\smallspace
\solution{
We view this as an experiment where at each step we make a choice between
three equiprobable outcomes.

Let $X_i$ = number of hours to return to room on $i$th step.

Let $N$ = number of steps until good door is selected.

Then $N$ is geometrically distributed with probability $1/3$.
}

\ppart\pts{5} Use Wald's Theorem to find $\Ex[T]$

\solution{
$\Pr(X_i = 2) = 1/3$

$\Pr(X_i = 4) = 1/3$

$\Pr(X_i = 8) = 1/3$

$\Ex[X_i] = 14/3$

$\Ex[N] = 3$

By Wald's Theorem,
%
\[
\Ex[\sum_{i=1}^N X_i] = 14
\]
}

\eparts   




%%% markov and chebyshev bounds %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{markov1}\pts{12}
\ksource{Nancy}
\ktopics{Markov and Chebyshev Bounds}
The average IQ of all MIT faculty is known to be exactly $150$.

\ppart\pts{3} Give a tight upper bound on the probability that a
random MIT faculty member's IQ is $175$ or more.

\smallspace
\solution{Use Markov, get $\leq 150/175 = 6/7$}

\ppart\pts{3} Give an example distribution of weights showing that
your bound in the first part is tight.

\tinyspace
\solution{6 faculty members with IQ 175, one with IQ 0.}

Now assume also that the standard deviation of IQs of MIT
faculty members is 25.

\ppart\pts{3} Give a tight upper bound on the probability that a
random MIT faculty member's IQ is 175 or more, taking this new
information into account.

\smallspace
\solution{Use one-sided Chebyshev}

\ppart\pts{3} Give an example distribution of weights showing that
your bound in the previous part is tight.

\tinyspace
\solution{LTTR}




\kproblem{pmethod1}
\pts{14}
\ksource{Nancy}
\ktopics{Probabilistic Method}
Consider $n$ players in a round-robin tournament.  We are going to
consider the question of whether there exists a possible tournament
outcome (that is, a tournament digraph) in which every player wins at
least two matches (that is, every node in the digraph has at least two
outgoing edges).  We would like you to use the probabilistic method to
show that such an outcome exists, for certain values of $n$.  

\bparts

\ppart\pts{3} Say a match between two players---$a$ and $b$---is won
by $a$ with probability $1/2$ and by $b$ with probability $1/2$.  What
is the probability that a particular player wins no more than one
game?

\smallspace
\solution{$\frac{n}{2^{n-1}}$, since there are $n$ ways to win no more
  than one game---$1$ way to win zero, $n-1$ ways to win 1 versus
  $n-1$ opponents---out of $2^{n-1}$ possible ways to win/lose $n-1$
  games.}

\ppart\pts{3} Now, upper bound the probability that \textit{some}
player wins no more than one game.

\smallspace
\solution{By the union bound, this is just $\frac{n^2}{2^{n-1}}$.}

\ppart\pts{2} Lower bound the probability that \textit{all} players
win at least two games.

\smallspace
\solution{This is just the complement of the previous part, so
  $1-\frac{n^2}{2^{n-1}}$.}

\newpage
\ppart\pts{2} Show a condition implying a positive probability of
\textit{all} players winning at least two games.

\smallspace
\solution{$1-\frac{n^2}{2^{n-1}} > 0$.}

\ppart\pts{4} Explain \textit{briefly} why your condition implies the 
existence of such a tournament.

\smallspace
\solution{If there is a non-zero probability of such an event
  occuring, then there must be a configuration in which that event
  occurs.}

\eparts



\kproblem{indep1}
\pts{12}
\ksource{Kyle}
\ktopics{Mutual independence}
%
Consider three random variables, $A$, $B$, $C$, each of which takes on
either $-1$ or $1$ independently with uniform probability, and a
fourth random variable $D=A\cdot B\cdot C$.

\bparts

\ppart\pts{6} Show that any three of these variables are mutually
independent, but all four are not.

\mediumspace

\kignore{
\ppart\pts{3} Explain \textit{briefly} why this is the case.

\mediumspace
\solution{Enumerate the possibilities; it turns out that, for any
  three ($x$, $y$, and $z$ from $\set{A,B,C,D}$), $\Pr(x=1\cap y=1\cap
  z=1)=\Pr(x=1)\Pr(y=1)\Pr(z=1)$, and $\Pr(x=1\cap
  y=1)=\Pr(x=1)\Pr(y=1)$ and so on.  However, four variables
  overdetermine the possibilities: either the probability of the
  intersection is exactly 1 (if the relation is satisfied), or
  is 0 (otherwise).}
}

\ppart\pts{6} Extend this theorem to $n$ independent random variables
$X_1,\ldots,X_n$ over the same distribution and their product
$Y=\prod_{i=1}^n X_i$, and argue its correctness.

\mediumspace
\solution{TBD}

\eparts



\kproblem{intransitivity1}
\pts{10}
\ksource{Kyle and Nancy}
\ktopics{Intransitivity of probability}
%
Consider four 4-sided dice (labelled $A$, $B$, $C$, and $D$), each
with four unique digits from 1 through 16:
%
\begin{center}
\begin{tabular}{cllll}
A: &1&8&11&14 \\
B: &2&5&12&15\\
C: &3&6&9&16\\
D: &4&7&10&13\\
\end{tabular}
\end{center}
%
Die $x$ is said to beat die $y$ on a particular roll if $x$ comes up
with a higher roll than $y$.

\bparts

\newcommand{\beats}[2]{\ensuremath{#1~\mathrm{beats}~#2}}
\ppart\pts{5} Calculate $\Pr(\beats{B}{A})$, $\Pr(\beats{C}{B})$,
$\Pr(\beats{D}{C})$, and $\Pr(\beats{A}{D})$.

\mediumspace
\solution{\begin{itemize}
    \item $Pr(\beats{B}{A}) = 1/16 + 1/16 + 3/16 + 4/16 = 9/16$
    \item $Pr(\beats{C}{B}) = 1/16 + 2/16 + 2/16 + 4/16 = 9/16$
    \item $Pr(\beats{D}{C}) = 1/16 + 2/16 + 3/16 + 3/16 = 9/16$
    \item $Pr(\beats{A}{D}) = 0/16 + 2/16 + 3/16 + 4/16 = 9/16$
  \end{itemize}}

Consider the binary relation $R(x,y)$ on dice that indicates whether
$Pr(\beats{x}{y})>Pr(\beats{y}{x})$.  A relation is said to be a
\textit{strict partial order} if it satisfies the requirements for
being a partial order except that it is \text{not} reflexive.  (For
instance, $<$ on the natural numbers is a strict partial order, while
$\leq$ on the same set is a partial order.)

\ppart\pts{5} Is $R$ a strict partial order?  Prove your answer.

\solution{No, it is not transitive; clearly $R(D,C)$, $R(C,A)$, and
  $R(B,A)$, but $\neg R(D,A)$.}

\eparts



\kignore{
\kproblem{prob1}\pts{15}
\ksource{Nancy}
\ktopics{Conditional probability, independence, product rule,
inclusion-exclusion, set theory and probability}
%
Suppose $A$, $B$, and $C$ are events in a probability space, where $A$
and $C$ are independent events, $B$ and $C$ are independent events,
and $B \subseteq A$.

Suppose also that $\Pr(A) = 1/100$, $\Pr(B) = 1/10,000$, and $\Pr(C) =
1/1000$.
 
Calculate each of the following.  If it is impossible to determine the
value exactly from the given information, then give the range of
possible values.
 
\bparts

\ppart\pts{1} $\Pr(A \cap C)$
 
\tinyspace
\solution{$1/10^5$}
 
\ppart\pts{1} $\Pr(B \cap C)$
 
\tinyspace
\solution{$1/10^7$}
 
\ppart\pts{1} $\Pr(A \cap B)$
 
\tinyspace
\solution{$1/10^4$}

\ppart\pts{2} $\Pr(B | A)$
 
\tinyspace
\solution{$1/100$}
 
\ppart\pts{2} $\Pr(B | C)$
 
\tinyspace
\solution{$1/10^4$}
 
\ppart\pts{2} $\Pr(B - C)$
 
\tinyspace
\solution{$1/10^4 - 1/10^7$, or $.0000999$, approximately $.0001$}
 
\ppart\pts{2} $\Pr(B \cup C)$
 
\tinyspace
\solution{$1/10^4 + 1/10^3 - 1/10^7$, or $.0010999$, approximately $.0011$} 
 
\ppart\pts{2} $\Pr(A \cap (B \cup C))$

\tinyspace 
\solution{$1/10^4 + 1/10^5 - 1/10^7$, or $.0001099$, approximately $.00011$}
 
\ppart\pts{2} $\Pr(B | A \cap (B \cup C))$

\tinyspace 
\solution{$.0001/.0001099$, slightly less than 1}

\eparts 
}



\kproblem{diagnosis1}\pts{12}
\ksource{Nancy}
\ktopics{Probability}
It was reported in last Sunday's paper that $1/1000$ of the population
are estimated to have a newly-discovered chronic illness called
Creeping Rot Disease.  We don't know what it is, but it doesn't sound
good.
 
Luckily, a new test for Creeping Rot has become available. 
If a person has C.R., the test is 80\% accurate in diagnosing it. 
On the other hand, if the person does not have C.R., the test has only  
a 20\% probability of a "false positive". 

\bparts
 
\ppart\pts{4} If the test is given to a random person in the population, then
what is the probability that it comes out positive?

\smallspace 
\solution{
\begin{eqnarray*}
\Pr(T)
&=& \Pr(T | CR)\Pr(CR) + \Pr(T | \overline{CR})\Pr(\overline{CR}) \\
&=& (.8)(.001) + (.2)(.999)  \\
&=& .2006 
\end{eqnarray*}}
 
\ppart\pts{4} If a person gets a positive test result, then what is the
probability that he actually has C.R.?

\smallspace 
\solution{
\begin{eqnarray*}
\Pr(CR | T)
&=& \Pr(T|CR)\Pr(CR)/\Pr(T)  \\
&=& (.8)(.001)/(.2006)
\end{eqnarray*}
Approx. .004 }
 
\ppart\pts{4} If a person gets a negative test result, then what is the
probability that he has C.R.?

\smallspace 
\solution{
\begin{eqnarray*}
\Pr(CR | \overline{T}) &=& \Pr(\overline{T}|CR)\Pr(CR)/\Pr(\overline{T})  \\
&=& (1 - \Pr(T|CR))\Pr(CR)/ (1 - \Pr(T)) \\
&=& (.2)(.001)/(.7994) 
\end{eqnarray*}
Approx. .0025 }

\eparts



\end{problems}  


\end{document}

