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

\input{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.\ }}
\renewcommand{\solution}[1]{\textbf{Solution:} #1}
\newcommand{\ksource}[1]{}
\newcommand{\ktopics}[1]{}
\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\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{\ssol}[2]{\ifshowsolutions #1 \else #2 \fi}

\newcommand{\kignore}[1]{}

\DeclareMathOperator{\lcm}{lcm}

\begin{document}

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

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

\makeatother

\askaboutsolutions

\ifshowsolutions
\handout{pfinalsol}{Practice Final---Solutions}{20 May 2001}
\else
\handout{pfinal}{Practice Final}{17 May 2001}
\fi

\textbf{You do not have to turn in the solutions to this Practice
  Final. It is designed to help you study for the final.}

\textbf{Final Exam:} Covers the entire course. The final will be held
Thursday, May 24, 2001 from 1:30 p.m. to 4:30 p.m. in Rockwell.
The final is open book\slash notes; bibles are not allowed.

\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 traced out hit every node in the $(n+1)$-cube, and thus it
is a Hamiltonian path.
}
\end{problemparts}



%%%%%%%%%% 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. (In fact, the set~$S$ does not have any minimum!
  No matter what rational value larger than~$\sqrt{2}$ we choose,
  there is another rational value which is closer to~$\sqrt{2}$.
  However, $S$~has a so called \emph{infimum}, or largest possible
  lower bound, which is $\sqrt{2}$.)}

\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 characters.''  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}



%%%%%%%%%% 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} Suppose $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 different primes 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{\[\lcm(a,b) = \prod_i p_i^{\max(\alpha_i,\beta_i)}.\]}

\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
  pigeonhole principle, 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.}



\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 asymptotically 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 recurrence now becomes
  \begin{displaymath}
    T(n)=T(n-1)+6T(n-2)+6n.
  \end{displaymath}
  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
    &=&a(n-1)+b+6\bigl(a(n-2)+b\bigr)+6n \\
    &=&(7a+6)n + (-13a+7b),
  \end{eqnarray*}
  which gives $a = -1$ and $b = -13/6$. So, $T(n)=A3^n+B(-2)^n - n -
  13 / 6$.  We plug in and solve for the constants:
  \begin{eqnarray*}
    6 &=& T(1) = 3A - 2B - 19/6 \\
    42 &=& T(2) = 9A + 4B - 25/6
  \end{eqnarray*}
  The solutions to this system are $A=43/10$ and $B=28/15$, which gives
  the complete solution $T(n)=(43/10)3^n + (28/15)(-2)^n - n - 13/6$.}

\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~$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
\bmod 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
\bmod 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
}




%%% 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: Choose some element $e\in
  S$ and define $f(X)=X\cup\set{e}$ if $e\not\in X$, or
  $f(X)=X-\set{e}$ if $e\in X$; another way to write this is $f(X) = X
  \oplus \set{e}$. We must prove the function is defined on its
  domain, is one-to-one, and is onto.
  
  \textit{$|X|$ even-sized implies that $|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
$\set{1,\ldots,5}$, randomly and independently, using the uniform
distribution on $\set{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{Let $X_i$~be the indicator for the event that the $i$th
  person chooses the correct position, \ie $X_i = 1$ if person~$i$
  chooses the number that gives her\slash his position in alphabetical
  order and $X_i = 0$ otherwise. The number of people choosing the
  correct number is then $X_1 + X_2 + X_3 + X_4 + X_5$, which implies
  that the expected number of people choosing the correct number is
  \begin{displaymath}
    \sum_{i=1}^5 \Ex(X_i) = \sum_{i=1}^5 \Pr(X_i = 1).
  \end{displaymath}
  Since every person chooses a number in the range $\set{1,\ldots,5}$
  independently uniformly at random, $\Pr(X_i = 1) = 1 / 5$ for
  every~$i$. Therefore, the expected number of people who choose the
  number that gives their position in alphabetical order is~$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{Let $A$~be the event that exactly one person chooses the
  right position and $A_i$ be the event that (only) person~$i$ chooses
  the right position. Then
  \begin{displaymath}
    \Pr[A]
    = \Pr[A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5]
    = \sum_{i=1}^5 \Pr[A_i]
  \end{displaymath}
  since the~$A_i$ are disjoint. Furthermore,
  \begin{displaymath}
    \Pr[A_i] = \underbrace{\frac{1}{5}}_{\mathrm{Winner}}
    \underbrace{\biggl(\frac{4}{5}\biggr)^4}_{\mathrm{Losers}}
  \end{displaymath}
  for every~$i$, thus $\Pr[A] = (4/5)^4$.}

\newpage

Now suppose the 5 students are all assigned numbers in the range
$\set{1,\ldots,5}$ by a course TA, who chooses randomly from the
uniform distribution on permutations of $\set{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{As in part~(a), let $X_i$ be the indicator for
  the event that person~$i$ chooses the number that gives her\slash
  his position in alphabetical order and obtain that the expected
  number of people choosing the correct number is
  \begin{displaymath}
    \sum_{i=1}^5 \Ex(X_i) = \sum_{i=1}^5 \Pr(X_i = 1).
  \end{displaymath}
  For every~$i$, $\Pr(X_i = 1)$ is the number of 5-permutations with
  $i$~in the right place divided by the total number of
  5-permutations, \ie $\Pr(X_i = 1) = 4! / 5! = 1 / 5$.  Therefore,
  the expected number of people who choose the number that gives their
  position in alphabetical order is~$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{We need to calculate the number of permutations of five
  elements such that exactly one element is in the right position.
  There are five ways to choose the element that is in the right
  position; we have to multiply this number with the number of ways to
  permute the remaining four elements in such a way that no element is
  in the right position. One way to calculate the number of such
  permutations is to use a tree diagram; another is to use
  inclusion\slash exclusion \`a~la derangements (we did a similar
  problem in Tutorial~11). To formalize the latter method, let $A$~be
  the set of 4-permutations such that at least one number is in the
  right place. We are interested in the complement of~$A$---the set of
  4-permutations such that no number is in the right place---this set
  contains $4! - |A|$ elements. Now we rewrite $A = A_1 \cup A_2 \cup
  A_3 \cup A_4$, where $A_i$~is the set of permutations that have the
  $i$th element (and possibly also other elements) in the right place
  and use inclusion\slash exclusion:
  \begin{displaymath}
    |A| = |A_1 \cup A_2 \cup A_3 \cup A_4| =
    \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j|
    + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - |A_1 \cap A_2 \cap A_3 \cap A_4|.
  \end{displaymath}
  Now we note that $|A_i| = 3!$ for every~$i$ since we fix the
  position of the $i$th element and can permute the remaining elements
  arbitrarily. Similarly, $|A_i \cap A_j| = 2!$ and $|A_i \cap A_j
  \cap A_k| = 1!$. This gives
  \begin{displaymath}
    |A| = |A_1 \cup A_2 \cup A_3 \cup A_4| =
    \binom{4}{1} \cdot 3! - \binom{4}{2} 2! + \binom{4}{3} 1! - \binom{4}{4} 0! = 24 - 12 + 4 - 1 = 15.
  \end{displaymath}
  Therefore, the number of permutations of four elements such that no
  number is in the right position is $4! - |A| = 24 - 15 = 9$ and the
  number of permutations of five elements such that exactly one
  element is in the right position is~$45$. Since the total number of
  permutations is $5! = 120$, the sought probability is $45 / 120 = 3 /
  8$.}

\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 = \mbox{number of steps until good door is selected} = \min\{n
: \mbox{miner selects good door the $n$th time}\}$. Then $N$~is a
stopping time and $\Ex[N] = 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\biggl[\sum_{i=1}^N X_i\biggr] = 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, get $\leq 1 / (1+1^2) = 1 / 2$}

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

\tinyspace
\solution{One faculty member with IQ 175 and one with IQ 125.}




\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

\solution{To prove the first part, we only need to show that $A$, $B$
  and~$D$ are independent; it is already given that $A$, $B$ and~$C$
  are independent and the remaining cases are symmetric to the first
  one. So consider the event $\{A = a, B = b, D = d\}$. We can rewrite
  \begin{displaymath}
    \Pr(A = a, B = b, D = d)
    = \Pr(D = d \mid A = a, B = b) \Pr(A = a, B = b)
    = \frac{\Pr(D = d \mid A = a, B = b)}{4}\,.
  \end{displaymath}
  Now note that for any $a$ and~$b$, $\Pr(D = d \mid A = a, B = b) =
  \Pr(C = abd)$ by the definition of~$D$. Since $C$~is either $-1$
  or~$1$ with uniform probability, this probability is $1/2$, which
  proves that
  \begin{displaymath}
    \Pr(A = a, B = b, D = d) = 1/8 = 
    \Pr(A = a) \Pr(B = b) \Pr(D = d).
  \end{displaymath}
  To prove the second part, we just need to note that
  \begin{displaymath}
    \Pr(A = 1, B = 1, C = 1, D = -1) = 0.
  \end{displaymath}}
  
\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{The extended theorem is that any collection of $n$~of the
  above random variables is independent but all $n+1$ of them are not
  independent. It is proven in the same way as part~(a) above.}

\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{We use the law of total probability to compute
  \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}

