Exercise 3. Alice puts 100 balls in a bag. On each ball she has written the square of an integer. Bob wants to find two balls such that the difference of the numbers is a multiple of 7. How many balls does he need to draw at a minimum to be sure to achieve his goal, regardless of the numbers chosen by Alice at the beginning?
## Solution to Exercise 3

A congruence table modulo 7 shows that the square of an integer can only take the values $0, 1, 2,$ or $4$ modulo 7. Thus, if Bob draws 5 balls, he will have two that have the same remainder modulo 7, according to the pigeonhole principle. The difference in the numbers on these two balls will therefore be a multiple of 7. Conversely, if he draws only 4 balls, he could have one ball with a number congruent to 0 modulo 7, one with a number congruent to 1, one with a number congruent to 2, and one with a number congruent to 4, so he would not achieve his goal. Therefore, Bob must draw 5 balls.

Grader's Comment: The exercise is very well done. However, there are quite a few confusions about the pigeonhole principle. Since there are 4 squares modulo 7, the pigeonhole principle ensures that if you take 5 balls, then two will have the same congruence modulo 7. However, it should be explained why taking 4 balls does not guarantee having two with the same congruence modulo 7 (by providing a counterexample).