# Combinatorics

• Jun 13th 2011, 12:52 PM
benus
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(Shake)...

• Jun 13th 2011, 12:59 PM
Also sprach Zarathustra
Re: Combinatorics
Quote:

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(Shake)...

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...
• Jun 13th 2011, 05:18 PM
Also sprach Zarathustra
Re: Combinatorics
Quote:

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(Shake)...

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