In an exotic country, the National Bank issues coins that can take any value in the interval $[0, 1]$. Find the smallest constant $c > 0$ such that the following holds, no matter the situation in that country: Any citizen of the exotic country that has a finite number of coins, with a total value of no more than $1000$, can split those coins into $100$ boxes, such that the total value inside each box is at most $c$.
Problem
Source: BMO Shortlist 2021
Tags: Balkan, shortlist, 2021, combinatorics, coins, Boxes
08.05.2022 21:14
This was also P3 from the 2022 Azerbaijan TST and it was proposed by Romania.
09.05.2022 11:31
A very thoughtful problem on greedy algorithms! It makes sense to begin by considering arrangements with equal coins, i.e. $n \geq 1000$ coins, each with value $\frac{1000}{n}$. For any distribution in $100$ boxes, the Pigeonhole Principle guarantees a box with at least $\left\lceil \frac{n}{100} \right \rceil$ coins and hence with total amount at least $\left\lceil \frac{n}{100} \right \rceil \cdot \frac{1000}{n}$. To maximize the latter, let $n = 100q - r$ for $q\geq 1$ and $0\leq r \leq 99$ and we wish to max $\frac{1000q}{100q-r} = \frac{1000}{100 - \frac{r}{q}}$, i.e. to min $\frac{r}{q}$. This occurs for maximal $r$ and minimal $q$, i.e. $r=99$ and $q= 11$, which yields a sum $\frac{1000}{91}$ in at least one of the boxes. (Actually, $q=10$ is also possible for $n\geq 1000$, but then necessarily $r=0$ and we get a sum of $10$.) Hence the requirement is not always possible for $r< \frac{1000}{91}$. Now we prove for $r=\frac{1000}{91}$. Firstly we get rid of the large coins by noting that there are at most $1000$ coins of value exceeding $\frac{1000}{1001}$ (otherwise the total sum would exceed $1000$) and hence we may arrange these in the $100$ boxes in a way that each box coins at most $10$ from these (and so far the total sum in each box is at most $\frac{10000}{1001}$). Now we proceed greedily -- aiming to put one by one each of the remaining coins in at least one box. If at some point this is no longer possible, then we would have sums $x_1,\ldots,x_{100}$ in the boxes and adding the next coin (with value $x \leq \frac{1000}{1001}$) anywhere would lead to exceeding $\frac{1000}{91}$. In other words, $x_i + x > \frac{1000}{91}$ за $i=1,\ldots,100$, hence $x_1+x_2+\ldots+x_{100}+100x > \frac{10000}{91}$. But since $x_1+x_2+\ldots+x_{100}+x \leq 1000$ и $x\leq \frac{1000}{1001}$, we get $\frac{10000}{91} < 1000 + 99 \cdot \frac{1000}{1001} = \frac{10000}{91}$, contradiction. So the algorithm can be performed successfully and we are done.
05.09.2022 00:41
This one was proposed by me. Here is the solution I sent together with the problem. Fun fact: during high school, after I solved IMO 2014/5, I was so impressed with it that I eventually came up with this problem. If someone feels the 2 problems have the same feeling, that's the reason why The answer is $c=\frac{1000}{91}=11-\frac{11}{1001}$. Clearly, if $c'$ works, so does any $c>c'$. First we prove that $c=11-\frac{11}{1001}$ is good. We start with $100$ empty boxes. First, we consider only the coins that individually value more than $\frac{1000}{1001}$. As their sum cannot overpass $1000$, we deduce that there are at most $1000$ such coins. Thus we are able to put (at most) $10$ such coins in each of the $100$ boxes. Everything is all right: $10\cdot\frac{1000}{1001}<10<c=11-\frac{11}{1001}$. Next, step by step, we take one of the remaining coins and prove there is a box where it can be added. Suppose that at some point this algorithm fails. It would mean that at a certain point the total sums in the $100$ boxes would be $x_1,x_2,\dots,x_{100}$ and no matter how we would add the coin $x\left(\le \frac{1000}{1001}\right)$ in any of the boxes, that box would be overflowed i.e. it would have the total sum $> 11-\frac{11}{1001}$. Therefore, $$x_i+x>11-\frac{11}{1001},\text{ for all } i=\overline{1,100},\text{ so } x_1+x_2+\dots+x_{100}+100x>100\cdot\left(11-\frac{11}{1001}\right).$$But with $1000\ge x_1+x_2+\dots+x_{100}+x$ and $\frac{1000}{1001}\ge x$ we obtain the contradiction $$1000+99\cdot \frac{1000}{1001}>100\cdot\left(11-\frac{11}{1001}\right)\leftrightarrow 1000\cdot \frac{1100}{1001}>100\cdot 11\cdot \frac{1000}{1001}.$$Thus the algorithm does not fail and since we have finitely many coins, we will eventually reach to a happy end. Now we show that $c=11-11\alpha$ with $1>\alpha >\frac{1}{1001}$ does not work. Take $r\in \left[\frac{1}{1001}, \alpha\right)$ and a positive integer $n\in \left[1001, \frac{1000}{1-r}\right]$ (such an $n$ exists, because $\frac{1000}{1-r}\ge 1001\leftrightarrow r\ge \frac{1}{1001}$, true). Now we take $n$ coins each of value $1-r$. Their sum is $n\cdot \left(1-r\right)\le \frac{1000}{1-r}\cdot (1-r)=1000$. Now, no matter how we place them in $100$ boxes, as $n\ge 1001$, there exist $11$ coins in the same box. But $11\left(1-r\right)=11-11r>11-11\alpha$, so the constant $c=11-11\alpha$ does not work indeed.
14.06.2024 16:03
Answer: $11-\frac{1}{91}.$ Lower Bound: Take $1001$ coins with value $\frac{1000}{1001}$. There must exist a box with at least $11$ coins thus, $c\geq 11.\frac{1000}{1001}=\frac{1000}{91}$. Upper Bound: Let $a_1\geq a_2\geq ...\geq a_n$ be the values of the coins. Let $B_1,...,B_{100}$ be the boxes. We put $a_1,a_2,...,a_k$ into $B_1$ such that $a_1+...+a_k\leq 11-\frac{1}{91}<a_1+...+a_{k+1}$. After that we apply the same for $B_2,...,B_{100}$. Denote $|B_i|$ as the total value of coins in $B_i$. If $|B_i|<10-\frac{10}{1001},$ then \[a_i+...+a_j<10-\frac{10}{1001}<11-\frac{11}{1001}<a_i+...+a_j+a_{j+1}\implies a_{j+1}>11-\frac{11}{1001}-10+\frac{10}{1001}=1-\frac{1}{1001}\]\[10(1-\frac{1}{1001})>a_i+...+a_j>j.a_{j+1}=(j-i+1)(1-\frac{1}{1001})\implies 10>(j-i+1)\implies a_i+...+a_j+a_{j+1}<j-i+2<11\]Which is impossible. Hence $|B_i|\geq 10-\frac{10}{1001}$. Let $f=1000-\sum{B_i}$. Look at the case $f_{min}$. Note that $f_{min}\leq \frac{1000}{1001}$ since we can provide $|B_i|\geq 10-\frac{10}{1001}$. Let $x$ be a coin which is not in a box in case $f_{min}$. Since $|B_i|+x>11-\frac{1}{91},$ \[x\leq 1000-\sum{|B_i|}=\sum{10-|B_i|}\leq \sum{x+\frac{1}{91}-1}=100x-\frac{100.90}{91}\implies \frac{1000}{1001}>x\geq \frac{9000}{91.99}=\frac{1000}{1001}\]So we get a conrtadiction. This gives that there is no coin outside boxes and $|B_i|\leq 11-\frac{1}{91}$ as desired.$\blacksquare$