Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2014 IMO Problems/Problem 5"

m
(→‎Solution)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
For each positive integer <math>n</math>, the Bank of Cape Town issues coins of denomination <math>\tfrac{1}{n}</math>. Given a finite collection of such coins (of not necessarily different denominations) with total value at most <math>99+\frac{1}{2}</math>, prove that it is possible to split this collection into <math>100</math> or fewer groups, such that each group has total value at most <math>1</math>.
+
For each positive integer <math>n</math>, the Bank of Cape Town issues coins of denomination <math>\tfrac{1}{n}</math>. Given a finite collection of such coins (of not necessarily different denominations) with total value at most <math>99+\tfrac{1}{2}</math>, prove that it is possible to split this collection into <math>100</math> or fewer groups, such that each group has total value at most <math>1</math>.
 +
 
 
==Solution==
 
==Solution==
 +
The bound is not tight. We'll prove the result for at most <math>k - \frac{k}{2k+1}</math> with <math>k</math> groups.
 +
 +
First, perform the following optimizations.
 +
- If any coin of size <math>\frac{1}{2m}</math> appears twice, then replace it with a single coin of size <math>\frac{1}{m}</math>.
 +
- If any coin of size <math>\frac{1}{2m+1}</math> appears <math>2m+1</math> times, group it into a single group and induct downwards.
 +
Apply this operation repeatedly until it cannot be done anymore.
 +
 +
Now construct boxes <math>B_0</math>, <math>B_1</math>, ...., <math>B_{k-1}</math>. In box <math>B_0</math> put any coins of size <math>\tfrac 12</math> (clearly there is at most one).
 +
In the other boxes <math>B_m</math>, put coins of size <math>\frac{1}{2m+1}</math> and <math>\frac{1}{2m+2}</math> (at most <math>2m</math> of the former and at most one of the latter).
 +
Note that the total weight in the box is less than <math>1</math>.
 +
Finally, place the remaining ``light'' coins of size at most <math>\frac{1}{2k+1}</math> 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 <math>1</math>.
 +
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 <math>1 -\frac{1}{2k+1}</math>, meaning the total amount in the boxes is strictly greater than
 +
<cmath> k \left( 1 - \frac{1}{2k+1} \right) </cmath>
 +
which is a contradiction. (The inequality is strict since the pile has a coin leftover.)
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Latest revision as of 02:04, 26 August 2017

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$.

Solution

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$, ...., $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.)

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

2014 IMO (Problems) • Resources
Preceded by
Problem 4 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 6
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_IMO_Problems/Problem_5&oldid=87191"