Exercise 1099Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Pigeonhole in a Latin square

#pigeonhole#Latin square#entries

Statement

In an $n\times n$ array filled with entries from $\{1,\ldots,n\}$ , show that if each row has all $n$ distinct values, then each column also has distinct values.

Hint

Each row is a permutation of $\{1,\ldots,n\}$ . Count occurrences of each value.

Show solutionHide solution

Solution

Row constraint. Each row contains each value exactly once. So value $k$ appears $n$ times in the whole array.

Column constraint. Value $k$ appears at most once per column (if it appeared twice in a column, that column would have a repeat). With $n$ total occurrences and $n$ columns, $k$ must appear exactly once per column.

Conclusion. Each column contains each value exactly once (Latin square property).

Pigeonhole in a Latin square

Statement

Solution

More problems in Pigeonhole principle