Problem

Source: 2013 Saudi Arabia IMO TST III p1

Tags: combinatorics, lattice, grid



Adel draws an $m \times n$ grid of dots on the coordinate plane, at the points of integer coordinates $(a,b)$ where $1 \le a \le m$ and $1 \le b \le n$. He proceeds to draw a closed path along $k$ of these dots, $(a_1, b_1)$,$(a_2,b_2)$,...,$(a_k,b_k)$, such that $(a_i,b_i)$ and $(a_{i+1}, b_{i+1})$ (where $(a_{k+1}, b_{k+1}) = (a_1, b_1)$) are $1$ unit apart for each $1 \le i \le k$. Adel makes sure his path does not cross itself, that is, the $k$ dots are distinct. Find, with proof, the maximum possible value of $k$ in terms of $m$ and $n$.