logo Gonitzoggoβ

Too Many Balls


$2023$ balls are divided into several buckets such that no bucket contains more than $99$ balls. We can remove balls from any bucket or remove an entire bucket, as many times as we want. Prove that we can remove them in such a way that each of the remaining buckets will have an equal number of balls and the total number of remaining balls will be at least $100$.


Source: BdMO 2023 National Secondary P4



Proof Based Problems  


  1 Upvote                    0 Downvote


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

For the sake of contradiction, assume that this is not possible.

So, there is not $k$ boxes with $\frac{100}{k}$ or more balls because taking these $k$ buckets keeping exactly $\lceil\frac{100}{k}\rceil$ balls satisfies the condition.

  •  So, there is no box with 100 or more balls.
  •  there is not 2 boxes with 50 or more balls.
  •  there is not 3 boxes with 34 or more balls.
  •  there is not 4 boxes with 25 or more balls.
  • there is not 5 boxes with 20 or more balls.
  • There is not 100 or more boxes with balls.


So, the highest amount of total balls is $99+49+33+24+19\cdot(99-4)=2010<2023$

Contradiction.

So, this is always possible.

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.

Editorial


Need a hint? Checkout the editorial.

View Editorial