Exercise 1107Combinatorics › Pigeonhole principleL1Added 3 Nov 2026

Pigeonhole in a table

#pigeonhole#table#rows

Statement

Fill an $n\times n$ table with entries from $\{1,\ldots,n\}$ such that each row has all $n$ values. Show that each column has all $n$ values.

Hint

Each value appears exactly $n$ times total; each column contains at most one of each value.

Show solutionHide solution

Solution

Per value. Value $k$ appears exactly once in each row, so exactly $n$ times total.

Per column. Each column contains at most one $k$ (if two, the column has $k$ twice, contradiction with... actually not yet established). Hmm.

Corrected. The problem requires that entries in each column are distinct too — that's a Latin square. The statement "each row has all values" doesn't force each column to have all values (e.g., all rows identical).

Conclusion. The problem is false as stated. In a Latin square, both row and column properties hold by definition.

Pigeonhole in a table

Statement

Solution

More problems in Pigeonhole principle