There are 110 guinea pigs for each of the 110 species, arranging as a 110 × 110 array. Find the maximum integer such that, no matter how the guinea pigs align, we can always find a column or a row of 110 guinea pigs containing at least different species.
, 2021
Solution
Let and be respectively the number of columns and rows containing the -th species. Since the intersections of these columns and rows must contain all 110 guinea pigs of species , we have , hence . This implies . Also, there are 220 rows and columns in total, so by the pigeonhole principle, at least one of them contains different species. Finally, consider the construction where the position is a guinea pig of species , and then we know that is indeed the answer sought.
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.