Maths Olympiad Prep

Library / /5 of 5

Combinatorics Difficulty 6.8 National Olympiad Prove it Switzerland

Problem:

Let nn be a positive integer. Kimiko starts with nn piles of pebbles each containing a single pebble. She can take an equal number of pebbles from two existing piles and combine the removed pebbles to create a new pile. Determine, in terms of nn, the smallest number of nonempty piles Kimiko can end up with.

Solution

Solution:

If nn is a power of 22 then there may be only one pile remaining; otherwise, there will be at least two piles remaining, but this can be attained. It is clear why you can reach one pile if nn is a power of 22: the first n/2n/2 piles can each receive pebbles from two piles with a pebble, the next n/4n/4 piles can inherit two pebbles from two piles with two stones each and so forth, doubling each "generation".

Suppose nn is not a power of 22 and write n=c2kn = c 2^{k}, c>1c > 1. We claim there is always a pile with a number of pebbles not divisible by cc. This is clearly true initially. Suppose it is not true at some point, and consider what happens when you next create a pile. If this pile does not receive some pebbles from the existing pile(s) possessing a quantity not divisible by cc, then they will maintain the invariant. If instead the pile receives some xx pebbles from them, then the pile will have 2x2x, but cc does not divide 2x2x as cc is odd and does not divide xx. In particular, one can never reduce to a single pile, as nn is of course divisible by cc.

Finally, we show that you can always reach just two piles. This can be done via induction: Write n=2k+rn = 2^{k} + r, r<2kr < 2^{k}. If we get to a pile with rr pebbles, then the remaining 2k2^{k} pebbles can always be consolidated into one pile, irrespective of the initial distribution: we begin by having 2k12^{k-1} piles receiving 11 pebble from two piles, but not from each other, creating 2k12^{k-1} piles with 22 pebbles each, and then double each generation like above. To create a pile with rr pebbles, we have two cases. If r<2k1r < 2^{k-1} then simply create two piles with 2k12^{k-1} pebbles by doubling, and then take away some pebbles from both of them so that they both have rr pebbles, and set one of them aside. If r>2k1r > 2^{k-1} then create a pile with 2k2^{k} pebbles and a pile with 2k12^{k-1}, and again take away some pebbles from both of them so the larger pile has rr pebbles. One can formulate an alternative induction argument where you use the fact nn can be consolidated into two piles of size n1n-1 and 11, to show that n+1n+1 can be consolidated into n+2n+2 and 22 and then show via a number-theoretic argument that you can reach n+1n+1 and 11 from here if nn is odd.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.