Waste less time on Facebook — follow Brilliant.
×

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.

Note by Calvin Lin
3 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears 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

Sort by:

Top Newest

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 - 3 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...