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