Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /172 of 359

Taiwan IMO Selection Camp, 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×di≥110c_i \times d_i \ge 110, hence ci+di≥11+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,604 problems in a working order, from Junior Challenge 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.