Решение задачи 451

Условие:

Для оклейки кубика n×n×n имеется неограниченный набор полосок ширины 1, каждая из которых состоит из целого числа клеток. Какое наименьшее число полосок необходимо взять, чтобы оклеить кубик в один слой (оклеивать разрешается так, чтобы каждая клетка полоски покрывала на поверхности кубика какую-то клетку целиком)?

Решение:

Оценка:

Отметим 3n клеток на кубе: диагонали на трех смежных гранях, как показано на рисунке (n=3).

Обозначим множество отмеченных клеток через M. Рассмотрим какую-нибудь клетку А из множества M. Через F(A) обозначим те три клетки, которые могут быть покрыты вместе с клеткой А одной полосой (А входит в эти три клетки). Пусть F(A)={A, B, C}, тогда F(A)=F(B)=F(C)={A, B, C}. Другими словами множество M разбивается на непересекающиеся тройки, причем никакая полоса не может накрыть клетки из разных троек. Также заметим, что чтобы накрыть три клетки, нужно хотя бы две полосы. Получается, чтобы оклеить множество M, а значит и весь куб, нужно минимум 2n полосок.

Пример:

На картинке с помощью развертки показано, как оклеить куб 3×3×3 шестью полосками, один цвет обозначает одну полоску. Для куба n×n×n оклейка аналогична.

Ответ: 2n.