IMO 2014/5

For each positive integer $n$ , the Bank of Cape Town issues coins of denomination $\frac{1}{n}$ . Given a finite collection of such coins (of not necessarily different denominations) with total value at most $99 + \frac{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.

#Combinatorics #NumberTheory #IMO

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Outline; will complete this later.

The idea is to induct. Replace the $100$ by $n.$ The sum doesn't exceed $k - \dfrac{1}{2}$ and we need to show that they can be split in to $n$ groups such that the sum of no groups exceeds $1$ . The base case is trivial; suppose the assertion is true for some $1, 2, \cdots , k-1.$ Let $j$ be the largest odd factor of $k,$ and divide the numbers less than $k$ in to $k+1$ groups based on their largest odd divisors (all numbers with their largest odd divisors $x$ go in group $x$ ). It is easy to show that the sum of no group exceeds $1$ . It it also easy to prove that all the coins which are smaller than $\dfrac{1}{2k}$ fit in to these groups without the sum exceeding $1,$ so the induction step is complete.

Sreejato Bhattacharya - 6 years, 11 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$