Browse · MathNet
PrintBaltic Way shortlist
Baltic Way counting and probability
Problem
There are 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.
Solution
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 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 containing the plate chosen by Alice there is another plate containing two coins, and does not contain all the plates. Without loss of generality, suppose that in order to get from to within one needs to go in the clockwise direction. Then the move of Bob is to move the coin from also in the clockwise direction. Then either is the clockwise endpoint of , and we just move one plate with one coin from to the next block in the clockwise direction, or is not the clockwise endpoint of , and the move results in dividing into two blocks, each containing exactly one plate with two coins. In both cases, the invariant is maintained.
---
Alternative solution.
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.
---
Alternative solution.
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.
Final answer
Yes
Techniques
Invariants / monovariantsGames / greedy algorithms