10 real numbers are chosen between 1 and 55 prove that there are at least three numbers forming a triangle.
(Combinatorics e hathekhori)
Re: Pigeonhole Problem
Posted: Sat Feb 06, 2021 12:00 am
by Mehrab4226
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.
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)
Re: Pigeonhole Problem
Posted: Tue Feb 09, 2021 1:20 pm
by Asif Hossain
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 :/ )
Re: Pigeonhole Problem
Posted: Tue Feb 09, 2021 5:50 pm
by Asif Hossain
a mistake numbers are on open interval (1,55). (Still your proof is right)
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??)
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.
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.
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.