Consider an -by- grid of unit squares, indexed by with and . There are coins, which are initially placed in the squares with and . If a coin occupies the square with and and the squares , and are unoccupied, then a legal move is to slide the coin from to . How many distinct configurations of coins can be reached starting from the initial configuration by a (possibly empty) sequence of legal moves?
Solution
The number of such configurations is . Initially the unoccupied squares form a path from to consisting of horizontal steps and vertical steps, and every move preserves this property. This yields an injective map from the set of reachable configurations to the set of paths of this form. Since the number of such paths is evidently (as one can arrange the horizontal and vertical steps in any order), it will suffice to show that the map we just wrote down is also surjective; that is, that one can reach any path of this form by a sequence of moves. This is easiest to see by working backwards. Ending at a given path, if this path is not the initial path, then it contains at least one sequence of squares of the form . In this case the square must be occupied, so we can undo a move by replacing this sequence with .