Maths Olympiad Prep

Library / /187 of 397

, 2021

Combinatorics Difficulty 5.8 AIME, harder Prove it Taiwan

There are 110 guinea pigs for each of the 110 species, arranging as a 110 × 110 array. Find the maximum integer nn 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 nn different species.

Solution

Let cic_i and rir_i be respectively the number of columns and rows containing the ii-th species. Since the intersections of these columns and rows must contain all 110 guinea pigs of species ii, we have ci×di110c_i \times d_i \ge 110, hence ci+di11+10=21c_i + d_i \ge 11 + 10 = 21. This implies i(ci+di)110×21=2310\sum_i (c_i + d_i) \ge 110 \times 21 = 2310. Also, there are 220 rows and columns in total, so by the pigeonhole principle, at least one of them contains [2310220]+1=11\left[\frac{2310}{220}\right]+1=11 different species. Finally, consider the construction where the position (x,y)(x, y) is a guinea pig of species (11[x11]+[y11]+1)(11\left[\frac{x}{11}\right] + \left[\frac{y}{11}\right] + 1), and then we know that n=11n=11 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.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.