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?$

答案

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.$

2001 AIME II Problem 5

Solution:

Problem 5 in Other Years