Matrix filling

Task number: 3922

In the \( 10 \times 10 \) matrix, the numbers \( \{1{,}2, \ldots, 10 \} \) are written so that each number has ten occurrences. Show that then in some column or row we find at least four different numbers.

Show in general, that if in an \( n \times n \) matrix each number occurs exactly \( n \)-times, then a row or column has at least \( \sqrt{n} \) different numbers. If is \( \sqrt{n} \) an integer, the estimate is tight.

  • Solution

    Let’s mark the rows indexes by \( 1,…, 10 \) and the column ones by \( 11,…, 20 \).

    For a contrary, suppose that each number (symbol) has at most three occurrences in each row or column.

    In two ways, we estimate the number of pairs \( (i, s) \), where \( i \) is the index of the row or column and \( s \) is the symbol that appears in the relevant row or columns.

    \( \# (i, s) \le 20 {\cdot} 3 \), because in each of the twenty rows or columns we find at most three different symbols.

    By analyzing the cases, we notice that the number of pairs of \( (i, s) \) with a fixed \( s \) is at least 7: Without loss of generality, we can assume that \( s \) occurs in more columns than rows. If all 10 \( s \) symbols are in one line, we have 11 \( (i, s) \) pairs; if they are in two rows, there are at least 7 of those pairs; and the same if they are in three lines.

    Hence \( \# (i, s) \ge 10 {\cdot} 7 \), which is already leading to a contradiction.

    Note that, in general, it must be proved that the number of pairs with fixed \( s \) is at least \( 2 \sqrt{n} \).

Difficulty level: Moderate task
Proving or derivation task
Solution require uncommon idea
Cs translation
Send comment on task by email