Городская олимпиада по математике среди физ-мат школАлматы, 2008 год

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

Комментарий/решение

Ответ: при $n \ge 2$ ответ $(n-2)^3$, при $n = 1$: $0$.

Оценка. Исходно куб состоит из $n^3$ изолированных единичных кубиков. Удаление одной перегородки уменьшает количество компонент на $1$. Чтобы из каждого кубика можно было добраться до грани, каждая компонента связности должна содержать хотя бы один граничный кубик. Число граничных кубов равно $G = n^3 - (n-2)^3$. После удаления $k$ перегородок будет $n^3 - k$ компонент, и оно не превосходит $G$, откуда $k \ge (n-2)^3$.

Пример. Достаточно для каждого внутреннего кубика удалить ровно одну перегородку, соединяющую его с кубиком, который на единицу ближе к фиксированной грани. Это создаёт лес деревьев, каждое из которых содержит ровно один граничный кубик и не соединяет разные граничные кубики между собой.