A table is given.
a) If any 9 fields of the table are labeled, prove that it is possible to select three rows and three columns that contain all of the labeled fields.
b) Label 10 fields of the table so that for any three rows and three columns that we select there is at least one labeled field that is contained neither in the selected rows nor the columns.
(Moscow olympiad 1961, modified)
Solution
a) We consider three different cases (note that these are the only possibilities):
1. There are three rows that contain at least two labeled fields. In this case we select these three rows and we are left with at most 3 labeled fields, so we can select three columns that contain the remaining labeled fields.
2. There is one row that contains at least 3 and another row that contains at least two labeled fields. In this case we select these two rows and we are left with at most 4 labeled fields, so we select a row that contains one of the remaining labeled fields and three columns that contain the other labeled fields.
---
3. There is a row that contains at least 4 labeled fields.
In this case we select that row and we are left with at most 5 labeled fields, so similarly we can select two rows and three columns that contain the remaining labeled fields.
b) One such labeling is given in the following figure:
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.