\documentclass[12pt]{article}

\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amsfonts}
\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{substr}

\IfSubStringInString{\detokenize{solution}}{\jobname}{%
  % Solutions
  \newcommand\qfill{}
  \newcommand\qpage{}
  \newcommand\qonly[1]{}
  \newcommand\answer[1]{#1}
  \newcommand\question[1]{{\em #1}}
  \newcommand\rubric[1]{}
}
{%
  \newcommand\qfill{\vfill}
  \newcommand\qpage{\newpage}
  \newcommand\qonly[1]{#1}
  \newcommand\answer[1]{}
  \newcommand\question[1]{#1}
  \newcommand\rubric[1]{}
}

\pagestyle{fancy}
\lhead{MATH 387-01}
\chead{Problem Set \#4\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due October 21, 2015}}

\begin{document}
\begin{enumerate}
\item {\bf (10 points)} \question{Let $\mathcal S$ be a collection of subsets of $\{1,\ldots, n\}$.}
  \begin{enumerate}
  \item \question{{\bf (4 points)} Demonstrate that it is possible for
      $|\mathcal S|$ (i.e., the number of \emph{subsets} of
      $\{1,\ldots,n\}$ contained as \emph{elements} of $\mathcal S$)
      to equal $2^{n-1}$ without any two elements of $\mathcal S$
      being disjoint from each other.}

    \answer{Let's consider all the subsets which contain $1$, i.e.,
      let's take every subset of $\{2,3,\ldots,n\}$ and insert $1$
      into each. This is a collection of $2^{n-1}$ sets none of which
      are mutually disjoin, since for every pair of sets $A$ and $B$,
      the two sets have at least one element (i.e., the element $1$)
      in common.}

  \item \question{{\bf (6 points)} Prove that if $|\mathcal S|\geq
      2^{n-1}+1$, then $\mathcal S$ contains two elements which are
      disjoint from each other.}

    \answer{Let us create pigeonholes for the subsets of
      $\{1,2,\ldots,n\}$, with each pigeonhole being home to exactly
      two sets: a set $S$ and its complement
      $\{1,2,\ldots,n\}-S$. Since there are $2^n$ subsets of
      $\{1,2,\ldots,n\}$ in total, this partition results in
      $\frac{2^n}2=2^{n-1}$ pigeonholes. Thus, if we have a collection
      of $2^{n-1}+S$ subsets of $\{1,\ldots,n\}$, then by the
      Pgeonhole Principle two of them must be in the same pigeonhole,
      so by the scheme used to construct our pigeonholes, those two
      are complementary to each other and thus disjoint.}

  \end{enumerate}
  
\item {\bf (10 points)} \question{Suppose that the sequence of numbers
    $a_n$ is given by the recurrence $a_n=4a_{n-1}+n$ with initial
    value $a_1=0$. Prove that $a_n=\Theta(4^n)$.}

  \answer{Just to get a feel for this sequence, it's illuminating to
    work out the first several elements: $a_1=0$, $a_2=2$, $a_3=11$,
    $a_4=48$, $a_5=197$, $a_6=794$. We can see that all of these are
    well below $4^n$. Also, let's note that proving that this is
    $\Theta(4^n)$ includes, as subordinate arguments, neeeding to show
    that it is both $O(4^n)$ and $\Omega(4^n)$.

    Proving that $a_n=\Omega(4^n)$ is easy; let's simply show by
    induction that for $n\geq 2$, $a_n\geq\frac184^n$. This is clearly
    true in the base case $n=2$, since $a_2=2=\frac{16}{8}$. Now let
    us assume that $a_n\geq\frac184^n$ and seek to show a lower bound
    on $a_{n+1}$, making use of our recurrence:
    \[a_{n+1}=4a_n+(n+1)>4a_n\geq
    4\left(\frac184^n\right)=\frac184^{n+1}\] completing our inductive
    proof.

    On the other hand, showing $a_n=O(4^n)$ is a bit harder, because
    that annoying addition causes our ratio with $a^n$ to creep
    upwards, although in a bounded fashion, so what we basically have
    to prove is that an upper bound on $a_n$ is some $f(n)4^n$, where
    $f(n)$ is itself bounded above by a constant. Since we can be
    ridiculously liberal with our bound, let's try showing by
    induction that $a_n\leq\left(1-\frac1n\right)4^n$. This is true
    and in fact sharp for $n=1$, demonstrating our base case. For
    larger values, let us assume $a_n\leq\left(1-\frac1n\right)4^n$
    and seek to place an upper bound on $a_{n+1}$ using our
    recurrence:
    \[a_{n+1}=4a_n+(n+1)\leq4\left(1-\frac1n\right)4^n+(n+1)=\left(1-\frac1n+\frac{n+1}{4^{n+1}}\right)4^{n+1}\leq\left(1-\frac1{n+1}\right)4^{n+1}\]
    The last inequality in the line above is not wholly obvious; it is
    essentially the assertion that
    $\frac1n-\frac{n+1}{4^{n+1}}\geq\frac1{n+1}$. Multiplying by a
    common denominator and rearranging, however, it is the inarguably
    true inequality $4^{n+1}\geq n^3+2n^2+n$.}
  
\item {\bf (10 points)} \question{If you are given an unsorted list of
    $n$ numbers, how long will it take to determine whether there are
    three numbers $x$, $y$, and $z$ in the list such that $xy=z$? Give
    your answer in big-O notation and explain your reasoning.}

  \answer{A simple algorithm to do this is to iterate $x$ over the
    entire length of the list, $y$ over the entire length of the list,
    and $z$ over the entire length of the list, checking for each
    triple whether $xy=z$; if we find values for which $xy=z$, we can
    answer ``yes''; otherwise after we completely exhaust every
    possibility we can say ``no''. But this involves looking at
    \emph{every} triple $(x,y,z)$ in the list (in practice we could
    halve the sample space, since $(x,y,z)$ and $(y,x,z)$ represent
    the same proposition), so it would take $O(n^3)$ time to complete
    this process.

    That was all I expected---and, to be honest, all I came up
    with---but props to Sean Harper and Kelsey Hough for coming up
    with an approach which uses slightly more space but less time: we
    can sort the list in $O(n\log n)$ time (or $O(n^2)$ time using a
    less efficient sort), and then, for each choice of the pair
    $(x,y)$, perform a binary search to see if the product $xy$ is in
    the list. The binary search itself takes $O(\log n)$ time, and is
    performed on $O(n^2)$ pairs $(x,y)$, so this search will take
    $O(n^2\log n)$ time, which subsumes the $O(n\log n)$ or $O(n^2)$
    time spent by the sort, so this algorithm completes in $O(n^2\log
    n)$ time.}
  
\item {\bf (10 points)} \question{Ten people go to a party and are
    introduced; everyone shakes hands with at least one other
    person. Prove that there must be at least two partygoers who shook
    hands with the same number of people. Is this still true if not
    everyone shakes hands with at least one person?}

  \answer{Each person shook hands with between 1 and 9 other people;
    if we classify people by the number of hands they shook, we are
    thus classifying them into 9 pigeonholes, and since there are 10
    pigeons, two are in the same hole so that two people shook the
    same number of hands.

    If, on the other hand, someone could have shaken 0 hands, then
    there is a plausible assignation of pigeons to pigeonholes without
    collision, since now our pigeonholes are numbered from 0 to 9, and
    there are 10 of them. However, despite the numerical plausibility
    of such a scenario, it cannot occur, for two reasons.

    One simple argument why that would be impossible is because one
    person at the party would have shaken 9 hands, i.e., been
    introduced to every other person, while one other person would
    have shaken 0 hands, i.e., not been introduced to any other
    person. These two requirements would be contradictory, since the
    extremely sociable and extremely unsociable person would have to
    simultaneously meet and not meet.

    Alternatively, in order for this to happen, then when we add up
    the number of handshakes each person has taken part in, we get
    $0+1+2+3+4+5+6+7+8+9=45$, and this will turn out to be
    impossible. It is impossible to get such a total because each
    handshake contributes 2 to the total (since each of the two
    handshake participants would count it), and so this total should
    always be even, which 45 is not. This alternative approach has the
    distinct disadvantage that it only results in a contradiction when
    the number of people is $2$ or $3$ modulo 4, whereas the argument
    in the previous paragraph always works.}


\end{enumerate}

\vfill
\begin{center}
  \fbox{
    \begin{minipage}{6in}
      On two occasions I have been asked --- "Pray, Mr. Babbage,
      if you put into the machine wrong figures, will the right
      answers come out?" In one case a member of the Upper, and in
      the other a member of the Lower House put this question. I am
      not able rightly to apprehend the kind of confusion of ideas
      that could provoke such a question.
      \hfill ---Charles Babbage
    \end{minipage}
  }
\end{center}

\end{document}
