Pigeonhole Problem

For students of class 11-12 (age 16+)
Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm
Re: Pigeonhole Problem

Unread post by Asif Hossain » Tue Feb 09, 2021 9:16 pm

My brain is still dizzing but Let me show my approach (See if you can fix my problem in my proof :/)
(1,55)= (1,2) U [2,4) U [4,8) U [8,55)
IF ANY OF THE THREE NUMBERS FALL IN (1,2) OR [2,4) OR [4,8) THEN WE ARE DONE.
BUT IF AT LEAST 4 NUMBERS FALL IN [8,55)....(Shut Down)
Hmm..Hammer...Treat everything as nail

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Pigeonhole Problem

Unread post by Mehrab4226 » Tue Feb 09, 2021 9:22 pm

I will only say 5 numbers must be in [8,55). As my solution says $a_6 >8$ and you can give the exact argument and show (1,8) can have at most 5 points. So the rest are in [8,55).
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
gwimmy(abid)
Posts:9
Joined:Tue Apr 06, 2021 11:23 am

Re: Pigeonhole Problem

Unread post by gwimmy(abid) » Tue Apr 06, 2021 12:02 pm

This is my solution:
$[1,55) = [1,1] U (1,2) U [2,3) U [3,5) U [5, 8) U [8,13) U [13,21) U [21,34) U [34,55)$

Now if we limit ourselves to picking one element from set at most, then we can have $n$ numbers such that no number satisfies $a+b>c$. But we have to pick $10$ numbers from $9$ sets and by PHP, $2$ numbers would come from a single set. So, we will end up with $3$ numbers $a,b,c$ satisfying the inequality.

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Pigeonhole Problem

Unread post by Mehrab4226 » Wed Apr 07, 2021 12:28 am

gwimmy(abid) wrote:
Tue Apr 06, 2021 12:02 pm
This is my solution:
$[1,55) = [1,1] U (1,2) U [2,3) U [3,5) U [5, 8) U [8,13) U [13,21) U [21,34) U [34,55)$

Now if we limit ourselves to picking one element from set at most, then we can have $n$ numbers such that no number satisfies $a+b>c$. But we have to pick $10$ numbers from $9$ sets and by PHP, $2$ numbers would come from a single set. So, we will end up with $3$ numbers $a,b,c$ satisfying the inequality.
Quite Elegantly Done
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Marzuq
Posts:9
Joined:Mon Apr 05, 2021 4:30 pm

Re: Pigeonhole Problem

Unread post by Marzuq » Sat Apr 17, 2021 8:13 am

My solution:
Before going to the main point , we will first find the maximum amount of number we can choose from 1 to 55 such that triangle inequality doesnt fully work on any one of them

Some points
1) for the maximality of the amount , we will choose the number and make it as smallest as possible
2) as triangle dont fully work on any 3 of them. So $a+b \le c$ if $a,b,c$ are those 3 numbers. But to make the numbers smallest as possible . So let $c = a+b$
3)starting from the number --> 1. (Making the numbers smallest as possible)

Case 1: If there is repition in choosing numbers
Then the first number is $1$. Second number is also $1$ The third number $= 1+1=2$. Fourth number $2+1 = 3$
This numbers continues like $1,1,2,3,5,8,13,21,34,55$
There are total $\boxed{10}$ of them

Case 2:if there is no repition in choosing numbers
With the same logic from the above , just there will be just one $1$ instead of two. So here is $\boxed{9}$ of them.

Now it has been said to choose 10 numbers from 1 to 55. From Case 1 , if repition is allowed , we can choose maximum 10 of them and from case 2, maximum 9 can be choosen.

Applying Pigeonhole Principle in case 2, we can prove that its impossible to choose 10 distinct intezer from 1 to 55 such that no triangle can form. But in Case 1, there is only 1 and unique way to choose 10 numbers (not distinct ) from 1 to 55 such that no triangle form.

Half-Credit : Mehrab4226 :mrgreen:

Post Reply