When can the cat and mouse meet?

Question

A cat and a mouse occupy the top right and bottom left cells respectively of an $m \times n$ rectangular grid, where $m, n > 1$. Each second they both move diagonally one cell.

For which pairs $(m, n)$ is it possible for the cat and the mouse to occupy the same cell at the same time?

Note: For every pair $(m, n)$ you must either prove that it is impossible for the cat and the mouse to occupy the same cell at the same time, or explain why there is a sequence of moves that ends with the cat and the mouse occupying the same cell at the same time.

---

Attribution: UK Intermediate Mathematical Olympiad Maclaurin paper 2021

Answer 1

I claim that you can do this if and only if

$m$ and $n$ are both odd.

Here's why:

First, there's the obvious parity issue: if one of $m$ and $n$ is even and the other is odd, then we can checkerboard-color the grid to see that they don't have access to the same cells.


Here, the cat is stuck on the white squares, while the mouse is stuck on the black squares.


There's also another parity condition, though - consider what happens when both $m$ and $n$ are even.

If you tilt your head 45 degrees to the right, you can see that there's a blue-and-red checkerboard now on the white cells only. Each turn, both of them swap colors; since one starts on blue and the other starts on red, they can never be the same color.

Finally, it remains to show that it's always possible to do when $m$ and $n$ are both odd. This is pretty easy: the mouse can move back and forth between the bottom left corner and the only adjacent cell to it, while the cat goes down and meets the mouse.
If both $m$ and $n$ are odd, then using the red/blue coloring, both of them will start on the same color. This shows that they will arrive on the same cell at the same time.

Answer 2

To end up moving $h$ cells to the right and $v$ cells upwards, you move:

$n_1$ times 1 cell to the right, 1 upwards,
$n_2$ times 1 right, 1 down,
$n_3$ times 1 left, 1 up,
$n_4$ times 1 left, 1 down.

Then $(n_1+n_2)-(n_3+n_4)=h$
$(n_1+n_3)-(n_2+n_4)=v$

One of $h$ and $v$ being odd with the other even creates a contradiction as to whether $n_1+n_2+n_3+n_4$ is odd or even. Either both are odd or even, and so is the number of moves. Now, the cat and mouse have to make the same number of moves. When they meet, combining their path creates a new one where one entity goes from one corner to the opposite. This new path must include an even number of moves because it's a multiple of 2. For that, both the $h$ and $v$ must be even, which is only possible if the dimensions of the grid are both odd.