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