Competition problem — Combinatorics

Combinatorics Difficulty 5.0 AIME, harder Prove it Brazil

Consider all the ways of writing exactly ten times each one of the numbers $0, 1, 2, 3, \ldots, 9$ in the squares of a $10 \times 10$ board.
Find the greatest integer $n$ with the property that there is always a row or a column with $n$ different numbers.

Solution

Let's count in two ways the number of ordered pairs $(d, l)$ , where $d$ is a digit and $l$ is a row or column containing $d$ . For simplicity, let a *line* be a row or a column. Since there are $10$ occurrences of $d$ , they are present in at least $7$ lines (the intersections of the rows and columns must cover all ten numbers). So the number of pairs are at least $7 \cdot 10 = 70$ . Since there are $10 + 10 = 20$ lines, one line must contain at least $\lfloor \frac{70-1}{20} \rfloor + 1 = 4$ different numbers. The

following example shows that the answer is indeed $4$ :

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 and solution reproduced as published; topic and difficulty added by this site.