Problem

Source: 2023 Singapore MO Round 2 Junior Q3

Tags: combinatorics



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$.) [asy][asy] unitsize(18); draw((0,0)--(3,0)--(3,3)--(0,3)--(0,0)--cycle); draw((0,1)--(3,1)); draw((2,0)--(2,3)); draw((1,1)--(1,3)); label("A",(0.5,2)); label("B",(1.5,2)); label("C",(2.5,2)); label("D",(1,0.5)); [/asy][/asy]