You're cleaning up your little nephew's toy room. There are Ttoys on the floor and n empty toy storage boxes. You randomly throwtoys into boxes, and when you're done the box with the most toyscontains N toys.
(a) What is the smallest that N 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 up, there will be (atleast) one pair of boxes that contain the same number of toys.
Hint
Argue the contrapositive by assuming that every box ends up adifferent number of toys. What is the fewest number oftoys you could have started with?
Note:
- Note you are only being asked to explain part (c) of thisactivity.
- You do not need to apply the Pigeonhole Principle directly;instead you can engage in \"tipping point\" reasoning. See the hintprovided in the activity.
