Добрый день!
Давайте представим себе 27 одинаковых кубиков сыра, из которых сложен один большой куб 3х3х3. Дело это вполне обыденное, такой большой сырный куб может встретиться почти в любом доме. Но не в каждом доме есть генетически модифицированный мышонок. Итак, в институте цитологии и генетики учёные случайно вывели хитрую породу мышек, которые питаются только маленькими кубиками сыра. Тонкость в том, что съев один кусочек, мышонок принимается за соседний с ним по грани кубик сыра.
В рамках очередного бесчеловечного эксперимента мышонку опять предложили съесть 27 кубиков сыра, находящихся в космическом спутнике (т.е. гравитацией можно пренебречь). Но коварные исследователи подменили центральный кубик на муляж, который невозможно съесть (то есть, на экспериментальном столе 26 кусочков сыра и один муляж, находящийся в самом центре куба 3х3х3.
Вопрос: сможет ли мышонок съесть все 26 кусочков сыра?
Если да, то как? Если нет, то почему?
Как вы уже догадались, это была первая из обещанных задачек о кубах. Полагаю, скоро в комментариях появятся разные решения, поэтому будьте осторожны, открывая их.
Успехов!
Понравилась заметка? Подпишитесь на
RSS-feed или email-рассылку.
Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
RSS-feed или email-рассылку.Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
У меня сразу вопрос: когда мышонок съедает один из нижних кубиков, два кубика, которые сверху, падают вниз? Если так, то задачка решается в общем-то просто.
ОтветитьУдалитьВопрос по условию: если съесть нижний кусок сыра, то кусок выше уровнем упадёт на его место или мышонок работает в отсутствии гравитации?
ОтветитьУдалитьЕсли гравитация есть, то можно съесть так:
ОтветитьУдалитьПусть есть слои верхний:
1 2 3
4 5 6
7 8 9
средний:
10 11 12
13 14 15
16 17 18
(14-ый несъедобный).
нижний:
19 20 21
22 23 24
25 26 27
Тогда есть можно так:
1, 2, 3, 6, 5, 4, 7, 8, 9, 10 ,11, 12, 15, 18, 17, 16, 25, 22, 19, 20, 21, 24, 27, 26, 23 и 13 (свалившийся на место 22).
Если гравитации нет (ну или как-то по другому кусочки закреплены), то по предыдущему решению видно, что мышонку надо съесть 14 нечётных и 12 чётных кубиков сыра, но рядом с каждым чётном кубиком только нечётные, а с каждым нечётным - чётные. Значит число съеденных чётных и нечётных кубиков может различаться не более чем на 1 - вывод - невозможно. (фактически решение раскраской в шахматном порядке)
Andrew и LisandreL, спасибо за дельный вопрос. Я внёс уточнение в условие - эксперимент проводят в космосе, потому что задача с гравитацией становится ещё проще :)
ОтветитьУдалитьА под "гранью" понимается грань первоначального куба, или грань той фигуры, что осталась на данный момент?
ОтветитьУдалитьНу в таком случае ответ не сможет.
ОтветитьУдалитьРешение - как описанно выше. Красим кусочки в чёрный и белый в шахматном порядке (углы все чёрные).
Чёрных кусочков 14, белых - 12 (13-ый муляж).
Предположим, что мышонок сможет съесть весь сыр. Так как двух одноцветных кусков сыра рядом нет, то в той последовательности, в которой он съедал сыр цвета будут чередоваться через 1, а значит разница между числом чёрных и белых кусков может быть 0 или 1. А она у нас 2. Противоречие. Вывод - несможет.
Помочь бы ему смог бы только шаман. )
P.S. Бедный мышонок. Ему приходится в невесомости питаться крашенным сыром. Будем надеяться, что красители были пищевыми.
на данный момент вынужден согласиться с LisandreL(((
ОтветитьУдалитьхотя решение задачи, думаю, кроется в том, что средний кубик должен иметь порядковый номер 27, и следовательно существует такой путь мыши при котором она пройдет равное количество четных и нечетных кубиков...
это только теория и пока у меня такой путь не получился((
Сможет, если начнет с центрального кубика одной из граней.
ОтветитьУдалитьLisandreL, красивое решение. Интересно, можно ли сделать редукцию на следующую задачу: дана шахматная доска у которой нет 2 клеток по сторонам какой-либо большой диагонали (там, где стоят ладьи). Костяшка домино покрывает ровно две стоящие рядом клетки. Вопрос, можно ли такими костяшками покрыть эту доску (обычную доску, очевидно, можно).
ОтветитьУдалитьШахматная доска двухмерная, а это задача трёхмерная, однако принцип решения у них одинаковый.
Не совсем понятно условие "соседний с ним по грани". Т.е. пока он не съест все кубики на одной грани на другую он не может перейти что ли?
ОтветитьУдалитьLisandreL, я не видел ваш последний комментарий. Фактически, вы сделали редукцию. :-)
ОтветитьУдалитьvzay, как написано в условии, под граню понимается грань только что съеденного кубика сыра ("съев один кусочек, мышонок принимается за соседний с ним по грани кубик сыра").
ОтветитьУдалитьСпасибо, что указали на эту не самую прозрачную формулировку! Я стараюсь научиться говорить так, чтобы было почти невозможно понять неправильно, но ещё не научился этому.
monkegoist, речь о гранях не большого куба, а только что съеденного кубика.
Задача слишком похожа на обычный обход графа, который неосуществим, если больше 2 нечётных вершин. Угловые кубики имеют чётность 3 и их 8 штук.
ОтветитьУдалитьjerom, можете рассказать подробнее?
ОтветитьУдалитьЧто плохого в наличии восьми вершин с валентностью три? Нас же никто не обязывает пройти через всё рёбра графа. Требуется лишь посетить все его вершины.
jerom, легко увидеть, что эти рассуждения тут не применимы.
ОтветитьУдалитьУ целого (без помененной середины) кубика есть всё те же 8 вершин с валентностью 3, да ещё и 6 середин граней с валентностью 5. Тем не менее он съедается достаточно просто «змейкой»: 1, 2, 3, 6, 5, 4, 7, 8, 9, 18, 17, 16, 13, 14, 15, 12, 11, 10, 19, 20, 21, 24, 23, 22, 25, 26, 27.
Нет, т.к. великая теорема Ферма.
ОтветитьУдалитьЯ действительно ошибся, спутав задачу с Семью мостами Кёнигсберга.
ОтветитьУдалитьНадо подумать, нельзя ли построить дополняющий граф, в котором кубики превратятся в рёбра.
Спиральный послойный подход. Нумерация Lisandrel
ОтветитьУдалить5 2 3 6 9 8 7 4 1 10 11 12 15 18 17 16 13 10 19 20 21 24 27 26 25 22 23
ну смотря с какого начнет. если начнет с центрального на грани кубика - то без проблем.
ОтветитьУдалитьBasilevs, если вы уже читали мои комментарии, то зачем пытаетесь обойти? Там же доказанно, что этого сделать невозможно.
ОтветитьУдалитьВы 2 раза «съели» 10-ый кубик.
grimskin, ну-ну...
Если в невесомости и кубики не могут изменять положение, то ответ - нет.
ОтветитьУдалитьЗдесь задача из теории графов про обход графа.
есть теорема "Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечетной степени."
Каждый кубик - вершина графа. Соседние кубики соединяем ребрами графа. Получается есть 8 вершин (углы) у которых три соседних вершины. То есть более две вершины с нечетными степенями (числом соседей).
Значит решения нет - сьесть все за один заход мышонок не сможет. Ему потребуется помощь экспериментатора чтобы несколько раз вернуться и доедать оставленные пропущенные кубики.
1a1, Эйлеров путь обходит все РЕБРА графа по разу, в то время как в задаче Ильи нужно обойти все ВЕРШИНЫ по разу. Это две совершенно разные задачи.
ОтветитьУдалитьОбход всех вершин графа называется гамильтоновым путем. Не во всяком графе существует гамильтонов путь. Насколько я знаю, в данный момент не известно необходимого и достаточного условия для существования гамильтонового пути в данном графе. Вопрос о существовании гамильтонового пути решается полным перебором и имеет сложность NP, пруфлинк.
Да, Анонимный прав.
ОтветитьУдалитьЭто задача на гамильтонов граф. Известные из теории достаточные условия не помогают - задачу решать перебором :(
Похоже любой путь через все вершины (кубики) должен проходить через центр - вырезанную вершину(несъедобный кубик)
Этот граф имеет более 3-х вершин и валентность каждой не превосходит четырех, а 4<27/2, что по условию Дирака говорит, что граф - Гамильтонов, т.е. такой путь обхода есть.
ОтветитьУдалитьVair, для условия Дирака должно быть >, а не <.
ОтветитьУдалитьВпрочем то, что условие Дирака не выполняется не гарантирует нам, что граф не Гамильтонов.
Сможет: начать с центрального кусочка на любой из граней и двигаться "по спирали", обходя центральный кусочек куба: сначала съедаем всю эту грань, потом поднимаемся в "пояс" вокруг центрального кусочка, съедаем его весь, поднимаемся в оставшуюся грань и съедаем ее всю.
ОтветитьУдалить(Ответов не читал, решение придумал почти сразу.)
Еще подумал. Не работает мое решение. На последнюю грань так можно попасть только в середине одного из ребер, и тогда один кубик останется. Думаю дальше.
ОтветитьУдалитьПосле съедения верхней грани (едим начиная с центрального кубика), у нас получается корыто - центрального кубика ведь нет.
ОтветитьУдалитьСначала сьедаем стенку корыта, а потом днище.
Но центральный кубик в днище съесть не получится. Один кубик несьеденый останется.
lord-corwin, у вас в оставшейся грани один кубик останется несъеденным.
ОтветитьУдалить2 LisandreL: Гм. Действительно. Пардоньте.
ОтветитьУдалитьСергей, да, спасибо. До меня дошло через несколько минут, в следующем сообщении написал :)
ОтветитьУдалитьКто в детстве играл во всякие математические олимпиады, должен с ходу решить, потому как первая попытка - "а не на чёт-нечёт ли эта задачка" :-)
ОтветитьУдалить//aamonster
Если мышь может начать поедание с центрального кубика, то задача решаема :)
ОтветитьУдалитьОлександр С., центральный кубик несъедобен, поэтому с него нельзя начинать.
ОтветитьУдалитьНе центральный-центральный, а центральный со стороны одной из слоев.
ОтветитьУдалитьДа если даже центральный кубик съедобен, то если мы с него начнём, задача будет не сильно отличаться от уже рассмотренной - ведь из центра куба он может пойти только в центр одной из граней, а оттуда (при условии, что центрального уже нет) - уже сказали.
ОтветитьУдалитьОлександр С, хорошо, пусть мышонок начнёт с центрального кубика одной из граней. Как ему съесть все 26 кусочков?
ОтветитьУдалить