Question

You're cleaning up your little nephew's toy room. There are T toys on the floor and n empty toy storage boxes. You randomly throw toys into boxes, and when you're done the box with the most toys contains N toys.

(a)What is the smallest that NN could be when T=2n+1?

(b) What is the smallest that NN could be when T=kn+1?

(c)Now suppose that the number of toys T satisfies

T<n(n−1)/2.

Prove that when you are done cleaning there will be (at least) one pair of boxes that contain the same number of toys.

Answer 1

In both parts, I will find the minimum value of N. Since NN =N² is increasing function of N, we would have found the required minimum value.

1. Claim:N=3. Let's assume there was a distribution of toys such that N < 3. Therefore each box contains atmost 2 toys. Since we have n boxes we would get atmost 2n toys in the boxes contradicting the fact that there were actually 2n+1 toys. So we have N>2. For N=3, the distribution is 3 in first box, 2 in the rest.
2. Claim:N=k+1. The proof is the same as before, substitute 2 with k and 3 with k+1 in the above proof.
3. Let's assume that we have one distribution of toys with different number of toys in each box. Arrange the boxes in increasing number of toys. In this case first box, will have atleast 0 toys, 2nd box will have atleast one toy, kth box will have atleast k-1 boxes and so on. Hence the the number of toys is atleast 0+1+2+...+n-1 = n(n-1)/2 contradicting the fact that T< n(n-1)/2