IMC 1999, Day 1, Problem 5
Suppose that points of an grid are marked. Show that for some one can select distinct marked points, say , such that and are in the same row, and are in the same column, , and are in the same row, and and are in the same column.
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Solution 1. We prove the more general statement that if at least points are marked in an 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 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 of marked points. Let be an arbitrary marked point. For any positive integer , let be an other marked point in the row of and be an other marked point in the column of .
Let be the first index for which is the same as one of the earlier points, say , .
If is even, the line segments , , ..., are alternating horizontal and vertical. So one can choose , and or if is odd or even, respectively.
If is odd, then the points , and are in the same row/column. In this case chose . Again, the line segments , , ..., are alternating horizontal and vertical and one can choose or if is even or odd, respectively.
Solution 2. Define the graph in the following way: Let the vertices of be the rows and the columns of the grid. Connect a row and a column with an edge if the intersection point of and is marked.
The graph has vertices and edges. As is well known, if a graph of vertices contains no circle, it can have at most edges. Thus 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.
Transcribed from the official solutions, page 3. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.