Конструктор

Условие

Никите подарили игру «Конструктор», в которой было 100 деталей разной длины. В инструкции к игре написано, что из любых 3 деталей можно составить треугольник.

Никита решил проверить это утверждение и стал составлять из деталей треугольники.

Детали лежат в наборе по возрастанию длины.

Какое наименьшее число проверок (в самом плохом случае) необходимо сделать Никите, чтобы доказать или опровергнуть то, что написано в инструкции?

Подсказка: любая из деталей короче самой длинной и длиннее самой короткой, а любые 2 детали в сумме короче 2 самых длинных и длиннее 2 самых коротких.

Ответ

Никите нужна только 1 проверка. Ему достаточно проверить, можно ли составить треугольник из 2 самых коротких деталей и 1 самой длинной.

Если треугольник не составляется, то утверждение инструкции опровергнуто. Если же его можно составить, то сумма длин 2 самых коротких деталей больше длины самой длинной, а это означает, что из любых деталей можно составить треугольник.