Competition problem — Combinatorics

Library / /13 of 14

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Singapore

Define a domino to be a $1 \times 2$ rectangular block. A $2023 \times 2023$ square grid is filled with non-overlapping dominoes, leaving a single $1 \times 1$ gap. John then repeatedly slides dominoes into the gap; each domino is moved at most once. What is the maximum number of times that John could have moved a domino? (Example: In the $3 \times 3$ grid shown below, John could move 2 dominoes: D, followed by A.)

| A | B | C |
|---|---|---|
| D | | |

Solution

Label the squares in the grid $(0,0)$ to $(2022, 2022)$ . Consider the position of the gap after a domino is moved. Note that the parity of the coordinates of the square containing the gap will not change. Also, the same square cannot contain the gap twice, otherwise this implies that a domino was moved into that square, and was moved out of the square again later, which is disallowed.

Considering coordinates modulo $2$ , in the $2023 \times 2023$ grid, there are $1012^2$ squares labelled $(0,0)$ , $1012 \times 1011$ squares labelled $(0,1)$ or $(1,0)$ , and $1011^2$ squares labelled $(1,1)$ . Hence, the number of moves is at most $1012^2 - 1$ , if all the $(0,0)$ squares are the 'gap square' at some point.

This is attainable by connecting these squares in a 'snake' pattern, and sliding dominoes accordingly; the remaining $1 \times 2022$ rectangles can be also tiled with dominoes that do not move throughout.

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.