Let $m$ and $n$ be positive integers. A $2 m \times 2 n$ grid of squares is coloured in the usual chessboard fashion. Find the number of ways of placing $m n$ counters on the white squares, at most one counter per square, so that no two counters are on white squares that are diagonally adjacent. An example of a way to place the counters when $m=2$ and $n=3$ is shown below.

![](https://cdn.mathpix.com/cropped/2024_04_17_a44cdb2aaa22cdcae469g-4.jpg?height=412&width=610&top_left_y=610&top_left_x=801)
Divide the chessboard into $m n 2 \times 2$ squares.

![](https://cdn.mathpix.com/cropped/2024_04_17_a44cdb2aaa22cdcae469g-4.jpg?height=404&width=702&top_left_y=1224&top_left_x=755)

Each $2 \times 2$ square can contain at most one counter. Since we want to place $m n$ counters, each $2 \times 2$ square must contain exactly one counter.

Assume that the lower-right corner of the $2 m \times 2 n$ chessboard is white, so in each $2 \times 2$ square, the upper-left and lower-right squares are white. Call a $2 \times 2$ square UL if the counter it contains is on the upper-left white square, and call it LR if the counter it contains is on the lower-right white square.

Suppose some $2 \times 2$ square is UL. Then the $2 \times 2$ square above it (if it exists) must also be UL, and the $2 \times 2$ square to the left of it (if it exists) must also be UL.

![](https://cdn.mathpix.com/cropped/2024_04_17_a44cdb2aaa22cdcae469g-4.jpg?height=415&width=417&top_left_y=2113&top_left_x=903)

Similarly, if some $2 \times 2$ square is LR, then the $2 \times 2$ square below it (if it exists) must also be LR, and the $2 \times 2$ square to the right of it (if it exists) must also be LR.

![](https://cdn.mathpix.com/cropped/2024_04_17_a44cdb2aaa22cdcae469g-5.jpg?height=417&width=420&top_left_y=537&top_left_x=901)

Then the collection of UL $2 \times 2$ squares form a region that is top-justified and left-justified, and the collection of LR $2 \times 2$ squares form a region that is bottom-justified and right-justified. This means that the boundary between the two regions forms a path between the lower-left corner and upper-right corner of the $2 m \times 2 n$ chessboard.

![](https://cdn.mathpix.com/cropped/2024_04_17_a44cdb2aaa22cdcae469g-5.jpg?height=420&width=734&top_left_y=1248&top_left_x=739)

Conversely, any path from the lower-left corner to the upper-right corner, where each step consists of two units, can serve as the boundary of the UL squares and LR squares. Thus, the number of ways of placing the counters is equal to the number of paths, which is $\left(\begin{array}{c}m+n \\ m\end{array}\right)$.