21Why assume what is not said [7]
Of course he meant reals and such a proof is easy to construct by PHP. take [2,4],(4,8],(8,12]. One box must contain 3 numbers and they form sides of a triangle...
If any 7 numbers( not necessarily distinct ) are chosen from 2 to 12, prove that among those 7 numbers we can get three which form the sides of a triangle.
-
UP 0 DOWN 0 0 8
8 Answers
11Consider a permutation P_\propto (\lambda) of the set \lambda = \left(\alpha_1, \alpha_2....\alpha_7 \mid 2\le \alpha_i \le 12 : 1\le i\le 7 \right)
P_\propto (\lambda)=(a_1,a_2,a_3...a_7 \mid a_i\le a_{i+1})
Now think of the triplets - \left\{\begin{matrix} (a_1,a_2,a_3) & (a_2,a_3,a_4) & (a_3,a_4,a_5) & (a_4,a_5,a_6) & (a_5,a_6,a_7) \end{matrix}\}\right.
Needless to mention that (in the ith triplet) ai+1+ai+2>ai & ai+ai+2>ai+1....The only thing to prove remains that there exists an i such that ai+ai+1>ai+2.....
The proof is obviously by contradiction -
By assuming the opposite, we have \sum_{i=1}^{5}\left({a_i+a_{i+1}}<a_{i+2} \right)
Simplyfying gives \sum_{i=1}^{5}{a_i}<a_1+2a_2+\sum_{i=3}^{5}{a_i}<a_7
Which is only possible if a7=12 and a1=a2=2....(Assuming no 3 are equal)....which implies \sum_{i=3}^{5}{a_i}<8 - An obvious contradiction....
Edit : Assuming all the nos. are integers....(Which is not specified....h4hemang is requested to confirm it)
2111Interesting the way a wrong turn in a soln can render it useless....[56]
The simplification step (Last but two lines) finishes the case for reals.....
a1+2a2+a3+a4+a5<a7 is the one.....LHS>12, but RHS<12....So equality case is the only way out implying ai=2 for all i.....but that case is already ruled out....
Indeed such a proof was easy to construct without applying PHP...[67]
21perhaps because its very weak...
one can easily extend (2,12) to (2,16)
i don't know the largest k , so that its valid for (2,k) though...
seems interesting
the result is valid for (1,8), and one can extend it to (1,13) ,again i dnt know the upper bound
11Lol...maybe because this was something simpler...
However can you think of shrinking the Upper bound - in other words bring that down from 12? That would do it anyhow, and precisely i think any number > 5 (or maybe lower) will work
21Oh well...
fix any positive real n. if you choose k element from the set [n,t), so that at least 3 among the chosen elements form sides of a triangle then maximum value of t is given by n(Fk) where Fk is the k-th fibonacci number. For t > n(Fk) there will be k numbers ,so that no three of them forms sides of a triangle... for example n,n,2n,3n,5n,...n(Fk).so its the strongest bound.
@Devil: why do you want to shrink the upper bound? of course the result is valid for all n<t≤n(Fn)...didn't get what you meant.
If you mean the minimum no of numbers to be chosen form (2,12) for ensuring existence of triangle ,then it would be 6. (so no need to choose 7 numbers). actually choosing 6 numbers from (2,16) is the strongest case...
21so h4hemang can make is question strongest by restating it:
If any 7 numbers( not necessarily distinct ) are chosen from 2 to 26, prove that among those 7 numbers we can get three which form the sides of a triangle.
11Well actually I was shrinking the upper bound for mere experimentation....just wondering for the more extreme case as you just posted :P
