IMO 1994 SL C4

Origin: EST | Category: Combinatorics

Problem

There are n + 1 fixed positions in a row, labeled 0 to n in increasing order from right to left. Cards numbered 0 to n are shuffled and dealt, one in each position. The object of the game is to have card i in the ith position for 0 \leqi \leqn. If this has not been achieved, the following move is executed. Determine the smallest k such that the kth position is occupied by a card l > k. Remove this card, slide all cards from the (k + 1)st to the lth position one place to the right, and replace the card l in the lth position. (a) Prove that the game lasts at most 2n −1 moves. (b) Prove that there exists a unique initial configuration for which the game lasts exactly 2n −1 moves.

Solution

(a) For i = 1, . . . , n, let di be 0 if the card i is in the ith position, and 1 otherwise. Define b = d1 + 2d2 + 22d3 + \cdot \cdot \cdot + 2n−1dn, so that 0 \leqb \leq 2n −1, and b = 0 if and only if the game is over. After each move some digit dl changes from 1 to 0 while dl+1, dl+2, . . . remain unchanged. Hence b decreases after each move, and consequently the game ends after at most 2n −1 moves. (b) Suppose the game lasts exactly 2n −1 moves. Then each move de- creases b for exactly one, so playing the game in reverse (starting from the final configuration), every move is uniquely determined. It follows that if the configuration that allows a game lasting 2n −1 moves exists, it must be unique. Consider the initial configuration 0, n, n −1, . . . , 2, 1. We prove by induction that the game will last exactly 2n −1 moves, and that the card 0 will get to the 0th position only in the last move. This is trivial for n = 1, so suppose that the claim is true for some n = m −1 \geq1 and consider the case n = m. Obviously the card 0 does not move until the card m gets to the 0-th position. But if we ignore the card 0 and consider the card m to be the card 0, the induction hypothesis gives that the card m will move to the 0th position only after 2m−1 −1 moves. After these 2m−1 −1 moves, we come to the configuration 0, m −1, . . . , 2, 1, m. The next move yields m, 0, m −1, . . . , 2, 1, so by the induction hypothesis again we need 2m−1 −1 moves more to finish the game.