1
$\begingroup$

There are 12 different sticks in a bag of integral length. You pull out 3 sticks, and you CANNOT put them together to form a triangle. What are the shortest possible lengths of the 12 sticks? What is the shortest length of the longest stick?

THIS IS NOT A HOMEWORK QUESTION. WAS GIVEN AS A PUZZLE TO THINK ABOUT

Im really not sure how to go about this. All I am thinking is if the sticks are all multiples of each other?

$\endgroup$
  • $\begingroup$ The triangle inequality is useful here. $|a|+|b|\geq |a+b|$. In this context, to form a triangle with side lengths $a, b$ and $c$ you require that the sum of the lengths of the two shorter sides must be greater than or equal to the length of the longer side. $\endgroup$ – JMoravitz Feb 27 '17 at 0:15
  • $\begingroup$ I don't really understand the question. Are you saying that no combination of three sticks taken from the $12$ will make a triangle? $\endgroup$ – lulu Feb 27 '17 at 0:17
  • $\begingroup$ Im not really sure why he said 12 sticks, but Im guessing you need to know how many sticks to figure out the shortest length of the longest stick in the bag $\endgroup$ – H.T Feb 27 '17 at 0:19
  • $\begingroup$ Also, thanks for suggesting the triangle inequality! How would I use that to go about finding integral lengths? $\endgroup$ – H.T Feb 27 '17 at 0:19
  • 1
    $\begingroup$ I believe if degenerate triangles are allowed, the shortest possible lengths obey the Fibonacci sequence. This should be due to the fact that when constructing such a set of 12 lengths, the minimum possible "next" length is the sum of the two largest lengths you have so far. So, it would go like "1,1,2,3,5" etc. $\endgroup$ – Michael Wang Feb 27 '17 at 2:26
2
$\begingroup$

The lengths of the sticks can be arranged in the nondecreasing series $(a_1,a_2,...,a_{12})$. The shortest length is $1$, so we can say, that in this bag there are two sticks with length $1$, so $a_1=a_2=1$

Now we can construct next pieces by taking two longest (last) sticks, summing their lengths and adding $1$ to obtain the smallest integer number larger than the sum of two other integers: $$a_{k+2}=a_k+a_{k+1}+1$$ we have then: $$a_{k+2}>a_k+a_{k+1} \geq a_i+a_j \,\,\,(i<j\leq k+1) $$ so if we get $3$ sticks, the longest is longer than the sum of the remaining two, so we can't arrange them to make a triangle.

The series is then $$(1,1,3,5,9,15,25,41,67,109,177,287)$$

We can also say, that the degenerate triangles doesn't count as triangles in this context. In this case we don't have to add $1$ to the lengths of two sticks in forst formula, so we have: $$a_{k+2}=a_k+a_{k+1}$$ and this is the recursive formula for Fibonacci series: $$(1,1,2,3,5,8,13,21,34,55,89,144)$$

$\endgroup$
  • $\begingroup$ in the second case you meant that degenerate triangles do count, right? $\endgroup$ – mau Mar 28 '17 at 20:45
  • $\begingroup$ @mau - no. Degenerate triangles were counted as triangles in first case. $\endgroup$ – Jaroslaw Matlak Mar 29 '17 at 7:05
  • $\begingroup$ A degenerate triangle is (1,1,2), not anyone in the first case $\endgroup$ – mau Mar 29 '17 at 7:38
  • $\begingroup$ @mau - the question is to find numbers, that can not be the lengths of triangle sides. So if we assume, that degenrate triangle is not a triangle, lengths (1,1,2) are ok. $\endgroup$ – Jaroslaw Matlak Mar 29 '17 at 12:13
  • $\begingroup$ silly me... you are perfectly right! $\endgroup$ – mau Mar 29 '17 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.