Условие
Петя купил "Конструктор", в котором было 100 палочек разной длины. В инструкции к "Конструктору" написано, что из любых трёх палочек "Конструктора" можно составить треугольник. Петя решил проверить это утверждение, составляя из палочек треугольники. Палочки лежат в конструкторе по возрастанию длин. Какое наименьшее число проверок (в самом плохом случае) надо сделать Пете, чтобы доказать или опровергнуть утверждение инструкции?
Решение
Пете достаточно проверить, можно ли составить треугольник из двух самых коротких палочек и одной самой длинной. Если треугольник не составляется, то утверждение инструкции опровергнуто. Если же треугольник составить можно, то сумма длин двух самых коротких палочек больше длины самой длинной. Но в этом случае сумма длин двух любых палочек набора длиннее любой другой. (Действительно, сумма длин двух любых не меньше суммы длин самых коротких, а длина любой палочки не больше длины самой длинной.) А это и означает, что из любых палочек можно составить треугольник, т. е. утверждение инструкции доказано.
Ответ
Одна проверка.
Источники и прецеденты использования
