Problem

Source: iran2004

Tags: pigeonhole principle, induction, geometry, rectangle, probability, expected value, combinatorics proposed



assume that we have a n*n table we fill it with 1,...,n such that each number exists exactly n times prove that there exist a row or column such that at least $\sqrt{n}$ diffrent number are contained.