IMC 1999, Ημέρα 1, Θέμα 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.
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
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.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.