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

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

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

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

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

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

We get:

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


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