http://www.artofproblemsolving.com/Forum/viewtopic.php?p=550634&sid=b86b26ebd9a4da148df0c43cb44622c1#p550634 is similar...

For every positive integer $n$, Cape Town Bank issues coins of $\dfrac{1}{n}$ value. Consider a finite collection of such coins (the coins do not necessarily have different values), having the sum of their values at most $99+\frac{1}{2}$. Prove that we can partition the collection into at most $100$ groups, such that the sum of the coins' values in each group does not exceed $1$.

Let me guess: The windmill problem in 2011, the tango problem in 2012, and the Cape town bank problem in 2014? windmill: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2363537 tango: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=492441

prague123 wrote: Let me guess: The windmill problem in 2011, the tango problem in 2012, and the Cape town bank problem in 2014? windmill: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2363537 tango: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=492441 Wrong. This problem was submitted by Luxembourg.

@fattypiggy123: The problem in your link is superficially similar, but not really close to the IMO problem. Also Iura's solution in the link does not seem to carry over; one can get stuck in the middle with some coins left over.

I agree with Manuel. The problem is quite a bit stronger.

Prove the more general statement: if there are a collection of finite coins with sum of values less than $k - \frac{1}{2}$ then we can divide the collection into $k$ groups with the sum of coin values in each group not exceeding 1. Induct on $k$; the base case is trivial. In the general case, if any subset of the finite coins has sum of values exactly $1$, we can put it into one group and induct immediately. Otherwise, call coins with value $1/m$ big if $m \leq 2k$ and small otherwise. First, for each big coin with value $1/m$, write $m$ as the product of an odd number and power of two, $m = 2^a \cdot \ell$, and classify the big coins into $k$ groups based on the value of $\ell$ (there are $k$ possible values of $\ell$, the odd numbers between $1$ and $2k - 1$.) Now note that each group has sum less than $1$, because if any group's sum exceeded $1$, due to the way each coin is a power of two multiple of another, we could have found a subset with sum exactly $1$ inside this group by greedily taking the largest coin, and then we'd have invoked the induction hypothesis. So otherwise, we've put the big coins into groups. Now, we just take the small coins one by one and insert them into any group where they fit. If some coin $1/m$ doesn't fit in any group, then every group sum is greater than $1 - 1/m$, so the total sum of values of coins already in the groups at that point is greater than $k - k/m > k - 1/2$ since $m$ is a small coin, a contradiction. Therefore this produces a valid division.

General problem For every positive integer $n$, Cape Town Bank issues some coins that has $\frac{1}{n}$ value. Let a collection of such finite coins (coins does not neccesarily have different values) which sum of their value is less than $r-\frac{1}{2}$. Prove that we can divide the collection into at most $r$ groups such that sum of all coins' value does not exceed $1$. Proof with induction For $r=1$ it is trivial. Now assume it is proven for $r = 1,\cdots, R-1$. We will prove it now for $r=R$. If there is a sum of some such reciprocals equal to $1$, we just take these in one group and by induction it will work for the other coins. So, if it would be impossible, we can look to the coins with value equal to a fraction of $S_1:$ $1, \frac{1}{2}, \frac{1}{2^2} \cdots$ $S_2:$$\frac 13, \frac{1}{2*3}, \frac{1}{2^2*3} \cdots$ $\cdots $ $S_{R}:$ $\frac{1}{2R-1}, \frac{1}{2(2R-1)},\frac{1}{2^2(2R-1)}\cdots$ $\cdots$ (others) CLAIM The sum of coins in $S_i$ for $1 \le i \le R$ is each time smaller than one. Proof: Else, the sum of som coins would be equal to one. Now for each coin with an other value, we place it in a $S_i$ with $i \le R$ such that the sum of values in $S_i$ keeps being smaller or equal to one. This is possible, as $min \{ S_i | i \le R\} \le \frac{R-0.5}{R} = 1 - \frac{1}{2R}$ and each new value is maximum $\frac{1}{2R+1}$. Hence we can place all others.

Unfortunately, there is a 2006 article by Bar-Noy, Ladner and Tamir, dealing with precisely this problem, which they call off-line UFBP ("unit fractions bin packing"); see http://pdf.aminer.org/000/267/584/dynamic_bin_packing_of_unit_fractions_items.pdf(mainly page 7 and 8). However, they only offer the bound $H+1$, where $H = \left \lceil 99 + \dfrac {1} {2}\right \rceil = 100$, thus $1$ worse than asked here! likely because they do not limit themselves at values $H - \dfrac {1}{2}$. Is this more general case that much harder? or is it easier? It is quite strange how this has escaped the attention of the Problem Selection Committee!?!

manuel153 wrote: @fattypiggy123: The problem in your link is superficially similar, but not really close to the IMO problem. Also Iura's solution in the link does not seem to carry over; one can get stuck in the middle with some coins left over. Indeed, the IMO problem might be harder but one can see from the solutions that they both share similar ideas, namely it is possible to ignore coins with big denomination.

Denote 100 by $n$ and $99\frac12$ by $n-1/2$ and consider the minimal counterexample, at first minimal by $n$, then minimal by number of coins. If the lightest coin has weight $m$, then by minimality we may partition the other coins by $n$ groups, all at most 1 and at least $1-m$ (else we may add the lightest coin). So $n-1/2>n(1-m)+m$, $m>\frac1{2n-2}$. Next, if there are two coins with weights $1/2k$, they may be replaced to $1/k$ and our counterexample is not minimal. Analogously, if there exist $p$ coins of weight $1/p$. Then the total weight is less than \[ \sum_{k=1}^{n-1} \left(\frac 1{2k}+\frac{2k-2}{2k-1}\right)\leq 1/2+(n-2)\cdot 1=n-3/2 \]and our counterexamples works for $n-1$ instead of $n$. A contradiction.

Is the value $99+\frac12=99.50$ in the problem statement tight? It cannot be raised to $99.99$ (there are simple counter examples), but I see no reason why it cannot be raised to $99.51$.

The bound is not tight. We'll prove the result for at most $k - \frac{k}{2k+1}$ with $k$ groups. First, perform the following optimizations. - If any coin of size $\frac{1}{2m}$ appears twice, then replace it with a single coin of size $\frac{1}{m}$. - If any coin of size $\frac{1}{2m+1}$ appears $2m+1$ times, group it into a single group and induct downwards. Apply this operation repeatedly until it cannot be done anymore. Now construct boxes $B_0$, $B_1$, \dots, $B_{k-1}$. In box $B_0$ put any coins of size $\tfrac 12$ (clearly there is at most one). In the other boxes $B_m$, put coins of size $\frac{1}{2m+1}$ and $\frac{1}{2m+2}$ (at most $2m$ of the former and at most one of the latter). Note that the total weight in the box is less than $1$. Finally, place the remaining ``light'' coins of size at most $\frac{1}{2k+1}$ in a pile. Then just toss coins from the pile into the boxes arbitrarily, other than the proviso that no box should have its weight exceed $1$. We claim this uses up all coins in the pile. Assume not, and that some coin remains in the pile when all the boxes are saturated. Then all the boxes must have at least $1 -\frac{1}{2k+1}$, meaning the total amount in the boxes is strictly greater than \[ k \left( 1 - \frac{1}{2k+1} \right) \] which is a contradiction. (The inequality is strict since the pile has a coin leftover.) And dear IMO jury: THIS IS NOT A NUMBER THEORY PROBLEM.

v_Enhance's argument raises the bound from $90.50000$ to $90.50248\ldots=99+\frac12+\frac{1}{402}$. How much farther can we go?

manuel153 wrote: v_Enhance's argument raises the bound from $90.50000$ to $90.50248\ldots=99+\frac12+\frac{1}{402}$. How much farther can we go? Acctually v_Enhance's argument bests the bound, but not so much, since $ \frac{k}{2k+1} \rightarrow \frac{1}{2}$ as $k \rightarrow \infty $ I believe that the intention of the problem proposer is to hide all of this by replacing $k$ by a large number (in this case, $k=100$, which is not so large...)

mavropnevma wrote: Unfortunately, there is a 2006 article by Bar-Noy, Ladner and Tamir, dealing with precisely this problem, which they call off-line UFBP ("unit fractions bin packing"); see http://pdf.aminer.org/000/267/584/dynamic_bin_packing_of_unit_fractions_items.pdf(mainly page 7 and 8). I have studied the proof on page 7 and 8 carefully. The result is quite trivial: pack as many items as you can pack by decreasing size, and you will be able to pack a lot. There is no way of deriving a solution to the IMO problem from these arguments. The best that you can get out of it is a solution for the cases where $99+\frac12$ is replaced by the smaller value $99$. For the larger value in the IMO problem one needs a smarter way of packing.

prague123 wrote: The result is quite trivial: pack as many items as you can pack by decreasing size, and you will be able to pack a lot. There is no way of deriving a solution to the IMO problem from these arguments. Actually, after the easy initial optimizations, v_Enhance's argument is more or less greedy (a priori greedy does at least as well as his setup, but in this case it's equivalent). Also, if we do another trivial optimization then I'm pretty sure we get a nontrivial asymptotic boost (still with the greedy algorithm): namely, we can reduce to the case where $\frac{1}{n}$ appears at most $p-1$ times, where $p$ is the smallest prime dividing $n$. In v_Enhance's solution we only work with $p=2$, but even just considering both $p=2$ and $p=3$ should give a nontrivial boost.

Yes, my solution is definitely greedy with optimizations. It's interesting to note the resemblance to this China TST 2006 problem, even though they turn out to be quite different because of the strict inequality. China TST wrote: Given positive integer $n$, find the biggest real number $C$ which satisfy the condition that if the sum of the reciprocals of a set of integers (They can be the same.) that are greater than $1$ is less than $C$, then we can divide the set of numbers into no more than $n$ groups so that the sum of reciprocals of every group is less than $1$.

Does anyone have some smallers counterexamples for $k$ instead of $100$? For every positive integer $n$, Cape Town Bank issues coins of $\dfrac{1}{n}$ value. Consider a finite collection of such coins (the coins do not necessarily have different values), having the sum of their values at most $k-\epsilon$. Prove that we can partition the collection into at most $k$ groups, such that the sum of the coins' values in each group does not exceed $1$.

Time to post some storage on problems that i thought were nontrivial! We prove at most n groups with total n-1/2. By optimality combine all denominations of 1/2k,1/2k into 1/k, and m of 1/m where m is odd. Now group them into types 1/2,(1/3 and 1/4),...,(1/(2n-1) and 1/(2n)) (they obviously fit since each group is at most 2/3+1/4<1): Note that each group doesn't exceed one since there are at most m-1 of 1/m, and we claim that we can add the other types of coins into these groups. Suppose not, then there is at least (1-1/(2n+1)) in each group for a total of n(1-1/(2n+1))>n-1/2, contradiction. Remark. This was not a very strong problem; there was probably some better bound because obviously we could optimize our groups more (e.g. put 2/3 with 1/4 with 1/12 optimizes more). However, I'm not going to spend the time to find a stronger bound, because this remark was come up in the last few seconds of posting this, and I shall not dwindle with you pessimists and keep working on problems. "bro sounds like plato" - some person on discod

This seems right, wouldn't mind somebody checking though We generalize to $k$ containers, with total sum at most $k - \frac{1}{2}$. First, we proceed with optimization. For any coins that sum to 1, place them into a container thus reducing the problem to $k - 1$ containers with a total sum at most $k - \frac{3}{2}$. For any two coins of denomination $\frac{1}{2d}$, combine them into one coin with denomination $\frac{1}{d}$. Note now there is at most one coin of form $\frac{1}{2d}$ for any $d$ and $k-1$ coins of the form $\frac{1}{k}$. Now consider placing all the coins into the containers such that the coins are grouped in the following manner: $\{\frac{1}{2}, \frac{1}{3}, \dots, \frac{1}{3} \}$ $\{ \frac{1}{4}, \frac{1}{5}, \dots, \frac{1}{5} \}$ $\{\frac{1}{6}, \frac{1}{7}, \dots, \frac{1}{7}\}$, and so on such that the last container contains coins of the form $\{\frac{1}{2k}, \frac{1}{2k+1}, \dots, \frac{1}{2k+1} \}$. It is easy to see that each box always has a group of coins that sum to less than 1. Then fill in the remaining gaps with smaller denominations. At the end of this process, let the minimal coin outside of a container have weight $\frac{1}{\alpha}$. Then the sum of denominations in the $i$-th container $C_i$, must be greater than $\frac{1}{\alpha}$ giving, \begin{align*} \sum C_i > k - \frac{k}{\alpha} \end{align*}However as $k - \frac{1}{2} > C_i$, we see that \begin{align*} k - \frac{1}{2} > k - \frac{k}{\alpha} \iff 2k > \alpha, \end{align*}a clear contradiction as we have already fit coins of this form. Remark: Just something I noticed, this isn't exactly optimal. Similar to how we bounded coins of the form $\frac{1}{2k}$ we could extend to bounding coins of the form $\frac{1}{pk}$ for some prime $p$ though I doubt that it strengthens the bound by a lot.

We change all pairs of the coins of the form $\frac{1}{2n}$ to one coin of value $\frac{1}{n}$. If we have $n$ coins of value $\frac{1}{n}$ we make a coin of value $1$. We prove the more general problem where we substitute $100$ with $x$. We make it so that we make all the $\frac{1}{1}$ coins irrelevant by decreasing our $x$. Notice that we have at most $1$ of each of the coins with even denominators and we have at most $2n$ of the coins with denominators $2n+1$. Claim 1: We can place all the coins from value $\frac{1}{2}, \frac{1}{3} \ldots \frac{1}{2x}$ proof: We let each of our $x$ piles contain the $x$ numbers with even denominators ($\frac{1}{2}, \frac{1}{4} \ldots \frac{1}{2x}$). We now can see that we can also place the odd coins in their "neighboring" piles. Specifically we claim that $\frac{n-1}{2n-1} + \frac{1}{2n} + \frac{n}{2n+1} \leq 1$ this is obvious by multiplying. We can see that this proves the claim. Claim 2: If we cannot place a coin with denominator greater than $2n$ than our total value is above $x - \frac{1}{2}$. proof: Let this coin have value $\frac{1}{y}$. We need the piles to each have more than $\frac{y-1}{y}$. Specifically we need the piles to sum to at least $x \frac{y-1}{y} \leq x - \frac{1}{2}$ which obviously has size issues when $y > 2x$ Combining these claims we see the result. $\blacksquare$

Solved in Cape Town. We prove this in general, that a collection of coins with total value at most $x-\frac 12$ can be split into $x$ such groups. First notice that we may assume that there is at most one of each coin of denomination $\frac 1{2n},$ since replacing two of them with one of denomination $\frac 1n$ is a more restrictive version of the same problem. Similarly we assume that there are at most $k-1$ coins of denomination $\frac 1k$ when $k$ odd (we may do this for $k=1$ since it is equivalent to decreasing $x$ by $1,$ and the situation cannot happen if $x=1$ so this will work). Now we place coins one at a time with nonincreasing denomination. Suppose that this fails for some coin with denomination $\frac 1{2n}.$ Then we have all groups have total value more than $1-\frac 1{2n},$ so the total value of coins is greater than $x-\frac {x-1}{2n}$ and thus $x-\frac{x-1}{2n} < x-\frac 12$ so simplifying gives $x > n+1.$ But now we can check that the total value of the coins placed before is less than or equal to $\frac 12+1-\frac 13+\frac 14+1-\frac 15+\cdots+1-\frac 1{2n-1}.$ This is less than $n-\frac 12$ so we must have $x-\frac x{2n}<n-\frac 12,$ but $x-\frac x{2n}=x\left(1-\frac 1{2n}\right) > (n+1)\left(1-\frac 1{2n}\right)=n-\frac 12+1-\frac 1{2n},$ contradiction. Now suppose this fails for a coin with denomination $\frac 1{2n+1}.$ We have all groups have total value more than $1-\frac 1{2n+1},$ so the total value of coins is more than $x-\frac{x-1}{2n+1}$ and this is less than or equal to $x-\frac 12$ so we can simplify to get $x>n+\frac 32.$ Now we can see that the total value of coins placed before is less than or equal to $\frac 12+1-\frac 13+\frac 14+\cdots+\frac 1{2n}+1-\frac 2{2n+1}$ which is less than $n+\frac 12$ so we must have $x-\frac x{2n+1}<n+\frac 12$ but $x-\frac x{2n+1}=x\left(1-\frac 1{2n+1}\right)>\left(n+\frac 32\right)\left(1-\frac 1{2n+1}\right)=n+1-\frac 1{2n+1}>n+\frac 12,$ contradiction, so we are done.

If we have two coins of denomination $\frac{1}{2n}$, we merge them into one coin of denomination $\frac{1}{n}$; we can then separate the coin into two once we've allocated the piles. Similarly, if we have $2n-1$ coins of denomination $\frac{1}{2n-1}$, we just place them all into one pile since that's extremely efficient (no leftover space). So we may now assume we have at most one coin of denomination $\frac{1}{2n}$ and at most $2n-2$ coins of denomination $\frac{1}{2n-1}$. For $1 \leq i \leq 100$, we place all coins of denomination $\frac{1}{2i}$ and $\frac{1}{2i-1}$ in pile $i$. We now fill in all spaces with coins of denomination $\frac{1}{201}$, $\frac{1}{202}$, etc. When we can't fill any more spaces, each pile must be at least $\frac{200}{201} > \frac{199}{200}$ in value, for a total of $\frac{199}{2} =99.5$ spent; we've used all our coins.

Generalize $100$ to $n$. First, do the following reductions: 1. If there are two coins of denomination $\frac{1}{2k}$ for any $k \ge 1$, replace them with one coin of denomination 2. If there are $2k+1$ coins of value $\frac{1}{2k+1}$, replace them with a coin of value $1$. If we can find a valid grouping after these reductions then we can also find one before since we can split the coins in both bullet points. If we have a coin of denomination $1$, then we're done by induction, so assume we don't. Now place the one (if we one) $\frac{1}{2}$ value coin into one group. Next, for all $1 \le k \le n-1$ place all $\frac{1}{2k+1}$ and $\frac{1}{2k+2}$ coins into one group. By our restrictions, this group has value at most \[\frac{2n}{2n+1} + \frac{1}{2n+2} < 1\]Now we can just shove the rest of the coins that have value $\le \frac{1}{2n+1}$ into any group that still has room. FTSoC, assume we can't do this. Then the total value is at least \[n \cdot \left(1-\frac{1}{2n+1}\right) > n-\frac{1}{2}\]a contradiction, which finishes the problem.

Replace $100$ with general $k$. Now we can make the following optimization. Assume that the Bank of Cape Town allows us to trade $2m - 1$ coins of denomination $\frac{1}{2m - 1}$ for a coin of denomination $1$ and $2$ coins of denomination $\frac{1}{2m}$ for a single coin of denomination $\frac{1}{m}$. We make this optimization repeatedly, and are left with at most $2m - 2$ coins of denomination $\frac{1}{2m - 1}$ and at most $1$ coin of denomination $\frac{1}{2m}$. Now we can set aside all coins that have denomination $1$. Place all coins of denomination $\frac{1}{2m - 1}$ and $\frac{1}{2m}$ in pile $m$ which is valid since the total value of pile $m$ is at most $\frac{2m - 2}{2m - 1} + \frac{1}{2m} < 1$. Notice that all coins of denomination $< \frac{1}{2k}$ can be placed into groups. If not, then we can create pre-existing groups and show that it is impossible that the coins of denomination $< \frac{1}{2k}$ cannot fit anywhere.. Then this implies that all of the groups have remaining space that is $< \frac 1 2n$ which is a contradiction since the sum of the preexisting groups would be $> n - \frac 12$, so we are done.

Incorrect solution

Replace 100 with $n$ and $99.5$ with $n-0.5$. We induct on $n$. Replace two coins $\frac1{2m}$ with one coin $\frac1m$. Replace $2m+1$ coins $\frac1{2m+1}$ with $1$ coin, and make separate group (this is just induction hypothesis). Keep doing this until we cannot. At this point we have at most 1 coin with denominator is even and at most $2t$ coins if denominator = $2t+1$. Consider set $S_0$ containing the $\frac12$ coin, and $S_m$ containing all coins $\frac1{2m}$ and $\frac1{2m+1}$ for every $m<100$. Then, each set has sum at most 1. We are now left with denominations $\frac1{201},\frac1{202},$ etc. Distribute them into the sets, we can do this because the sets have sum less than 1. Suppose we are still left with some "extra" denominations. So, the "sets" each have sum as at least $1-\frac1{201}=\frac{200}{201}$. Since there are 100 such sets, we already have a total sum of $\frac{20000}{201}>\frac{199}2$, a contradiction.

Replace $100$ with a general $n$. We will perform an algorithm on the coins as follows: Exchange $2$ coins of denomination $\tfrac{1}{2k}$ for a coin of denomination $\tfrac{1}{k}$. Exchange $k$ coins of denomination $\tfrac{1}{k}$ for a coin $1$. It is obvious that if we can split the collection into $n$ groups after the algorithm, we can make the split before. Hence, we can assume that the algorithm is performed as many times as possible. We are left with at most $2k-2$ coins of denomination $\tfrac{1}{2k-1}$ and at most $1$ coin of denomination $\tfrac{1}{2k}$. Group the above coins together, which is possible since the sum of each group can equal at most \[\frac{2k-2}{2k-1}+\frac{1}{2k} = \frac{4k^2-2k-1}{4k^2-2k} < 1.\] Then, for all coins with denomination less than $\tfrac{1}{2n}$, we can simply add them to groups that have room. If there is not room for such a coin, then each group has sum greater than $1-\tfrac{1}{2n}$, which implies a total sum greater than $n-\tfrac{1}{2}$, a contradiction. Hence, we have a desired grouping. $\blacksquare$

This was massively overestimated in difficulty. We can use induction, so that, if the coin denomination of value $\frac{1}{k}$ is repeated more than $k$ times, we can simply put a whole bucket just for that coin. Also, we can take any even valued coin which is repeated more than twice, and group two of them together, so that $2$ coins of denomination $\frac{1}{2k}$ become one of denomination $\frac{1}{k}.$ Now, we have reduced the problem to showing that we can group coins with total value at most $\frac{2n+1}{2}$ into at most $n+1$ groups, where the coins of even denomination appear at most once, and the coins of denomination $2i+1$ occur at most $2i$ times. Put the coins of denomination $2$ into the first bucket (we do not have any coins of denomination $1$). For the other buckets, put one coin of denomination $2i$ in, and all of the other coins of denomination $2i-1$ as well. Then, notice that we are left over with denominations at least $2n+1$ which cannot be stored in its own bucket, since then there would be $1$ too many buckets. These denominations can be tossed into any buckets with leftover room. Then, we can see that it is always possible to put in these last coins, since otherwise we would have more than $(k-1)+\frac{1}{2}$ in denominations. Hence, we are done.

I will prove that if we have $2n+\frac{1}{2}$ as the total value we can split it into $n$ groups of value at most $1$. Suppose we have $2$ elements $\frac{1}{2n}$, we can treat this as one element of $\frac{1}{n}$. We can also say that we don't have $n$ elements of $\frac{1}{n}$ because we can induct from previous case that this works. Now consider $2n$ categories labled with the odd values from $1$ to $2n$. Clearly we can put any elements of the form $m2^k$ into the category labled $m$ without exceeding $100$ elements total. Now consider the elements smaller than $\frac{1}{4n}$, suppose an element smaller than that can not be put in any category, this means the total sum of all categories is more than $2n+\frac{1}{2}$ which is a contradicition.

(Replace $100$ with $N$) Consider the following step: If sum of multiple coins sum to a number of the form $\frac{1}{n}$, then we remove all of them and add a $\frac{1}{n}$ coin. In the current coin collection, assume that there are $d$ coins with value $1$, then we make single-ton groups with them and thus, we replace $N$ with $N-d$. We make the number $\frac{1}{2}$ into a single-ton group. For every $2 \le k \le N-1$, we have at-most one occurrence of $\frac{1}{2k}$ and at-most $2k$ occurrences of $\frac{1}{2k+1}$ and therefore, they sum to: $$\frac{1}{2k}+\frac{2k}{2k+1} < 1.$$Now, we claim that, for all $t \ge 2N-1$, we can freely skip it: If not, then each group has sum of at-least $1-\frac{1}{t}$ and therefore: total sum is at-least: $$\frac{N} - \frac{N-1}{t} \le N-\frac{1}{2}$$But this implies: $t \le 2N-2$, contradiction. Thus, we can place denominations of the form $\frac{1}{t}$ for all $t \ge 2N-1$ into any group which has space for it.

Solved this with a concerning amount of hints. But then again, I'm bad at combinatorics and especially at local arguments in particular. We approach this via induction. We prove the more general statement that for all $k\geq 1$, we are able to split a collection of coins of total value at most $(k-1)+\frac{1}{2}$ into $k$ groups, such that each group has a total value at most 1, for all $k\geq 0$. For $k=0$, the claim is obvious as we can simply chuck all the coins in one group. We first conduct the following optimization. Whenever we have 2 coins of denomination $\frac{1}{2r}$ we exchange it for a coin of value $\frac{1}{r}$ and whenever we have $r$ coins of denomination $\frac{1}{r}$, we exchange it for a coin of value 1. It is easy to see that if we are able to achieve our goal after this exchange, we are most obviously able to achieve it before (simply place the smaller coins where u placed the equivalent larger coin). Now, we place all the coins of size 1 (say there are $k$ of them) in separate boxes. Thus, we have coins of total value $(n-k)+\frac{1}{2}$ to be separated into $(n-k+1)$ groups which is guaranteed to be possible by the induction hypothesis. So, assume we have no coins of size 1 after this optimization. In this setup, we have at most 1 coin of value $\frac{1}{2k}$ for each $k \geq 1$ and at most $2k$ coins of value $\frac{1}{2k+1}$ for each $k\geq 1$. Algorithm : We place all coins of value $\frac{1}{2}$ in box $B_1$. For all $k\geq 2$, we then place all coins of value $\frac{1}{2k}$ and $\frac{1}{2k-1}$ in Box $B_k$. Proof : If $S_k$ is the total value of $B_k$ in such an assignment of coins, \[S_k \leq \frac{2k-2}{2k-1} +\frac{1}{2k} = \frac{4k^2-4k+2k-1}{4k^2-2k} = \frac{4k^2-2k-1}{4k^2-2k}<1\]Thus, we can place all coins of weights $\frac{1}{r}$ for $r\leq 2n$ using this algorithm. Now, we have successfully placed all the coins of denominations greater than $\frac{1}{2n}$. For the rest, we perform the following greedy algorithm. Algorithm : We pick the unplaced coin with the largest denomination ($\frac{1}{i}$-for smallest $i$) and place it in the left-most box which it can occupy (boxes are placed in the order $B_1,B_2,\dots,B_n$ from left to right). Proof : We claim that this successfully disposes of all the other coins. Assume that we eventually get stuck. That is, there exists a coin with denomination $\frac{1}{r}$ which cannot be placed in any of the boxes. Thus, each box has total value greater than $1-\frac{1}{r}$. Thus, the sum of total assigned coins $S$ is, \[(n-1)+\frac{1}{2}> S > n\left(1-\frac{1}{r}\right) = n - \frac{n}{r}\]which rearranges to $\frac{n}{r} < \frac{1}{2} \implies r < 2n$. But, we have already packed in coins of size $\frac{1}{r}$ for $r<2n$ and are dealing with smaller coins. Thus, this algorithm never breaks and we can reach our goal. This means the induction is complete. Thus, it is always possible to split a finite collection of coins with total value at most $99+\frac{1}{2}$ into 100 or fewer groups, such that each group has total value at most 1, as desired.

Used an embarrassingly high number of hints. Darn. Replace $100$ by $n.$ First, we optimize as follows: Given two coins of type $\frac{1}{2k}$ we "combine" them into a coin of type $\frac 1k.$ Given $2k+1$ coins of type $\frac{1}{2k+1}$ we combine them into one coin of type $\frac{1}{1}.$ Now we ignore all of the coins that have been combined as integers. Let the sum of the remaining coins be at most $\frac{2i-1}{i}.$ We will fit them into $i$ boxes. In the first box we put all coins of type $\frac 12$, of which there are $1$ or less. In the $j$th box we put the coins of type $\frac{1}{2j-1}$ and $\frac{1}{2j}.$ Of the former type there are at most $2j-2$ and of the latter type there is at most $1$ so the box has value at most $$1-\frac{1}{2j-1}+\frac{1}{2j}<1.$$Now all that remains are coins of value less than $\frac{1}{2i}.$ We perform a greedy algorithm and fit a remaining coin into any box that can fit it. I claim this fits all the coins. FTSOC this is not true. Then each coin already fits more than $1-\frac{1}{2i+1}$ worth of coins. Over all $i$ boxes, this combines to a total value of $i-\frac{i}{2i+1}>i-\frac{1}{2}$ which is a contradiction. Q.E.D.