Maths Olympiad Prep

Library / /51 of 64

Combinatorics Difficulty 8.2 Shortlist Find the answer

Consider an mm-by-nn grid of unit squares, indexed by (i,j)(i,j) with 1im1 \leq i \leq m and 1jn1 \leq j \leq n. There are (m1)(n1)(m-1)(n-1) coins, which are initially placed in the squares (i,j)(i,j) with 1im11 \leq i \leq m-1 and 1jn11 \leq j \leq n-1. If a coin occupies the square (i,j)(i,j) with im1i \leq m-1 and jn1j \leq n-1 and the squares (i+1,j),(i,j+1)(i+1,j), (i,j+1), and (i+1,j+1)(i+1,j+1) are unoccupied, then a legal move is to slide the coin from (i,j)(i,j) to (i+1,j+1)(i+1,j+1). How many distinct configurations of coins can be reached starting from the initial configuration by a (possibly empty) sequence of legal moves?

A number or a short expression. Spacing and $ signs are ignored.

Solution

The number of such configurations is (m+n2m1)\binom{m+n-2}{m-1}. Initially the unoccupied squares form a path from (1,n)(1,n) to (m,1)(m,1) consisting of m1m-1 horizontal steps and n1n-1 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 (m+n2m1)\binom{m+n-2}{m-1} (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 (i,j)(i,j1)(i+1,j1)(i,j) \to (i,j-1) \to (i+1,j-1). In this case the square (i+1,j)(i+1,j) must be occupied, so we can undo a move by replacing this sequence with (i,j)(i+1,j)(i+1,j1)(i,j) \to (i+1,j) \to (i+1,j-1).

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.