Skip to main content
OlympiadHQ

Browse · MathNet

Print

Macedonian Junior Mathematical Olympiad

North Macedonia counting and probability

Problem

A pile of coins is given. We take one coin from the pile, and we arbitrarily divide the rest in two piles. Then, we choose an arbitrary pile from the two, we take one coin, and we divide the rest in two arbitrary piles, and so on. Is it possible after a finite number of repetitions of this procedure to get a number of piles such that in every one of them there are coins?
Solution
At the beginning, let the first pile contain coins. After every step, we consider the value , denoting the sum of the number of piles and the number of coins in them. We have i.e. is invariant (it does not change), at any step. Suppose that the required state is attainable i.e. let's have, after a finite number of steps, piles with coins in every one of them. Then, from the above stated, we get , i.e , which is not possible. According to this, the required state is not attainable.
Final answer
No

Techniques

Invariants / monovariants