\documentclass[12pt]{article}
\textwidth = 6.7 in
\textheight = 9.2 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 10}
\\[1ex]}
\end{center}

This homework contains 4 problems worth a total of 34 points.
It is due on Friday, November 20th at noon.   Put your homework in
the appropriate dropbox in the Siebel basement.



\begin{enumerate}
%----------------------------------------------------------------------
\item 
\textbf{Pigeonhole principle [6 points]}

A software engineering at Snazzy Mobiles (a startup company)
slept for 61 hours over 10 nights.   Show that on some pair
of consecutive nights, he slept at least 13 hours.


%----------------------------------------------------------------------
\item 
\textbf{Pigeonhole II [10 points]}

Over a 30-day period,
Frank learns one or more fiddle tunes each day.  (Always an
integer number of tunes on any given day.)
Suppose that he learns no more than 45 tunes over the 30 days.
Prove that there is a period of 1 or more consecutive days
in which he learns exactly 14 tunes.

Hint:  Suppose $a_i$ is the number of tunes learned in all the
days up through and including $i$.   Consider the 
integers $a_1, a_2, \ldots, a_{30}$, together with
the integers $a_1 + 14, a_2 + 14, \ldots, a_{30}+ 14$.


%----------------------------------------------------------------------
\item 
\textbf{Bernouilli Trials [8 points]}

Marjorie is still a beginner at flute, so if she tries to play
a high A, there is only a 0.3 probability that it will sound.  If she
makes 5 attempts to play a high A, then...

\begin{enumerate}
\item What is the chance that it will sound exactly three times?
\item What is the chance that it will sound at least three times?
\item (4 points) What is the chance that it will sound three times in a row?
Include cases in which it sounds more than three times, as long as
at least three successes 
were consecutive.   Briefly explain how you calculated your
answer and why it's right.  Hint:  don't blindly
apply the Bernouilli Trials formula.   Reason from first principles.
\end{enumerate}

%----------------------------------------------------------------------
\item 
\textbf{Expected value [10 points]}

Instead of just giving out chocolate on Halloween in the obvious
way, your neighbor Mr. Egbert makes
you draw cards to see how much he will give you.
Mr. Egbert has a deck of 13 cards, with face values
1,2,\ldots,13 and you get to choose a hand containing four cards.

For each hand $h$, you get $C(h)$ small chocolates, where $C(h)$
is the maximum face value of any of the cards in the hand.  
For example, you get 9 chocolates if you draw a hand containing
2, 5, 6, and 9.

\begin{itemize}
\item How big is our sample space (aka how many possible hands)?
\item How many possible hands have $k$ as the maximum value of the
cards in the hand? (I.e. give a formula that depends on $k$.)
\item What is the chance of drawing a hand with maximum value $k$?
\item How many chocolates can you expect to get out of this
guy?  (I.e. what is the expected value of $C$?)
\end{itemize}


\end{enumerate}

\end{document}
