\documentstyle[12pt,macpsfig,amssymb]{article}
\input{/a/class/6.042/fall94/handouts/macros-course}

        \addtolength{\topmargin}{-.2in}
        \setlength{\textheight}{8.5in}

\setcounter{page}{0}

\renewcommand{\bar}{\overline}

\newcommand{\pr}{\problem}
%\newcommand{\pr}{\newpage\problem}
%\renewcommand{\bparts}{\begin{testproblemparts}}
%\renewcommand{\eparts}{\end{testproblemparts}}

\newcommand\tfitem{\item [{\bf T / F \hspace*{.1in} }]}
%\renewcommand{\theproblem}{Problem \arabic{problemnum}}

\newcommand\Ex[1]{\mbox{Ex}[\, #1 \, ]}
\newcommand\vari[1]{\mbox{Var}(\, #1 \,)}
\newcommand\Prob[1]{\mbox{Prob}[\, #1 \, ]}


\begin{document}

\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\bparts
\ppart
%\setlength{\itemsep}{3.5in}
Let $G=(V,E)$ be a directed graph in which each vertex has out-degree at 
least~$1$.
Prove by induction that 
$G$ contains a directed path of length~$m$ for all $m\in\nats$.
\ppart
Use the pigeonhole principle to prove that
if directed graph
$G=(V,E)$ has a path with $|V|$ edges, then $G$ contains a cycle.
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
For each of the following statements, 
(1) circle {\bf T} or {\bf F}  to indicate whether the statement is 
true or false, respectively, and 
(2) justify your answer succinctly.
The justification counts for more points than does the correct 
{\bf T}/{\bf F} answer.
A formal proof is not necessary, but you should be able to write a
one- or two-sentence explanation or picture that conveys the essential idea.

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
        \setlength{\labelwidth}{\leftmargin}%
%        \setlength{\itemsep}{1.3in}%
        \addtolength{\labelwidth}{-\labelsep}
}

%\item  $\forall X\subseteq \reals$, if $X$ is uncountable, 
%       then $\reals - X$ is countable.

\item  $f(x)= x^3+x$ is a bijection from $\reals$ to $\reals$.

\item  $f(x)= x^3-x$ is a bijection from $\reals$ to $\reals$.

\item  $\forall a,b,c\in\nats$, if $a\divides c$ and $b\divides c$, 
        then $ab \divides c$.

\item  $\forall a,b\in\nats$, we have $\gcd(7a+2b,3a+b) = \gcd(a,b)$.

%\item  $\forall a,b\in\nats$, we have $\gcd(7a+3b,3a+b) = \gcd(a,b)$.
%\item  For all positive integers $n$, we have $n$ divides $2n \choose n$.
%\item  For all finite sets $A$ and $B$, if $A$ is a proper subset of~$B$, 
%       then there is no bijection between $A$ and~$B$.  

\item  For all countably infinite sets $A$ and $B$, 
        if $A$ is a proper subset of~$B$,
        then there is no bijection between $A$ and~$B$.  

\end{list}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr

For each of the following pairs of functions $f(n)$ and $g(n)$, fill
in the blank with $o$, $O$, $\omega$, $\Omega$, and $\Theta$ depending 
depending on
whether $f(n)=o(g(n))$, $f(n)=O(g(n))$, $f(n)=\omega(g(n))$,
$f(n)=\Omega(g(n))$, or $f(n)=\Theta(g(n))$.
If there is more than one relation between $f(n)$ and $g(n)$, write
the strongest one.  
Suboptimal answers will get partial credit but
incorrect answers will be penalized, 
so do not guess unless you are reasonably sure.
As usual, $\lg n$ denotes logarithm to the base~2.
The first line is an example solution.

\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
%\renewcommand{\arraystretch}{4}         %make it 4 later.
\begin{array}{rcl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8^{\lg n}       & = & \blank  (n^3)\\  %%  EXAMPLE  %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
n!              & = & \blank (6^n) \\
2^{(\lg^3 n)}   & = & \blank (n^4) \\
        \makebox[0in][r]{(for any constant $k$,) }
{n\choose k}    & = & \blank  (n^k) \\
%%      (\lg n / \lg\lg n)!& = & \blank & (n^2\lg n)
\displaystyle \sum_{i=1}^n  \frac{1}{i}
                & = & \blank (1)  \\
\displaystyle \sum_{i=n}^\infty \frac{1}{i^2}
                & = & \blank (1) 
\end{array}
\]



  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \pr

  In an $\nats^+$-weighted undirected graph, each
  edge is assigned a positive integer weight.  
  The \defi{weighted-degree} of a node is the sum
  of the weights of its incident edges.

  Consider the following set of weighted degrees:
  $1, 3, 5, 7, \ldots, 2n-1$.

  \bparts 
  \ppart Show that if $n$ is odd, then no graph on $n$ nodes has 
  this set of weighted-degrees.

  \ppart Show that if $n>2$ is even, then there exists a graph on $n$ nodes
  with this set of weighted-degrees.\\
  Do this by constructing such a graph for each even~$n>2$.
  You may do this inductively, by constructing a graph for $n+2$
  from the graph already constructed for~$n$.  (Don't forget the base case.)

  \eparts 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
There are $k$ (distinguishable) students taking an exam who must be seated 
in a row of $n$ seats so that no two students 
are seated next to each other.
How many ways can the students be seated?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr

Assume that the annual inflation rate is forever fixed at $p= 5\%$.
Suppose Marilyn offers to pay Bobo $\$1000n$ dollars at the end of year $n$ for
every $n\geq 1$.  
So, at the end of year~1, Bobo gets $\$1000$;
at the end of year 2, Bobo gets another $\$2000$, 
at the end of year 3, Bobo gets another $\$3000$, and so on, forever.
In return, Marilyn wants an up front payment of $\$1,000,000$.  
Bobo figures this is a good deal since he (or his descendants) 
will be making an infinite amount of money in the future.  
Is Bobo right about it being a good deal?  
What is the present value of all future payments?  
You should not need a calculator to compute the exact answer.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr

Observe that
\begin{eqnarray*}
1 & = & 1 \\
4 & = & 1 + 3 \\
9 & = & 1 + 3 + 5 \\
16 & = & 1 + 3 + 5 + 7 \\
25 & = & 1 + 3 + 5 + 7 + 9
\end{eqnarray*}
Use generating functions to derive and prove a general formula.
For this problem, you {\em must\/} use generating functions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr

The prosecution at OJ's trial is attempting to tie OJ to the
crime by a new analysis of {\em blood thickness}.  
Blood thickness is expressed as a natural number.  
The average blood thickness over all humans is~100.  
OJ has very thick blood: its thickness is~150.  

\bparts
\ppart
Knowing only the average thickness, 
what bounds (upper and lower) can you prove on the fraction of humans
that can have blood thickness~150?  
\ppart
At the trial, the prosecution reveals that the standard deviation of 
blood thickness is~5.  It is further revealed that the blood found at 
the scene of the crime has thickness~150.  
Using Chebyshev's theorem, what can you say about the
fraction of humans that might have commited the crime?  
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Problem 4
\problem 
If $m$ identical balls are thrown randomly into $n$ identical bins, 
what is the expected number of empty bins?

% Problem 6
\problem
How many $n \times n$ (0-1)-matrices have no all-$0$ columns?

% Problem 8
\problem
Let $G$ be an undirected graph with $2n$ vertices. Argue carefully that if
$G$ contains no triangles, then $G$ contains at most $n^2$ edges, and that
this bound is tight.

% Problem 9
\problem
Let $X$ be a set of size $n$, and let $S_1,S_2, \cdots, S_b$ be a collection
of (not necessarily distinct) subsets of $X$, all of size $l$. Suppose there
exist integers $t$ and $\lambda$ such that if $Y$ is any subset of $X$ of size
$t$, then $Y \subseteq S_i$ for exactly $\lambda$ of the sets $S_i$. (Of
course, $1 \leq t \leq l$ and $1 \leq \lambda \leq b$.) Suppose that $R$ is a
subset of $X$ of size $k$, for some $k$, where $1 \leq k \leq t$. Argue that
$R$ is a subset of exactly $\displaystyle \lambda { n-k \choose t-k }/
{ l-k \choose t-k }$ of the subsets $S_i$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Prove that
\[
{1\over\sqrt{1}} + {1\over\sqrt{2}} + {1\over\sqrt{3}} + \cdots + 
        {1\over\sqrt{n}}
 > \sqrt{n} \mbox{\hspace*{.3in} for $n=2,3,4,\ldots$}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Give asymptotic upper bounds for $T(n)$ in each of the following recurrences.
Assume that $T(n)$ is constant for $n\leq 2$.
Make your bounds as tight as possible.
\begin{problemparts}
\problempart
$T(n) = 2 T(n/2) + n^3$
\problempart
$T(n) = T(9n/10) + n$
\problempart
$T(n) = 16 T(n/4) + n^2$
\problempart
$T(n) = 7 T(n/3) + n^2$
\problempart
$T(n) = 7 T(n/2) + n^2$
\problempart
$T(n) = 2 T(n/4) + \sqrt{n}$
\problempart
$T(n) = T(n-1) + n$
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Suppose you are offered a betting game in which you keep flipping a fair coin
until you get a head and if you flip the coin $k$ times without getting a head,
you win $\$ 2^k$.
If the game costs \$1 to play, what is your expected return (net winnings)?\\
Would you be willing to play this game?
Would you be willing to play this game if it cost \$1000?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
  \problem
  When designing VLSI circuits, a good rule of them is that the
  probability that the circuit will work is $e^{-pA}$ for some constant $p$,
  where $A$ is the area of the circuit.  Give a justification for this rule
  under the assumption that every unit of area on the chip fails independently
  with probability $p$ and that the circuit will fail if any unit of area fails.
  %   Idea we want is prob of working is $(1-p)^A$ which is at most $e^{-pA}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

Recall the Gambler's Ruin problem from lecture.  Assume the game is
fair---that is, $p=1/2$.  Suppose you have a goal of reaching $\$ T$.
Let $P_n$ be the probability that, starting with $\$n$, where $n\leq
T$, you reach your goal before going broke.  In lecture we showed that
$P_n = n/T$.

Suppose you start with $\$n$ and continue to play until you are broke.
Let random variable $M$ be the maximum number of dollars you ever
have.  Determine the expected value of~$M$.

\end{problems}

\end{document}
