# Math Help - pigeon hole principle

1. ## 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

2. 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."

3. sorry for misleading, seems like you are able to read my mind on
Originally Posted by emakarov
"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?

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

5. Originally Posted by emakarov

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!