4

Part of 2009 Switzerland - Final Round

Problems(1)

1 of n symbols in n x n square

Source: Switzerland - 2009 Swiss MO Final Round p4

n

be a natural number. Each cell of a

n \times n

square contains one of

n

different symbols, such that each of the symbols is in exactly

n

cells. Show that a row or a column exists that contains at least \sqrt{n} different symbols.