Pigenhole/Counting Pigeonhole, Counting Rosen, Instructor’s resource guide, page 357, exercise 38, page 356, exercise 32 S01 Final, 4 Tina Wang, S02

problem problemparts 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 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.

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

Let s_{1}, s_{2}, …, 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 ≠ 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).]

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 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 ∈ [0 … 9] there are i+1 possibilities for the number of 0’s (or 1’s, of course). Thus, the total number of legal pairs (a, b) is ∑_{i=0}^{9} i + 1 = 55Sincethereare(much)morepigeonsthanholes, oneholewillhaveatleast2pigeons.