Pigeonhole Problem

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

Unread post by Asif Hossain » Thu Feb 04, 2021 1:01 pm

10 real numbers are chosen between 1 and 55 prove that there are at least three numbers forming a triangle.
(Combinatorics e hathekhori)

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

Re: Pigeonhole Problem

Unread post by Mehrab4226 » Sat Feb 06, 2021 12:00 am

I couldn't solve this using PHP.
Let us assume the contrary,
Let there are $10$ numbers such that no three of them forms a triangle, in other words, there is no three of them having the property $a+b>c$, thus all have the property $a+b \leq c$
Let the $10$ numbers be $a_1,a_2, \dots a_{10}$ , WLOG $a_1 < a_2 < a_3 < \cdots < a_{10}$

Now $a_1 \geq 1 ,a_2 > 1$

$\therefore a_1+a_2 \leq a_3 >2$

Similarly, we get,

$a_4 > 3$ [Using $a_2+a_3 \leq a_4$]

$a_5 > 5$

$a_6 > 8$

$a_7 > 13$

$a_8 > 21$

$a_9 > 34$

$a_{10} > 55$

Contradiction. $\square$
If $a_i$ are not distinct from each other, then the statement is not true.

1,1,2,3,5,8,13,21,34,55 is an example
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
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Pigeonhole Problem

Unread post by Anindya Biswas » Sat Feb 06, 2021 11:13 pm

Mehrab4226 wrote:
Sat Feb 06, 2021 12:00 am
I couldn't solve this using PHP.
Let us assume the contrary,
Let there are $10$ numbers such that no three of them forms a triangle, in other words, there is no three of them having the property $a+b>c$, thus all have the property $a+b \leq c$
Let the $10$ numbers be $a_1,a_2, \dots a_{10}$ , WLOG $a_1 < a_2 < a_3 < \cdots < a_{10}$

Now $a_1 \geq 1 ,a_2 > 1$

$\therefore a_1+a_2 \leq a_3 >2$

Similarly, we get,

$a_4 > 3$ [Using $a_2+a_3 \leq a_4$]

$a_5 > 5$

$a_6 > 8$

$a_7 > 13$

$a_8 > 21$

$a_9 > 34$

$a_{10} > 55$

Contradiction. $\square$
If $a_i$ are not distinct from each other, then the statement is not true.

1,1,2,3,5,8,13,21,34,55 is an example


Pretty satisfying solution, I don't know if I can apply PHP here, but this was a really nice solution (I never thought fibonacci sequence would come up here in this question)
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Pigeonhole Problem

Unread post by Asif Hossain » Tue Feb 09, 2021 1:20 pm

An analogous problem was posted in aops PHP wiki page maybe manhattan something olympiad which was solved by dividing the interval and applying php. But this problem was in php chapter that's why i thought php might work though i have a stern belief that it can be solved by php same way as in the aops. (Though I am a nooB :/ )
Hmm..Hammer...Treat everything as nail

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Pigeonhole Problem

Unread post by Asif Hossain » Tue Feb 09, 2021 5:50 pm

a mistake numbers are on open interval (1,55). (Still your proof is right)
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 7:02 pm

Asif Hossain wrote:
Tue Feb 09, 2021 5:50 pm
a mistake numbers are on open interval (1,55). (Still your proof is right)
Then the selected numbers are not necessarily distinct! They can have repetition too.
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é

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Pigeonhole Problem

Unread post by Asif Hossain » Tue Feb 09, 2021 8:31 pm

Mehrab4226 wrote:
Sat Feb 06, 2021 12:00 am
I couldn't solve this using PHP.
Let us assume the contrary,
Let there are $10$ numbers such that no three of them forms a triangle, in other words, there is no three of them having the property $a+b>c$, thus all have the property $a+b \leq c$
Let the $10$ numbers be $a_1,a_2, \dots a_{10}$ , WLOG $a_1 < a_2 < a_3 < \cdots < a_{10}$

Now $a_1 \geq 1 ,a_2 > 1$

$\therefore a_1+a_2 \leq a_3 >2$

Similarly, we get,

$a_4 > 3$ [Using $a_2+a_3 \leq a_4$]

$a_5 > 5$

$a_6 > 8$

$a_7 > 13$

$a_8 > 21$

$a_9 > 34$

$a_{10} > 55$

Contradiction. $\square$
If $a_i$ are not distinct from each other, then the statement is not true.

1,1,2,3,5,8,13,21,34,55 is an example


I didn't understand the arguement Let there are $10$ numbers such that no three of them forms a triangle, in other words, there is no three of them having the property $a+b>c$, thus all have the property $a+b \leq c$ does it imply the triangle inequality?(As triangle inequality is a+b>c, b+c>a, c+a>b. does a+b>c imply all of them??)
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 8:36 pm

Asif Hossain wrote:
Tue Feb 09, 2021 8:31 pm
Mehrab4226 wrote:
Sat Feb 06, 2021 12:00 am
I couldn't solve this using PHP.
Let us assume the contrary,
Let there are $10$ numbers such that no three of them forms a triangle, in other words, there is no three of them having the property $a+b>c$, thus all have the property $a+b \leq c$
Let the $10$ numbers be $a_1,a_2, \dots a_{10}$ , WLOG $a_1 < a_2 < a_3 < \cdots < a_{10}$

Now $a_1 \geq 1 ,a_2 > 1$

$\therefore a_1+a_2 \leq a_3 >2$

Similarly, we get,

$a_4 > 3$ [Using $a_2+a_3 \leq a_4$]

$a_5 > 5$

$a_6 > 8$

$a_7 > 13$

$a_8 > 21$

$a_9 > 34$

$a_{10} > 55$

Contradiction. $\square$
If $a_i$ are not distinct from each other, then the statement is not true.

1,1,2,3,5,8,13,21,34,55 is an example


I didn't understand the argument Let there are $10$ numbers such that no three of them forms a triangle, in other words, there is no three of them having the property $a+b>c$, thus all have the property $a+b \leq c$ does it imply the triangle inequality?(As triangle inequality is a+b>c, b+c>a, c+a>b. does a+b>c imply all of them??)

Oh sorry, I should have mentioned that $c$ is the largest of them. Then we only have to worry about $a+b > c$ As the others are true no matter what a,b,c are, where c is the largest.
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é

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Pigeonhole Problem

Unread post by Asif Hossain » Tue Feb 09, 2021 8:56 pm

Mehrab4226 wrote:
Tue Feb 09, 2021 8:36 pm
Asif Hossain wrote:
Tue Feb 09, 2021 8:31 pm
Mehrab4226 wrote:
Sat Feb 06, 2021 12:00 am
I couldn't solve this using PHP.
Let us assume the contrary,
Let there are $10$ numbers such that no three of them forms a triangle, in other words, there is no three of them having the property $a+b>c$, thus all have the property $a+b \leq c$
Let the $10$ numbers be $a_1,a_2, \dots a_{10}$ , WLOG $a_1 < a_2 < a_3 < \cdots < a_{10}$

Now $a_1 \geq 1 ,a_2 > 1$

$\therefore a_1+a_2 \leq a_3 >2$

Similarly, we get,

$a_4 > 3$ [Using $a_2+a_3 \leq a_4$]

$a_5 > 5$

$a_6 > 8$

$a_7 > 13$

$a_8 > 21$

$a_9 > 34$

$a_{10} > 55$

Contradiction. $\square$
If $a_i$ are not distinct from each other, then the statement is not true.

1,1,2,3,5,8,13,21,34,55 is an example


I didn't understand the argument Let there are $10$ numbers such that no three of them forms a triangle, in other words, there is no three of them having the property $a+b>c$, thus all have the property $a+b \leq c$ does it imply the triangle inequality?(As triangle inequality is a+b>c, b+c>a, c+a>b. does a+b>c imply all of them??)

Oh sorry, I should have mentioned that $c$ is the largest of them. Then we only have to worry about $a+b > c$ As the others are true no matter what a,b,c are, where c is the largest.


But would that hold if repitition is allowed??
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 8:56 pm

Asif Hossain wrote:
Tue Feb 09, 2021 8:56 pm
Mehrab4226 wrote:
Tue Feb 09, 2021 8:36 pm
Asif Hossain wrote:
Tue Feb 09, 2021 8:31 pm


I didn't understand the argument Let there are $10$ numbers such that no three of them forms a triangle, in other words, there is no three of them having the property $a+b>c$, thus all have the property $a+b \leq c$ does it imply the triangle inequality?(As triangle inequality is a+b>c, b+c>a, c+a>b. does a+b>c imply all of them??)
Oh sorry, I should have mentioned that $c$ is the largest of them. Then we only have to worry about $a+b > c$ As the others are true no matter what a,b,c are, where c is the largest.
But would that hold if repitition is allowed??
Yes. $a_1 >1,a_2 > 1$ so $a_1+a_2 \leq a_3 > 2$ and so on.
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é

Post Reply