Track / Stage 5 / 20 of 400 #620 of 1964

Problem 620

AIME late

Combinatorics Difficulty 5.0 Prove it Brazilian Mathematical Olympiad · 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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$ :

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.