2001 AIME II Problem 5

Question

A set of positive numbers has the triangle property if it has three distinct elements that are the lengths of the sides of a triangle whose area is positive. Consider sets

\{4, 5, 6, \ldots, n\}

of consecutive positive integers, all of whose ten-element subsets have the triangle property. What is the largest possible value of

n?

Answer

Answer: 253

Concepts:triangle inequality Fibonacci extremal argument

Difficulty rating: 2390

Small hint:

In a set with no triangle, each element must be at least the sum of the two preceding elements

Big hint:

The smallest triangle-free ten-element set starting from

4, 5

grows like Fibonacci:

4, 5, 9, 14, 23, \ldots

Its largest element tells you where

n

must stop.

Solution:

Suppose a ten-element set

\{a_1 \lt a_2 \lt \cdots \lt a_{10}\}

has no triangle. Then every three elements fail the strict triangle inequality; in particular

a_{i+2} \ge a_{i+1} + a_i

for each

i.

Starting from

a_1 \ge 4

and

a_2 \ge 5,

this forces

a_3 \ge 9,

a_4 \ge 14,

a_5 \ge 23,

a_6 \ge 37,

a_7 \ge 60,

a_8 \ge 97,

a_9 \ge 157,

and

a_{10} \ge 254.

So if

n \le 253,

no ten-element subset of

\{4, 5, \ldots, n\}

can avoid triangles, since its largest element would have to be at least

254.

Conversely, taking equality throughout, the subset

\{4, 5, 9, 14, 23,

37, 60, 97, 157, 254\}

of

\{4, 5, \ldots, 254\}

has no triangle.

Therefore the largest possible value is

n = 253.