1. ## 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...

2. ## Re: Combinatorics

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

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

3. ## Re: Combinatorics

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

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 $2\cdot 100$choices.

Now, let $X$ be distinct entries in it.

$X=\sum I_i$ where I_i is indicator variable of $i$ appearing in our chosen row or column.

It's clear that $E[I_i]=P[I\geq 1]$.

No we will find a lower bound for $P[I\geq 1]$.

Imagine the worst case scenario: all $100$ appearances of $i$ are in $10\times 10$matrix in the big $100\times 100$ matrix.

We get:

$P[I_i]\geq \frac{2\sqrt{100}}{2\cdot 100}=\frac{1}{10}$.

Or, by linearity: $E[X]\geq 10$.