Seven line segments, with lengths no greater than 10 inches, and no shorter than 1 inch, are given.

Seven line segments, with lengths no greater than 10 inches, and no shorter than 1 inch, are given. Show that one can choose three of them to represent the sides of a triangle.

• 3, 4, 5 is a triangle. QED – user117644 Feb 24 '15 at 17:35
• Can anyone please explain to me using pigeonhole principle – Aditya Kumar Feb 24 '15 at 17:37
• Your question doesn't require that principle. Here's an example of where it's needed: math.stackexchange.com/questions/198810/… – user117644 Feb 24 '15 at 17:39
• @MJD That edit changes the intention of the OP. This question, although it may not need it, can also be proved using pigeonhole principle. The OP was originally asking for a proof using the pigeonhole principle. – user218939 Feb 24 '15 at 17:45
• @mistermarko how is "3,4,5 is a triangle" a proof at all? – Cruncher Feb 24 '15 at 18:15

Let the lengths of seven of the line segments be $l_1, l_2, l_3, \dotsc, l_7$ in (weakly) ascending order. Now suppose that no triangle can be formed from these lengths. Furthermore, let $l_2 ≥l_1 ≥1$ (the minimum length,suggested by meelo).

Then $l_3 > 2$, $l_4 > 3$, $l_5 > 5$, $l_6 > 8$, $l_7 > 13$ (because if $l_i + l_{i+1} \geq l_{i+2}$, then we can form a triangle). But we know that $l_i \leq 10$, so thus a triangle has to be formed.

• It would be better to phrase this as letting $l_2\geq l_1\geq 1$ - it stills follows that $l_3> l_2+l_1 \geq 2$ and so on, and you don't need to make any unwarranted assumption about $l_1$ and $l_2$ being equal to anything. – Milo Brandt Feb 24 '15 at 23:31
• @Meelo yes you are right ,edited . thanks for your feedback :) – avz2611 Feb 25 '15 at 4:13

Hint: Suppose $a < b < c$ are three lengths that do not form a triangle. Then $c > a+b > 2a$.

• Should that be $\leq$ and $\geq$? – BlueRaja - Danny Pflughoeft Feb 24 '15 at 20:51
• @BlueRaja-DannyPflughoeft no for a triangle its a strict inequality, as for the second one yes it should be ≥ – avz2611 Feb 25 '15 at 4:11

Hint given by @MJD was really helpful

If you number the line segments from 1 to 7, and suppose no three of them can be used to make a triangle.

Start from seg. 1 and seg.2 . As you cannot use seg. 3 to make a triangle from seg.1 and seg. 2 so length of seg. 3 must be strictly more than 2 inches.

Continue same way you shall get (strict) lower bounds on lengths for

seg. 1 ------ 1 inch

seg 2 --------1 inch

seg 3---------2 inch

seg 4---------3 inch

seg 5---------5 inch

seg 6---------8 inch

Seventh segment cannot be greater than 10 inches, then it can be used to make a triangle with two of the previous 6 segments. (seg. 5 and seg. 6 for example)

Now question how to use Pigeonhole principle in here...? I am sorry I did not answer your question completely

Minimum sequence (degenerate triangles):

1, 1, 2, 3, 5, 8, 13

If any number were reduced a triangle would form. Therefore to make no triangles with 7, the upper bound must be 13.

I don't see how the pigeonhole principle even applies.

• How is this different from avz2611's answer? – wchargin Feb 24 '15 at 22:30
• Dunno. I couldn't read his. – Joshua Feb 25 '15 at 1:10
• I like the subtle plug for Fibonacci--I hadn't thought of the connection until I saw this list. – MichaelChirico Feb 25 '15 at 3:58