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