Задача с палочками
У Андрея есть палочки с целочисленными длинами и общей длиной 200. Ни из каких трёх нельзя составить треугольник. Какое наибольшее число палочек может быть?
Я знаю что любая палочка должна быть меньше либо равна суммы двух других, но что с этой инфой делать так и не понял.
Ответы (1 шт):
Автор решения: Harry
→ Ссылка
Ну, у меня ощущение, что минимальный набор включает палочки
1 1 2 3 5 8 ...
ну, т.е. числа Фибоначчи. Вроде бы всего - 10 палочек:
1 1 2 3 5 8 13 21 34
эти 9 палочек имеют длину 88. Если возьмем следующую палочку 55, то останется неиспользованной длина 57, и треугольник можно будет сделать. Поэтому приходится брать после палочки 34 палочку длиной 112.
Так что окончательно - 10 палочек.