Let's first consider the case that $n$ is a perfect square. We say $n=m^2$ It is clear that an "optimal" situation (in fact it is a "worst case" situation) would be that each number appeared in an $m \times m$ table. In that case the requirement is fulfilled, and it is sharp. If we raise n by 1, then in at most 1 column we can create m+1 times the same element (without decreasing the amound in another of course). So to raise the amount of times the same number appears, by 1, in each of the n columns and each of the n rows, we need at least 2n extra blocks. So the statement is ok up to $m^2+2m=(m+1)^2-1$. One more and we're back to the case $n$ is a perfect square. (a thing used here throughout the problem for the necessary verifications is scrapping all rows & columns where the number "k" doesn't appear, plus pigeonhole) Peter

sorry, can you give a real proof for a $n=m^2$? hmm...sounds like trivial expected value-problem but i'm too stupid to give a proof at the moment. Peter

I don't even think I understand the induction step Anyway, I wonder if the case $n=m^2$ is significantly easier than the general case.

Well, it is easy (trivial even). Look: We got an $m^2\times m^2$ square, in which each number appears $m^2$ times. The key is: if a number appears more than $m$ times in a row or column, then there are at least 2 rows/columns where the number appears less than $m$ times. (this is trivial) If you still want to have only $m$ different numbers on those rows, you'll need 2 more numbers having m+1 numbers on that row column, which leaves you 4 such cases again, which will loophole to infinity. (in fact, this part is pretty trivial too if you make some drawings) So if you know that the requirement is sharpened to $m$ numbers in each row and $m$ numbers in each columns, with $m^2$ in total, then there can be no row or column other than those $m$ containing that specific number. Which is just another wording for saying (cf. the last senctence I wrote): If you scratch all rows & columns from the array not containing that specific number, then you'll keep an $m\times m$ square. It doesn't necessarily imply that they really form a square like that, counterexample is below, but I didn't use the 'actual' square as given in proof either. $\begin{array}{cccc}1&2&1&2\\3&2&3&2\\1&4&1&4\\3&4&3&4\end{array}$

Another possible approach is: Let a "hit" be recorded for each time a different integer is present in a different row or column. Suppose i occurs in k rows and l comumns. Then the number of hits recorded by i is $k+l \geq 2 \sqrt kl \geq 2 \sqrt n$, so the total number of hits is at least $2n \sqrt n$. Hence some row or column (of which there are 2n), records at least $\sqrt n$ hits i.e. at least $\sqrt n$ elements are present.

Very nice, Fiachra, I just wonder how do you know that $\sqrt kl \geq 2 \sqrt n$? If that's true and it has a nice, rigorous solution, you got a very good and very short proof.

Why is $kl\ge n$? What if $i$ occurs in only one row, for example? [Edit: I see Peter has already asked the question ]

consider just the occurences of i in the table and rearrange them in decreasing order;then you get a partition of n(since i occurs exactly n times-just think of the symbol i as an asterisk in a Young Diagram for a partition).then clearly k would be largest part in the partition and l becomes the number of parts in the partition.then clearly since the number of i's is just n,it is clearly less than or equal to kl.

Thanks! I get it now. My objection was pretty stupid . I asked what happens if $i$ occurs in just one row, but then it also occurs in $n$ columns, and I had forgotten about that. Thanks again!

Sorry, I should probably have included this bit: Imagine the rectangle formed by the k rows and l columns (rearranging the rows and columns if necessary). All the occurences of i lie within this rectangle, which contains kl cells. Hence i occurs at most kl times i.e. $kl \geq n$.

yes, that was indeed the main element in my proof too (but less efficient) nice solution