\documentclass[12pt,ifthen]{article}
\usepackage{url}
\usepackage{comment}
\usepackage{hyperref}
\usepackage{xcolor}

\newcommand{\bits}[1]{\{0,1\}^{{#1}}}
\newcommand{\und}{\_\_\_\_\_\_\_\_\_}
\newcommand{\N}{{\sf N}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\tab}{\phantom{\qquad}}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid

\begin{document}

\centerline{\textbf{Honors HW 12. Due May 11} }



\begin{enumerate}



\item 
Let $n\in\N$. 

Alice has $a\in \bits n$ on her forehead.  Bob   has $b\in \bits n$ on her forehead. 
Carol  has $c\in \bits n$ on her forehead.  Donna has $c\in \bits n$ on her forehead.

They view $a,b,c,d$ as $n$-bits numbers.

They want to know if $a+b+c+d= 2^n-1$. 

Show how they can compute this with LESS THAN $n$ bits of communication. 

\item 
Let $n\in\N$. 
Let $i\in\N$. Think of $k\ll n$. 

Society now has done away with names and everyone is a number. 
$A_1$ has $a_1\in \bits n$ on her forehead. 
$A_2$ has $a_2\in \bits n$ on her forehead. 
$\ldots$
$A_k$ has $a_k\in\bits n$ on her forehead. 

They view $a_1,\ldots,a_k$ as $n$-bits numbers.

They want to know if $a_1+\cdots+a_k = 2^n-1$. 

Show how they can compute this with LESS THAN $n$ bits of communication. 

Recall that for the 2-egg problem we have that the number of drops needed is roughly $\sqrt{2}\sqrt{n}$. 

Let $D(e,n)$ be number of drops needed if you have $e$ eggs and $n$ floors. 


\item
Write a program that will, given $e,n$, compute $D(e',n')$ for all $1\le e'\le e$ and $1\le n'\le n$. 

\item
Run your program for $e=3$ and $n=1,\ldots,100$. Graph the function. Try to determine 
what the function is approximately. 

\item
Run your program for $e=4$ and $n=1,\ldots,100$. Graph the function. Try to determine 
what the function is approximately. 

\item
Is there some $e$ such that 

$$D(e,100)=D(e+1,100)=D(e+2,100)\cdots\hbox{?}$$


\end{enumerate}
\end{document}