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.

  • $\begingroup$ 3, 4, 5 is a triangle. QED $\endgroup$ – user117644 Feb 24 '15 at 17:35
  • 1
    $\begingroup$ Can anyone please explain to me using pigeonhole principle $\endgroup$ – Aditya Kumar Feb 24 '15 at 17:37
  • $\begingroup$ Your question doesn't require that principle. Here's an example of where it's needed: math.stackexchange.com/questions/198810/… $\endgroup$ – user117644 Feb 24 '15 at 17:39
  • $\begingroup$ @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. $\endgroup$ – user218939 Feb 24 '15 at 17:45
  • 6
    $\begingroup$ @mistermarko how is "3,4,5 is a triangle" a proof at all? $\endgroup$ – 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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Milo Brandt Feb 24 '15 at 23:31
  • $\begingroup$ @Meelo yes you are right ,edited . thanks for your feedback :) $\endgroup$ – 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$.

  • 1
    $\begingroup$ Should that be $\leq$ and $\geq$? $\endgroup$ – BlueRaja - Danny Pflughoeft Feb 24 '15 at 20:51
  • $\begingroup$ @BlueRaja-DannyPflughoeft no for a triangle its a strict inequality, as for the second one yes it should be ≥ $\endgroup$ – 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.

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

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.