У Димы есть 25 одинаковых кирпичей размера 5×14×17. Дима хочет построить из всех своих кирпичей одну башню, каждый раз добавляя сверху по одному кирпичу (каждый новый кирпич добавляет 5, 14 или 17 к высоте текущей башни). Назовем число n построимым, если Дима может построить башню высоты ровно n. Сколько существует построимых чисел?

Ответ:

98

Пошаговое объяснение:

"Отрежем" от каждого кирпича по 5 с каждой стороны. Очевидно, это не повлияет на количество построимых n, просто вычтет из каждого построимого n число 5 * 25 = 125. Получатся "кирпичи" размера 0×9×12. Будет удобнее уменьшить линейные размеры кирпичей в 3 раза, это тоже не повлияет на количество построимых n. Окончательная версия задачи такая:

У Димы 25 кирпичей. Добавляя один кирпич в башню, он увеличивает её высоту на 0, 3 или 4. Сколько существует возможных значений высоты получившейся башни?

Я утверждаю, что Дима может получить башню высотой 0, 3, 4 и любую высоту от 6 до 4 * 25 = 100.

Башни высотой 0, 3, 4 и 6 строятся тривиально. Докажем, что если Дима может построить башню высоты 6 ≤ n < 100, то и высоты n + 1 сможет.

• Если в построенной башне высоты n есть хотя бы один кирпич, добавивший к высоте 3, можно его перевернуть и прибавить высоту 4.
• Если в построенной башне высоты n есть хотя бы 2 кирпича, добавивших к высоте 4, и кирпич, добавивший к высоте 0, то можно их перевернуть так, чтобы они добавляли по 3.
• Если в башне нет ни одного кирпича, добавившего 3, и не больше одного кирпича, добавившего 4, то высота всей башни не больше 4, а по предположению она не меньше 6, такого не может быть
• Если в башне нет ни одного кирпича, добавившего 3, и нет ни одного кирпича, добавившего 0, до высота всей башни 100, этот случай я тоже не рассматриваю.

Итак, как бы ни была построена башня высоты 6 ≤ n < 100, башню высоты n + 1 тоже удастся построить, что и требовалось.

Значит, всего построимых чисел 3 + (100 - 6 + 1) = 98.