Library / /9 of 11

, 2013

Combinatorics Difficulty 8.5 Shortlist Prove it Saudi Arabia

Adel draws an $m \times n$ grid of dots on the coordinate plane, at the points of integer coordinates $(a, b)$ where $1 \leq a \leq m$ and $1 \leq b \leq n$ . He proceeds to draw a closed path along $k$ of these dots, $(a_{1}, b_{1}),(a_{2}, b_{2}), \ldots,(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 \leq i \leq 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$ .

Solution

If $m$ is even, Adel can draw the following closed path which passes through all the dots of his grid. Therefore, the maximum possible value of $k$ is $mn$ .

If $n$ is even, Adel can draw a similar closed path obtained by symmetry with respect to the first diagonal. Therefore, the maximum possible value of $k$ is $mn$ .

If $mn$ is odd, Adel can draw the following closed path which passes through $mn-1$ dots of his grid:

It remains to prove that this is the maximal possible value of $k$ . For this, assign black color to all dots of the grid of coordinates $(a, b)$ with $a+b$ odd and white color to all dots with $a+b$ even. Any consecutive dots in a path $(a_{1}, b_{1}),(a_{2}, b_{2}), \ldots,(a_{k}, b_{k})$ that Adel can draw have different colors. Therefore, the colors of the first and last dots in Adel's path describe the parity of the length of the path. Since the path of Adel is closed, it will start and end with the same color and therefore, its length is even. Therefore $k$ is even. This proves that the maximum possible value of $k$ is $mn-1$ .

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.