Треугольник из палочек

[Ktina]

Имеем $n$ палочек длины $1\le l_1<l_2<\dots <l_n\le 2012$
При каком наименьшем $n$ можно утверждать, что найдутся три палочки, из которых можно сложить треугольник?

[venco]

Очевидно, 18.

[Gagarin1968]

venco в сообщении #562276 писал(а):

Очевидно, 18.

Прошу прощения за дичайший некропостинг (теме-то уже больше 14 лет!), но дело в том, что я люблю давать старые задачи с dxdy своим ученикам. В том числе и эту. И её вчера решил один из них, очень толковый парень 9-классник. Но его ответ отличается от ответа уважаемого venco и равен $17$.
Привожу его решение:
Три палочки с длинами $ a<b<c$ не образуют треугольник, если выполняется неравенство: $a+b\leqslant c$.
Теперь, для того чтобы найти минимальное $n$, при котором треугольник обязательно существует, нужно определить максимальное количество палочек, из которых треугольник сложить нельзя, и прибавить к нему единицу.
А для того, чтобы набрать как можно больше палочек без единого треугольника, понятно, что их длины должны расти как можно медленнее. Минимально возможный рост даёт последовательность Фибоначчи. Вот вся цепочка чисел, не превышающих наибольшую длину $2012$:
$l_1=1$,
$l_2=2$,
$l_3=3$,
$l_4=5$,
$l_5=8$,
$l_6=13$,
$l_7=21$,
$l_8=34$,
$l_9=55,
$l_{10}=89$,
$l_{11}=144$,
$l_{12}=233$,
$l_{13}=377$,
$l_{14}=610$,
$l_{15}=987$,
$l_{16}=1597$.
А вот следующее число Фибоначчи $987+1597=2584$ уже превышает заданную максимальную длину $2012$.
Поэтому можно выбрать лишь $16$ палочек (выписанный набор), из которых ни одна тройка не образует треугольник. А 17-я палочка неизбежно окажется короче $2584$, а это нарушит условие неравенства треугольника (которое я привёл в начале поста) и гарантирует нам появление по меньшей мере одного треугольника.
Таким образом, наименьшее число палочек, из которых гарантированно можно сложить треугольник, равно $17$.
Немного поразмыслив, я, кажется понял, почему уважаемый venco дал очевидный для него ответ $18$. Дело в том, что последовательность Фибоначчи начинается с двух единиц: $1,1,2,3,5,8,\ldots$
Но если бы длины палочек могли повторяться, то в нашам наборе без треугольников было бы $17$ палочек, а для гарантии как минимум одного треугольника понадобилось бы $18$. Однако в условии задачи между длинами стоят знаки строгого неравенства.
В итоге мы получаем сдвинутый на одну позицию вправо ряд Фибоначчи, где все элементы строго возрастают. В этом ряду ровно 16 чисел не превышают 2012. Семнадцатую уникальную палочку без создания треугольника добавить уже физически невозможно.
venco, я прав?
Я вижу, что venco присутствует на форуме.

[waxtep]

Gagarin1968 в сообщении #1724824 писал(а):

Семнадцатую уникальную палочку без создания треугольника добавить уже физически невозможно.

Но можно же взять палочки с длинами $1,1+\varepsilon,2+\varepsilon,3+2\varepsilon,\ldots$

[Gagarin1968]

waxtep в сообщении #1724827 писал(а):

Но можно же взять палочки с длинами $1,1+\varepsilon,2+\varepsilon,3+2\varepsilon,\ldots$

Да, действительно!
Я-то дал своим ученикам условие с целочисленными длинами. А при вещественных $l_i$ получается, что 17-й член всё ещё строго меньше 2012. И тогда ответ 18.