Results 1 to 3 of 3

Math Help - Combinatorics

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    2

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Combinatorics

    Quote Originally Posted by benus View Post
    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...
    Last edited by Also sprach Zarathustra; June 13th 2011 at 02:18 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Combinatorics

    Quote Originally Posted by benus View Post
    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 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 05:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 10:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum