Competition problem — Combinatorics

Library / /10 of 10

Combinatorics Difficulty 4.3 AIME Prove it North Macedonia

A pile of $2010$ 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 $3$ coins?

Solution

At the beginning, let the first pile contain $2010$ coins.
After every step, we consider the value $S$ , denoting the sum of the number of piles and the number of coins in them.
We have
$S_0 = 1 + 2010 = 2011,\quad S_1 = 2 + (2010 - 1) = 2011,\quad S_2 = 3 + (2009 - 1) = 2011$
i.e. $S$ 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, $n$ piles with $3$ coins in every one of them. Then, from the above stated, we get $S = n + 3n = 4n$ , i.e $2011 = 4n$ , which is not possible. According to this, the required state is not attainable.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.