Maths Olympiad Prep

Library / /31 of 31

Combinatorics Difficulty 9.1 IMO level Prove it Baltic Way

There are 20192019 plates placed around a round table and on each of them there is one coin. Alice and Bob are playing a game that proceeds in rounds indefinitely as follows. In each round, Alice first chooses a plate on which there is at least one coin. Then Bob moves one coin from this plate to one of the two adjacent plates, chosen by him. Determine whether it is possible for Bob to select his moves so that, no matter how Alice selects her moves, there are never more than two coins on any plate.

Solutions — 2

Solution 1

Answer: Yes, it is possible.
We provide a suitable strategy for Bob. Given a configuration of coins on the plates, let a block be any inclusion-wise maximal contiguous interval consisting of non-empty plates. The idea of Bob's strategy is to maintain the following invariant throughout the game: in every block, all plates except at most one contain exactly one coin, while the remaining one contains two coins. Since the total number of coins is always equal to the total number of plates, this is equivalent to the following condition: either every plate contains exactly one coin (as in the initial configuration), or in every block there is exactly one plate with two coins and all the other plates of the block contain one coin each, and moreover the blocks are delimited by single plates containing zero coins. It now suffices to show that in any configuration CC satisfying the invariant, regardless of which plate Alice picks, Bob can always select his move so that the invariant is maintained after the move. We consider two cases: either Alice picks a plate with two coins, or with one coin. Suppose first that Alice picks a plate with two coins. If any of the adjacent plates contains one coin, then Bob moves a coin to this plate and the invariant is maintained - the set of blocks remains unchanged and only within one block the plate with two coins has moved. If both of the adjacent plates contain zero coins, then Bob moves a coin to any of them. Thus, one single-plate block disappears and some other block gets extended with two plates with one coin each; hence, the invariant is maintained.
Suppose now that Alice picks a plate with one coin. If the configuration is as the initial one - every plate contains one coin - then any move of Bob maintains the invariant. Otherwise, within the block BB containing the plate PP chosen by Alice there is another plate PP' containing two coins, and BB does not contain all the plates. Without loss of generality, suppose that in order to get from PP' to PP within BB one needs to go in the clockwise direction. Then the move of Bob is to move the coin from PP also in the clockwise direction. Then either PP is the clockwise endpoint of BB, and we just move one plate with one coin from BB to the next block in the clockwise direction, or PP is not the clockwise endpoint of BB, and the move results in dividing BB into two blocks, each containing exactly one plate with two coins. In both cases, the invariant is maintained.

Solution 2

Let's assign to each coin two plates: its original plate, and the plate next to it on the right. Bob will make sure that each coin will always lie on one of the two plates assigned to it. (When Alice chooses a plate, Bob moves an arbitrary coin from this plate to the second plate assigned to it.) It is clear that each plate can contain only two coins: the one that was originally on it, and its left neighbor.

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.