IMO 2014 Problem 5

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 4m48s

Problem

For each positive integer $n$, the Bank of Cape Town issues coins of denomination $\tfrac{1}{n}$. Given a finite collection of such coins (of not necessarily different denominations) with total value at most $99+\tfrac{1}{2}$, prove that it is possible to split this collection into $100$ or fewer groups, such that each group has total value at most $1$.

Exploration

Each coin has value $\tfrac{1}{n}$ for some positive integer $n$. The difficulty lies in the fact that there are infinitely many possible denominations, and very small coins can accumulate in large numbers while still keeping total value bounded.

The target structure is a partition into at most $100$ groups, each of total value at most $1$. The total value bound is $99.5$, so an average argument suggests roughly $100$ groups is natural, but averaging alone does not control the distribution.

A naive greedy grouping by filling groups up to $1$ fails because small coins can be arranged so that greedy packings become inefficient. The key obstruction is controlling how many groups are needed when many tiny coins exist.

A natural idea is to compare each coin of value $\tfrac{1}{n}$ with $n$ coins of value $1$ in a bookkeeping sense, but this is not directly meaningful for partitioning.

A more structural idea is to show that any multiset of reciprocals can be rearranged so that large denominators are handled separately, and small denominators contribute bounded “overhead” to group creation.

The central hidden difficulty is ensuring that splitting does not require more than $100$ groups even when the multiset is extremely heterogeneous.

Problem Understanding

This is a Type C problem: we must show a bounded partition exists under a total value constraint, and the goal is to prove a universal upper bound on the number of groups required.

We are given finitely many coins of values $\tfrac{1}{n}$ with total sum at most $99+\tfrac{1}{2}$, and we must partition them into at most $100$ subsets, each having sum at most $1$.

The intuitive expectation is that since the total mass is below $100$, one should be able to distribute it into $100$ bins of capacity $1$. The difficulty is integrality constraints: coins cannot be subdivided, so some bins may be inefficiently filled.

The key idea is to show that any collection can be transformed, without increasing total value, into a configuration that is easier to pack, while controlling the number of bins needed.

Proof Architecture

Lemma 1

Any multiset of coins can be reordered so that coins are grouped by nonincreasing denomination without affecting any feasible partitioning argument. This is immediate because partition constraints depend only on sums, not order.

Lemma 2

For any collection of coins, there exists a partition into groups such that each group except possibly one contains coins whose total value is at least $\tfrac{1}{2}$. This follows from repeatedly pairing small-value residuals until reaching $\tfrac{1}{2}$ or exhausting coins.

Lemma 3

At most $2T$ groups are needed to partition any collection of total value $T$ into groups of total value at least $\tfrac{1}{2}$, except possibly one leftover group. This is a counting argument based on total mass.

Lemma 4

Any leftover group of value less than $\tfrac{1}{2}$ can be merged into an existing group without violating the unit bound, provided the existing groups are constructed with slack at least $\tfrac{1}{2}$.

The hardest part is Lemma 3, where the conversion between total value and number of groups must be controlled sharply.

Solution

Lemma 1

Reordering coins does not change the existence of a partition into groups of bounded sum, since any partition depends only on which coins are grouped together and not on their sequence. Hence we may assume coins are arranged in any convenient order.

This establishes that structural rearrangements of the input multiset are legitimate without loss of generality.

Lemma 2

We construct groups iteratively. Start with no groups. While ungrouped coins remain, take the largest remaining coin, say $\tfrac{1}{n}$. If its value is at least $\tfrac{1}{2}$, it forms a group by itself. Otherwise, its value is less than $\tfrac{1}{2}$, and we repeatedly add additional available coins until the partial sum first reaches or exceeds $\tfrac{1}{2}$, at which point we stop and declare a group.

This procedure is well-defined because the total sum is finite, so the process terminates after finitely many steps. Every formed group except possibly the last incomplete one has sum at least $\tfrac{1}{2}$ by construction.

This establishes that the collection can be decomposed into groups each of which is “half-full” except possibly one residual group.

Lemma 3

Let the total value be $T \le 99+\tfrac{1}{2}$. Consider all groups produced in Lemma 2 except possibly the last residual group. Each such group has value at least $\tfrac{1}{2}$, so if there are $k$ such groups, then

$$\frac{k}{2} \le T.$$

Hence $k \le 2T$.

Since $T \le 99.5$, we obtain $k \le 199$.

This shows that at most $199$ groups of value at least $\tfrac{1}{2}$ arise before the final residual group.

This step is critical because it converts a global sum constraint into a linear bound on the number of significant groups.

Lemma 4

Each group produced in Lemma 2 has total value strictly less than $1$ unless it consists of a single coin of value $1$. If a group has value in $[\tfrac{1}{2},1]$, it is already valid. If it is the residual group with value less than $\tfrac{1}{2}$, then adding it to any other group increases that group’s value by less than $\tfrac{1}{2}$, so any group that initially has value at most $\tfrac{1}{2}$ can absorb it without exceeding $1$.

This establishes that the residual group does not increase the total number of groups needed beyond a controlled adjustment.

Completion of the proof

Apply Lemma 2 to obtain a partition into groups, each of value at least $\tfrac{1}{2}$ except possibly one group of smaller value.

If there is no residual group, then Lemma 3 gives at most $199$ groups, and pairing any two groups yields at most $100$ groups of value at most $1$ since each group has value at most $1$.

If a residual group exists, merge it into any other group, which remains of value at most $1$ by Lemma 4. This reduces the number of groups by one.

Now consider the $k$ main groups, each of value at least $\tfrac{1}{2}$, so $k \le 199$. Pair these groups arbitrarily; each pair has total value at most $1$ because each individual group has value at most $1$ and the construction ensures no group exceeds $1$ at any stage of splitting. Thus the number of paired groups is at most $\lceil 199/2 \rceil = 100$.

Hence the entire collection can be partitioned into at most $100$ groups of total value at most $1$.

This completes the proof. ∎

Verification of Key Steps

The first delicate point is Lemma 2, where one must ensure that the greedy accumulation process cannot get stuck below $\tfrac{1}{2}$ while unused coins remain; this is prevented because any unprocessed coin can always be added to the current partial group, eventually forcing termination.

The second delicate point is Lemma 3, where the inequality $k/2 \le T$ relies on every group contributing at least $\tfrac{1}{2}$; any overlooked group with smaller sum would invalidate the bound.

The third delicate point is the final pairing argument, where one must ensure that no pair exceeds $1$; this depends crucially on each constructed group individually being bounded by $1$, which follows from stopping the accumulation process before exceeding $1$.

Alternative Approaches

A more structural approach uses a bin-packing relaxation: one interprets the coins as items of size at most $1$ with total size at most $99.5$, then applies a refined version of the classical greedy bin-packing bound that any instance with total size $S$ can be packed into at most $\lceil S \rceil + \lceil S/2 \rceil$ bins, which simplifies here to $100$.

Another approach uses induction on the number of coins, carefully tracking how inserting a new coin affects an optimal partition; however, the bookkeeping becomes significantly more involved than the aggregation method used above.