\documentclass[12pt,HW250,ifthen]{article}
\usepackage{comment}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}
\usepackage{amsmath}

\begin{document}

\centerline{Homework 11, Morally due Tue May 7, 3:30PM}

\centerline{\bf THIS HW IS THREE PAGES!!!!!!!!!!}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

THROUGHOUT THIS HW:
Unless I tell you what $n$ is, assume $n$ is large enough
so that we can use our approximations and the Ind assumptions we made in class.
(If you were not in class then --- too bad for you!)

THROUGHOUT THIS HW:
Assume the grader does not already know the material so clearly explain what you are doing
or how you are setting up your program.



\begin{enumerate}

\item
(0 points but if you don't show up to the final I will assume you got this
problem wrong and you will get 0 points for this entire HW)
WHEN IS THE FINAL?
WHERE IS THE FINAL?

\item
(40 points)
We are going to put $m$ balls into $n$ boxes, uniformly at random.
You can assume $n$ is large so our approximations work.
\begin{enumerate}
\item
(20 points)
What is the probability (approx) that some box has at least 4 balls in it?
\item
(20 points)
Make a statement:

If $m\ge XXX$ then the prob that some box has 4 balls in it is $\ge \frac{3}{4}$.

FILL IN THE XXX. XXX will depend on $n$. Try to make XXX as small as possible. Please provide a number for the constant in-front of $n$.
\end{enumerate}

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(30 points)
Assume $n$ is large enough for our approximations to work. Also assume that $n^{0.9}$ is an integer. 
We are going to put $n^{0.9}$ balls into $n$ boxes, uniformly at random.
(Yes you read that right.)


\begin{enumerate}
\item
What is the prob that some box has $\ge 2$ balls?
\item
What is the prob that some box has $\ge 3$ balls?
\item
Find  a CONSTANT XXX (So XXX is ind of $n$)  
such that the prob that some box has $\ge XXX$ balls is $\ge \frac{1}{2}$.
Try to make XXX as large  as possible.
(You may use that $\binom{n}{k}\sim n^k$.)
\end{enumerate}

SHOW all of your work so that if the grader is not familiar with the problem he can still
understand your answer.


\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(30 points)
Let $p_n$ be the EXACT answer to the $n$-person hatcheck problem. Recall that
$$p_n = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} + \cdots + (-1)^n \frac{1}{n!}.$$

Write a program that does the following

For $2\le n\le 20$ 
\begin{enumerate}
\item
Compute $p_n$ exactly.
(To deal with the precision issues in your code, please keep the numerator and denominator of the computed fractions separately and perform only one division in the end.)
\item
Compete $\frac{1}{e}-p_n$ (it may be positive or negative).
\item
Put your results in a nice easy-to-read tables with first column $n$ and the second column
$p_n$ and third column $\frac{1}{e}-p_n$.
\item
Make a conjecture about when the $\frac{1}{e}-p_n$ is positive and when it is negative.
\item
Make a conjecture about how quickly $|\frac{1}{e} - p_n|$ goes to zero. For example, maybe you think
$|\frac{1}{e}-p_n|\sim\frac{\pi}{n}$.  (HINT: I do not think that.)
\end{enumerate}

Your answer should have the columns and the conjectures.


\end{enumerate}

\end{document}