There are n sticks which have distinct integer length. Suppose that it's possible to form a non-degenerate triangle from any 3 distinct sticks among them. It's also known that there are sticks of lengths 5 and 12 among them. What is the largest possible value of n under such conditions?
The main tool we need to solve this problem is the Triangle Inequality: For any triangle the sum of any two sides is larger than the third side.
A computer program is massive overkill.
So let's look possible triangles with 5 and 12 and an unknown side we'll call x. By the Triangle Inequality we have 5+x>12 and 5+12>x. Then 17>x>7, which makes integer x an element of {8,9,10,11,12,13,14,15,16}.
Then the set of stick lengths is a subset of {5,8,9,10,11,12,13,14,15,16}.
Next we'll consider the case that all three sides of a triangle are greater than 5. The most extreme example is when the two shorter sides are 8 and 9 and the long side is 16. Applying the Triangle Inequality we need 8+9>16, which is true so no conflicts in this case.
Finally we'll consider the case where one side of the triangle is 5 and the other two are larger. Call the other two sides x and y and without loss of generality let y>x. Then applying the Triangle Inequality we need x+5>y.
Then x+5>y>x. This means that y can only take at most four possible values, {x+1,x+2,x+3,x+4}, for any given x. Then this means the largest size of some set of n sticks is 6. Calculated from one occurrence of "5" plus one chosen value of x plus four potential values of y.
As a final step we need to show the maximum size of 6 is attainable while having 5 and 12 in the set. One way to achieve this is the set {5,8,9,10,11,12}.
Solution
