Results 1 to 5 of 5

Math Help - pigeon hole principle

  1. #1
    Newbie
    Joined
    Apr 2011
    Posts
    3

    pigeon hole principle

    hi all, i've got a question as well as the solution but can anyone kindly explain the solution or kindly set up an example for me? thank you all very much in advance.

    Question:
    Let there be 5 distinct real numbers a1-a5. Prove there are indices i,j with 0<ai-aj<1+aiaj

    Solution:
    As the function tan-pi/2,+pi/2) ->R is surjective, there are angles θi belongs to (-pi/2,+pi/2) with ai = tan θ, 1<=i<=5.
    Divide the interval (-pi/2,+pi/2) into 4 equal pieces, each of length pi/4. As we have 5 angles, at least 2 of them must lie in the same small interval, implying that there are i,j with 0<θi-θj<pi/4. Applying tan to the last inequality and using the identity
    tan(x-y)=(tan x - tan y) / 1 + tan x tan y
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    What exactly sentence or part of the sentence do you not understand? For example: "I don't understand what is meant by saying that tan(x) is surjective on (-pi/2, pi/2)" or "I don't understand how the fact that there are 5 angles implies that there are i,j with 0<θi-θj<pi/4."
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2011
    Posts
    3
    sorry for misleading, seems like you are able to read my mind on
    Quote Originally Posted by emakarov View Post
    "I don't understand how the fact that there are 5 angles implies that there are i,j with 0<θi-θj<pi/4."
    and how do i actually apply tan(x-y)=(tan x - tan y) / 1 + tan x tan y to the last inequality?

    thank you for your reply.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780


    I don't understand how the fact that there are 5 angles implies that there are i,j with 0<θi-θj<pi/4.
    The interval (-π/2, π/2) can be split into four disjoint intervals: (-π/2, -π/4], (-π/4, 0], (0, π/4] and (π/4, π/2). If there are five points: θ1 = tan(a1), ..., θ5 = tan(a5) lying in these four intervals, then there is an interval with at least two points, say, θi and θj. This is the essence of pigeonhole principle. This means that |θi - θj| < π/4.

    and how do i actually apply tan(x-y)=(tan x - tan y) / 1 + tan x tan y to the last inequality?
    Tangent is a monotonic function, so θi - θj < π/4 implies that tan(θi - θj) < tan(π/4) = 1. According to the hint, the left-hand side is equal to (tan(θi) - tan(θj)) / (1 + tan(θi)tan(θj)), i.e., (ai - aj) / (1 + ai * aj) < 1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2011
    Posts
    3
    Quote Originally Posted by emakarov View Post


    The interval (-π/2, π/2) can be split into four disjoint intervals: (-π/2, -π/4], (-π/4, 0], (0, π/4] and (π/4, π/2). If there are five points: θ1 = tan(a1), ..., θ5 = tan(a5) lying in these four intervals, then there is an interval with at least two points, say, θi and θj. This is the essence of pigeonhole principle. This means that |θi - θj| < π/4.

    Tangent is a monotonic function, so θi - θj < π/4 implies that tan(θi - θj) < tan(π/4) = 1. According to the hint, the left-hand side is equal to (tan(θi) - tan(θj)) / (1 + tan(θi)tan(θj)), i.e., (ai - aj) / (1 + ai * aj) < 1.
    gosh i can't believe i can understand this, thanks to your explanation!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Pigeon-hole Principle (2)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 3rd 2011, 01:40 PM
  2. [SOLVED] Pigeon-Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 30th 2011, 02:48 AM
  3. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 02:56 AM
  4. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 03:39 AM
  5. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 8th 2007, 05:37 PM

/mathhelpforum @mathhelpforum