\kproblem\ksource{Nancy's brain} Prove 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$.  \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$.}

\kproblem\ksource{Kyle's brain, modified from PS6 n4} 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?}

\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*}
  }

\kproblem\ksource{Kyle's brain, inspired by a trip to the Galleria} 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, with exactly one table and a \textit{single}
associated chair at each point.  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).  Prove that this must occur
if $4n+1$ members attend.

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

\kproblem\ksource{David Gries' book} A full binary tree is a binary
tree in which each node has either 0 children or 2 children.  Prove
\textit{by induction} that all non-empty full binary trees have an odd
number of nodes.

\solution{Base case: 1 node, odd.
  
  Induction: Assume all full binary trees of height $\leq n$ have an
  odd number of nodes.  Now, consider a full binary tree of height
  $n+1$.  Since the height is greater than $0$, the root node must
  have two children, $A$ and $B$, which must themselves be full binary
  trees of height $\leq n$.  The whole tree has $1+|A|+|B|$ nodes
  which, by the induction hypothesis, is odd+odd+odd=odd.  This proves
  the theorem.}

\kproblem\ksource{David Gries' book, Eg. 16.36} Let $n=2k$, for some
$k\geq 0$.

\bparts

\ppart Prove \textit{combinatorially} that $n!/2^k$ is an integer.

\solution{Consider a multiset with two of each of $k$ distinct
  elements.  The number of permutations with limited repetition of
  this set is $n!/(\underbrace{2!2!\cdots 2!}_{k})=n!/2^k$, which must
  be an integer.}

\ppart Prove the same theorem algebraically.

\solution{$n!=(2k)!=(\underbrace{2k}_{\mathrm{even}})
  (\underbrace{2k-1}_{\mathrm{odd}})
  (\underbrace{2k-2}_{\mathrm{even}})
  (\underbrace{2k-3}_{\mathrm{odd}}) \cdots (2)(1)$. There are $k$
  even factors, so $2^k|n!$.}

\eparts

\kproblem\ksource{Kyle's brain} \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 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 a
  probability $p_i$ of choosing $a_i$ for the $i\kth$ element of the
  tuple.}

\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 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*}}

\kproblem\ksource{Kyle's brain} \textbf{Theorem.}
\[ 2^{n-3}\prod_{i=1}^{n-3} 2^i = 2^{\binom{n}{2}-n} \]

\bparts

\ppart Give a combinatorial proof of the theorem. \hint{Consider a
  graph represented by a circle of $n$ nodes where there are no edges
  between directly adjacent nodes.}

\solution{Consider the RHS: there are $\binom{n}{2}$ edges between
  nodes in a complete graph, but only $\binom{n}{2}-n$ when the edges
  forming the outside of the circle are not considered.  Thus, there
  are $2^{\binom{n}{2}-n}$ such possible graphs on $n$ nodes.
  
  Now, consider the LHS: number the nodes in some way, and start with
  the first two.  Each has $n-3$ possible edges to other nodes: not to
  itself, and not to either of its two neighbors.  So, there are
  $2^{n-3}$ possible subsets of the edges from each of these two
  nodes.  The third node has $n-4$ edges that don't intersect with the
  first two sets: not to itself, not to either of its two neighbors,
  and not to the first node; thus, there are $2^{n-4}$ possible edge
  subsets.  The fourth node has $n-5$ edges that don't intersect with
  the first three sets: not to itself, not to either of its two
  neighbors, not to the first node, and not to the second node; so
  $2^{n-5}$ possible edge subsets.  And so on.

  By the product rule, this is $2^{n-3}\cdot 2^{n-3}2^{n-4}2^{n-5}\cdots=
  2^{n-3}\prod_{i=1}^{n-3} 2^i$.}

\ppart Give an algebraic proof of the theorem.

\solution{\begin{eqnarray*}
    2^{n-3}\prod_{i=1}^{n-3} 2^i
    &=& 2^{n-3 + \sum_{i=1}^{n-3} i} \\
    &=& 2^{n-3 + (n-3)(n-2)/2} \\
    &=& 2^{(2n-6+n^2-5n+6)/2} \\
    &=& 2^{(n^2-3n)/2} \\
    &=& 2^{(n(n-1))/2 - n} \\
    &=& 2^{\binom{n}{2} - n}
  \end{eqnarray*}}

\eparts

\kproblem\pts{12}\ksource{Nancy's brain -- Coverage: 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]$.
  
  \ppart\pts{3} What is the expected number of people who choose the
  number that gives their position in alphabetical order?
 
  \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}}$}
  
  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?
 
  \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

\kproblem\pts{10}\ksource{Nancy}
100 students enter a cafeteria with 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 For the $i\kth$ person to enter the cafeteria, what is the
probability he/she starts a new table?

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

\ppart What is the expected number of occupied tables after everyone
has entered? 

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

\kproblem\pts{10}\ksource{Nancy, 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?

\kproblem\pts{16}\ksource{Nancy} The average IQ of all MIT faculty is
known to be exactly $150$.

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

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

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

\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 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.

\solution{Use one-sided Chebyshev}

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

\solution{LTTR}

