$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$.
Problem
Source: BdMO 2023 Secondary National P4
Tags: combinatorics
15.04.2023 15:37
FTSOC, let the conclusion be false. Then there are 99 non empty buckets at most. So there is 1 bucket with at least \ceil{2023/99} = 21 balls We keep that bucket aside. So there are at most 2023-99 or 1924 balls remaining in at most 98 buckets. So there is one bucket with at most \ceil{1924/98} = 20 balls Next for at most 1825 balls there is one bucket with 19 balls For 1726 balls one bucket with 18 balls For 1627 balls one with 18 balls For 1528 balls one with 17 balls So now removing all the rest buckets and keeping 17 balls in each of these 6 buckets we get 102 balls in total Contradiction!
10.04.2024 16:33
If there are more than $99$ buckets, we are done. So, suppose there are exactly $99$ (possibly empty) buckets and let $a_1 \geq a_2 \geq a_3 \geq \dotsb \geq a_{99}$ be their contents. Note that once we have $ka_k \geq 100$ for some $k$, we are done. Indeed, in that case, we can achieve our goal by reducing each of $a_1, \dotsc, a_k$ into $a_k, \dotsc, a_k$ and throwing out the rest. So, suppose that $ka_k < 100$ for all $k$. This means that all the points $(k, a_k)$ lie under the curve $y = 100/x$. Therefore, we have \[ 2023 = a_1 + (a_2 + \dotsb + a_{99}) \leq 99 + \int_1^{99} \frac{100}{x} \,dx = 99 + 100\ln(99) < 559, \]contradiction!
11.07.2024 09:18
If there are at least $100$ initially non-empty buckets, then we remove balls until exactly one remains in each of them and we are done. So we may assume that we have exactly $99$ buckets, some of which may be empty. Let $a_1 \geq a_2 \geq a_3 \geq \dots \geq a_{99}$ be their initial amounts of balls. If there exists $k$ with $ka_k \geq 100$, then after removing completely $a_{k+1}$, $\ldots$, $a_{99}$ and decreasing each of $a_1,a_2,\ldots,a_{k-1}$ down to $a_k$, we would obtain exactly $k$ non-empty buckets with $a_k$ balls in each, in total $ka_k \geq 100$, hence we would be done. It remains to argue why such $k$ exists. Indeed, if opposite, then $ka_k \leq 99$ for all $k$, thus $a_k \leq \left \lfloor \frac{99}{k} \right \rfloor$, whence the total amount of balls $a_1 + a_2 + \cdots + a_{99}$ does not exceed $\sum_{k=1}^{99} \left \lfloor \frac{99}{k} \right \rfloor = 473 < 2023$, contradiction. (To calculate the sum, just note that each $50 \leq k \leq 99$ contributes with $1$, each $34 \leq k \leq 49$ contributes with $2$, each $25 \leq k \leq 33$ - with $3$, each $20 \leq k \leq 24$ - with $4$, and calculate quickly the rest.) P.S. Taking $a_k = \left \lfloor \frac{99}{k} \right \rfloor$ as initial distribution and utilizing the same argument shows that the best constant is $474$.