Thread: Combinatorics

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

Originally Posted by benus

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

New Hint: Suppose that you have all columns least 9 different numbers and get the contradiction(that there is a number that repeats 101 times)

Edit: I think now is better...

Perhaps would be batter if we look at the {1,2,...,100} mod 10...

Originally Posted by benus

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: .