Городская олимпиада по математике среди физ-мат школАлматы, 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$.

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