|
|
 |
Условие
Куб со стороной n ( n3 ) разбит перегородками на единичные кубики.
Какое минимальное число перегородок между единичными кубиками
нужно удалить, чтобы из каждого кубика можно было добраться до
границы куба?
Решение
Покажем, что меньшего, чем (n-2)3, числа удаленных перегородок недостаточно.
Удалим все граничные кубики. Останется куб (n-2)×(n-2)×(n-2),
разбитый перегородками на (n-2)3 кубиков. Теперь пространство разделено перегородками
на (n-2)3+1 областей, считая внешнюю. Удаление одной перегородки уменьшает число областей не
более, чем на 1. В конце число областей должно стать равным 1, поэтому придется удалить не менее (n-2)3
перегородок.
Этого количества хватает: достаточно из каждого неграничного кубика убрать нижнюю грань.
Ответ
(n-2)3.
