IMC 1999 · Day 1 · P5

We prove the more general statement that if at least $n + k$ points are marked in an $n \times k$ grid, then the required sequence of marked points can be selected.

If a row or a column contains at most one marked point, delete it. This decreases $n + k$ by 1 and the number of the marked points by at most 1, so the condition remains true. Repeat this step until each row and column contains at least two marked points. Note that the condition implies that there are at least two marked points, so the whole set of marked points cannot be deleted.

We define a sequence $b_1, b_2, \dots$ of marked points. Let $b_1$ be an arbitrary marked point. For any positive integer $n$, let $b_{2n}$ be an other marked point in the row of $b_{2n-1}$ and $b_{2n+1}$ be an other marked point in the column of $b_{2n}$.

Let $m$ be the first index for which $b_m$ is the same as one of the earlier points, say $b_m = b_l$, $l < m$.

If $m - l$ is even, the line segments $b_l b_{l+1}$, $b_{l+1} b_{l+2}$, …, $b_{m-1} b_l = b_{m-1} b_m$ are alternating horizontal and vertical. So one can choose $2k = m - l$, and $(a_1, \dots, a_{2k}) = (b_l, \dots, b_{m-1})$ or $(a_1, \dots, a_{2k}) = (b_{l+1}, \dots, b_m)$ if $l$ is odd or even, respectively.

If $m - l$ is odd, then the points $b_l = b_m$, $b_{l+1}$ and $b_{m-1}$ are in the same row/column. In this case chose $2k = m - l - 1$. Again, the line segments $b_{l+1} b_{l+2}$, $b_{l+2} b_{l+3}$, …, $b_{m-1} b_{l+1}$ are alternating horizontal and vertical and one can choose $(a_1, \dots, a_{2k}) = (b_{l+1}, \dots, b_{m-1})$ or $(a_1, \dots, a_{2k}) = (b_{l+2}, \dots, b_{m-1}, b_{l+1})$ if $l$ is even or odd, respectively.

Define the graph $G$ in the following way: Let the vertices of $G$ be the rows and the columns of the grid. Connect a row $r$ and a column $c$ with an edge if the intersection point of $r$ and $c$ is marked.

The graph $G$ has $2n$ vertices and $2n$ edges. As is well known, if a graph of $N$ vertices contains no circle, it can have at most $N - 1$ edges. Thus $G$ does contain a circle. A circle is an alternating sequence of rows and columns, and the intersection of each neighbouring row and column is a marked point. The required sequence consists of these intersection points.