Maths Olympiad Prep

Library / /16 of 20

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it North Macedonia

A total of 2n2^n coins are distributed among several children. If one of the children has at least half of the coins, the coins are redistributed: coins are transferred from such a child to each of the other children in such a way that each of them gets as many coins as it had. In the case when one child possesses all the coins there is no possibility for redistribution. What is the greatest number of consecutive redistributions? (For example, if 3232 coins are distributed among 66 children in the following way: 1717, 22, 99, 11, 22, 11, then after one redistribution the children will have: 22, 44, 1818, 22, 44, 22 coins, respectively; in the example, that number is 22).
Explain your answer!

Solution

At most nn consecutive redistributions. We will start with an example showing that nn consecutive redistributions are possible. Let 2n2^n coins be distributed among 33 children initially as follows: 11, 2n1+2n2++22^{n-1} + 2^{n-2} + \dots + 2, 11. The successive redistributions (a total of nn) will be:
21,2n1+2n2++22,21 2^1, 2^{n-1} + 2^{n-2} + \dots + 2^2, 2^1
22,2n1+2n2++23,22 2^2, 2^{n-1} + 2^{n-2} + \dots + 2^3, 2^2
2n2,2n1,2n2 2^{n-2}, 2^{n-1}, 2^{n-2}
2n1,0,2n1 2^{n-1}, 0, 2^{n-1}
0,0,2n 0, 0, 2^n
Let us show that nn is the maximal number of consecutive redistributions. We start by assuming that there is an initial distribution for which there are at least n+1n+1 possible redistributions and we seek contradiction: let us note that after one redistribution the number of coins that each child has is divisible by 22 (each child to whom coins have been added has a doubled number of coins which is an even number, and the child from whom coins have been taken has again an even number of coins since there is a total of 2n2^n coins i.e. an even number of them). Analogously after the second redistribution each child has a number of coins that is divisible by 44, and so on, until the nn-th redistribution in which the number of coins each child has is divisible by 2n2^n; taking into account that the total number of coins is constant and equals 2n2^n, the only possible distribution (in some order) is 2n,0,0,,02^n, 0, 0, \dots, 0. But then there cannot be a next redistribution. Contradiction!

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.