\problemdata                                                             
        {Pigenhole/Counting} % latex-friendly label for the prob.
        {Pigeonhole, Counting} % The topic(s) of the problem content.  
        {Rosen, Instructor's resource guide, page 357, exercise 38, page 356, exercise 32} % Source (if known)                                          
        {S01 Final, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}    
\begin{problemparts} 
\problempart      
A professor teaching 6.042 gives a multiple choice quiz that has 10
questions, each of which has 4 possible answers (a,b,c,d). What is the
\emph{minimum} number of students that must be in the professor's
class in order to guarantee that at least three answer sheets must be
identical? (assume that no answers are left blank).  Justify your
answer.

\solution{
There are $4^{10}$ possible answers. By the strong pigeonhole principle, in order to have the desired property, we need at least $2\cdot 4^{10}+1$ students.
}


\problempart Let $s_1, s_2,\ldots, s_{101}$ be 101 strings of
1's and 0's that are at most 9 digits long. Prove that there exist 2
strings, $s_i$ and $s_j$, with $i\neq j$, that contain the same number
of 0's and the same number of 1's. (For example, strings 110001001 and
101000110 contain the same number of 0's and the same number of 1's)
[Note: You actually need much fewer than 101 strings to prove the
above---you can give a proof using a lower number of strings if you
would like to (for equal credit).]

\solution{ We can associate a pair $(a,b)$ with each string, where
  $a$ is the number of 0's and $b$ is the number of 1's. There are
  \emph{at most} 100 such pairs (actually, the constraint about the
  length of the string implies that there are fewer than 100). We can
  consider the pairs to be the holes and the strings to be the
  pigeons. Since there are more pigeons than holes, one hole must have
  at least 2 pigeons. Two strings that are associated with the same
  pair will have the same number of 0's and the same number of 1's.
  
  If we take the constraint about the length into account, then we see that there can be only 55 $(a,b)$ pairs: for each possible length $i\in[0\ldots 9]$ there are $i+1$ possibilities for the number of $0$'s (or 1's, of course). Thus, the total number of \emph{legal} pairs $(a,b)$ is 
\[
\sum_{i=0}^{9}{i+1}=55
\]
Since there are (much) more pigeons than holes, one hole will have at least 2 pigeons.

}

\end{problemparts}
\end{problem}
                                 