There are $110$ guinea pigs for each of the $110$ species, arranging as a $110\times 110$ array. Find the maximum integer $n$ 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 $n$ different species.
Problem
Source: 2021 Taiwan TST Round 1 Mock Day 1 P1
Tags: combinatorics, Taiwan
22.07.2021 18:11
22.07.2021 18:29
07.02.2022 13:00
The answer is 11. So we have to show there exist atleast a coloumn or row with atleast 11species of guinea pigs. Number the species 1 to 110. Let $R_i$ and $C_i$ be the number of species in $i$th coloumn and row respectively. Again $x_i$ be the sum of the number of columns and rows occupied by $i$th species. So the following equality holds, $$\sum_{i=1}^{110} x_i=\sum_{i=1}^{110} C_i+R_i$$ For any $j$th species $x_j \geq 21$. So, $$\sum_{i=1}^{110} C_i+R_i \geq 21\times110$$PHP gives us power to deduce their exist a row or coloumn with at least 11species. As example, we give a pattern for 6$\times$6. Try the same pattern for 110$\times $110 also. 111222333 111222333 444555666 444555666