Куб со стороной n >= 3 разбит перегородками на единичные кубики. Какое минимальное число перегородок между единичными кубиками нужно удалить, чтобы из каждого кубика можно было добраться до границы куба?

задан 16 Окт '16 17:05

изменен 16 Окт '16 19:46

10|600 символов нужно символов осталось
0

Эта задача вроде бы звучала раньше на форуме, но ссылку я не смог найти. Так или иначе, будем надеяться, что она не с какой-нибудь текущей олимпиады :)

Кубики, выходящие на границу, уже обладают нужным свойством, поэтому надо понять, как "подтянуть" остальные. Удобно внешнюю границу куба вообще удалить, чтобы определить, сколько перегородок нужно выломать, дабы из любого кубика мы смогли выбраться наружу.

У нас получится куб со стороной $%n-2$%, и он разбит перегородками на $%(n-2)^3$% областей. Есть ещё одна внешняя область, с которой всё должно в итоге слиться. Когда мы одну перегородку убираем, то число областей уменьшается максимум на 1. Значит, требуется не менее $%(n-2)^3$% операций.

То, что этого числа хватает, обосновывается нетрудно. Достаточно увидеть, что можно обойти все кубики друг за другом, ломая по перегородке. Это делается по слоям, где мы идём "змейкой", а потом проламываем "потолок", и поднимается на "этаж" выше.

Можно, кстати, и на языке графов было рассуждать: вершины -- центры кубиков, и через каждую перегородку проводим ребро.

ссылка

отвечен 16 Окт '16 22:52

изменен 16 Окт '16 22:53

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,700
×1,259
×477

задан
16 Окт '16 17:05

показан
526 раз

обновлен
16 Окт '16 22:53

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru