Let A be a 100*100 matix such that every number of the set {1,2,.... ,100} appears exactly 100 times. prove that there exists a row or column in which there is at least 10 different numbers.
I am trying to apply the pigeonhole principle, but cant identify how to do it properly...
Please help
Here a solution that I get with a help of two friends.
First let us choose a random row or column, for that we have choices.
Now, let be distinct entries in it.
where I_i is indicator variable of appearing in our chosen row or column.
It's clear that .
No we will find a lower bound for .
Imagine the worst case scenario: all appearances of are in matrix in the big matrix.
We get:
.
Or, by linearity: .