Results 1 to 3 of 3

Math Help - Pigeonhole Problem

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    3

    Pigeonhole Problem

    Let n be a positive integer and let a1, a2,...,a(n+1) be an real numbers in the interval [0,1). Show that there exists two integers i,j with 1< i, j < (n+1) and i doesn't equal j such that |ai - aj| < (1/n).

    Ok. I can come up with an example...ai = .25 and aj = .3 and n = 5, but I'm sure that it's asking for a more general answer...

    Anyone have any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Black's Avatar
    Joined
    Nov 2009
    Posts
    105
    Express the interval [0,1) as the union of n subintervals.

    [0,1)=[0,1/n) \cup [1/n,2/n) \cup \dots \cup [(n-1)/n, 1).

    Since there are n+1 of the a_i's, at least two of them must be in one of the n intervals; i.e,

    \exists i,j s.t i\not= j and a_i,a_j \in [k/n, (k+1)/n), for 0\le k \le n-1.

    Therefore |a_i-a_j| < 1/n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    33
    Quote Originally Posted by Black View Post
    Express the interval [0,1) as the union of n subintervals.

    [0,1)=[0,1/n) \cup [1/n,2/n) \cup \dots \cup [(n-1)/n, 1).

    Since there are n+1 of the a_i's, at least two of them must be in one of the n intervals; i.e,

    \exists i,j s.t i\not= j and a_i,a_j \in [k/n, (k+1)/n), for 0\le k \le n-1.

    Therefore |a_i-a_j| < 1/n.
    hey, can you explain that in little easier language if there is any!!!
    thanksss
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeonhole principle problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 20th 2011, 04:46 PM
  2. a pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 11th 2010, 02:33 AM
  3. pigeonhole problem ... ASAP please
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 30th 2008, 12:03 AM
  4. Pigeonhole problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: October 18th 2008, 03:41 PM
  5. A pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 12th 2007, 11:22 AM

Search Tags


/mathhelpforum @mathhelpforum