Skip to main content

2021/22 AHSMC Part 1 Problem 9

Problem 9 of 16

At a daycare consisting of 100100 children, each child can bring at most 1010 toys (but could also bring fewer toys, including no toys at all). Without knowing how many toys each child will bring, what is the maximum value of nn for which the following statement is true?

At least nn children must bring the same number of toys.

Answer choices

Show solution

Solution

Each child can bring 0,1,2,…,100, 1, 2, \ldots, 10 toys. Since there are 100100 children, at least ⌈100/11⌉=⌈9.09⌉=10\bigl\lceil 100/11 \bigr\rceil = \lceil 9.09 \rceil = 10 must bring the same number of toys. This shows n≥10n \ge 10. To show that n=10n = 10 is the answer, suppose that 1010 children brought 00 toys each, 1010 more children brought one toy each, and so on until the last 1010 children brought 99 toys each. This accounts for all 100100 children, and in this situation the statement is false for any n>10n > 10. The answer is (B).