21 сент. 2010 г.

Куб сыра

Добрый день!

Давайте представим себе 27 одинаковых кубиков сыра, из которых сложен один большой куб 3х3х3. Дело это вполне обыденное, такой большой сырный куб может встретиться почти в любом доме. Но не в каждом доме есть генетически модифицированный мышонок. Итак, в институте цитологии и генетики учёные случайно вывели хитрую породу мышек, которые питаются только маленькими кубиками сыра. Тонкость в том, что съев один кусочек, мышонок принимается за соседний с ним по грани кубик сыра.

В рамках очередного бесчеловечного эксперимента мышонку опять предложили съесть 27 кубиков сыра, находящихся в космическом спутнике (т.е. гравитацией можно пренебречь). Но коварные исследователи подменили центральный кубик на муляж, который невозможно съесть (то есть, на экспериментальном столе 26 кусочков сыра и один муляж, находящийся в самом центре куба 3х3х3.

Вопрос: сможет ли мышонок съесть все 26 кусочков сыра?
Если да, то как? Если нет, то почему?

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

Успехов!

37 комментариев:

  1. У меня сразу вопрос: когда мышонок съедает один из нижних кубиков, два кубика, которые сверху, падают вниз? Если так, то задачка решается в общем-то просто.

    ОтветитьУдалить
  2. Вопрос по условию: если съесть нижний кусок сыра, то кусок выше уровнем упадёт на его место или мышонок работает в отсутствии гравитации?

    ОтветитьУдалить
  3. Если гравитация есть, то можно съесть так:

    Пусть есть слои верхний:
    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 - вывод - невозможно. (фактически решение раскраской в шахматном порядке)

    ОтветитьУдалить
  4. Andrew и LisandreL, спасибо за дельный вопрос. Я внёс уточнение в условие - эксперимент проводят в космосе, потому что задача с гравитацией становится ещё проще :)

    ОтветитьУдалить
  5. А под "гранью" понимается грань первоначального куба, или грань той фигуры, что осталась на данный момент?

    ОтветитьУдалить
  6. Ну в таком случае ответ не сможет.

    Решение - как описанно выше. Красим кусочки в чёрный и белый в шахматном порядке (углы все чёрные).

    Чёрных кусочков 14, белых - 12 (13-ый муляж).

    Предположим, что мышонок сможет съесть весь сыр. Так как двух одноцветных кусков сыра рядом нет, то в той последовательности, в которой он съедал сыр цвета будут чередоваться через 1, а значит разница между числом чёрных и белых кусков может быть 0 или 1. А она у нас 2. Противоречие. Вывод - несможет.
    Помочь бы ему смог бы только шаман. )

    P.S. Бедный мышонок. Ему приходится в невесомости питаться крашенным сыром. Будем надеяться, что красители были пищевыми.

    ОтветитьУдалить
  7. Анонимный21.09.2010, 12:02

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

    ОтветитьУдалить
  8. Анонимный21.09.2010, 12:40

    Сможет, если начнет с центрального кубика одной из граней.

    ОтветитьУдалить
  9. LisandreL, красивое решение. Интересно, можно ли сделать редукцию на следующую задачу: дана шахматная доска у которой нет 2 клеток по сторонам какой-либо большой диагонали (там, где стоят ладьи). Костяшка домино покрывает ровно две стоящие рядом клетки. Вопрос, можно ли такими костяшками покрыть эту доску (обычную доску, очевидно, можно).

    Шахматная доска двухмерная, а это задача трёхмерная, однако принцип решения у них одинаковый.

    ОтветитьУдалить
  10. Не совсем понятно условие "соседний с ним по грани". Т.е. пока он не съест все кубики на одной грани на другую он не может перейти что ли?

    ОтветитьУдалить
  11. LisandreL, я не видел ваш последний комментарий. Фактически, вы сделали редукцию. :-)

    ОтветитьУдалить
  12. vzay, как написано в условии, под граню понимается грань только что съеденного кубика сыра ("съев один кусочек, мышонок принимается за соседний с ним по грани кубик сыра").

    Спасибо, что указали на эту не самую прозрачную формулировку! Я стараюсь научиться говорить так, чтобы было почти невозможно понять неправильно, но ещё не научился этому.

    monkegoist, речь о гранях не большого куба, а только что съеденного кубика.

    ОтветитьУдалить
  13. Задача слишком похожа на обычный обход графа, который неосуществим, если больше 2 нечётных вершин. Угловые кубики имеют чётность 3 и их 8 штук.

    ОтветитьУдалить
  14. jerom, можете рассказать подробнее?
    Что плохого в наличии восьми вершин с валентностью три? Нас же никто не обязывает пройти через всё рёбра графа. Требуется лишь посетить все его вершины.

    ОтветитьУдалить
  15. 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.

    ОтветитьУдалить
  16. Нет, т.к. великая теорема Ферма.

    ОтветитьУдалить
  17. Я действительно ошибся, спутав задачу с Семью мостами Кёнигсберга.

    Надо подумать, нельзя ли построить дополняющий граф, в котором кубики превратятся в рёбра.

    ОтветитьУдалить
  18. Спиральный послойный подход. Нумерация 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

    ОтветитьУдалить
  19. ну смотря с какого начнет. если начнет с центрального на грани кубика - то без проблем.

    ОтветитьУдалить
  20. Basilevs, если вы уже читали мои комментарии, то зачем пытаетесь обойти? Там же доказанно, что этого сделать невозможно.
    Вы 2 раза «съели» 10-ый кубик.

    grimskin, ну-ну...

    ОтветитьУдалить
  21. Если в невесомости и кубики не могут изменять положение, то ответ - нет.

    Здесь задача из теории графов про обход графа.

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

    Каждый кубик - вершина графа. Соседние кубики соединяем ребрами графа. Получается есть 8 вершин (углы) у которых три соседних вершины. То есть более две вершины с нечетными степенями (числом соседей).
    Значит решения нет - сьесть все за один заход мышонок не сможет. Ему потребуется помощь экспериментатора чтобы несколько раз вернуться и доедать оставленные пропущенные кубики.

    ОтветитьУдалить
  22. Анонимный21.09.2010, 17:45

    1a1, Эйлеров путь обходит все РЕБРА графа по разу, в то время как в задаче Ильи нужно обойти все ВЕРШИНЫ по разу. Это две совершенно разные задачи.

    Обход всех вершин графа называется гамильтоновым путем. Не во всяком графе существует гамильтонов путь. Насколько я знаю, в данный момент не известно необходимого и достаточного условия для существования гамильтонового пути в данном графе. Вопрос о существовании гамильтонового пути решается полным перебором и имеет сложность NP, пруфлинк.

    ОтветитьУдалить
  23. Да, Анонимный прав.
    Это задача на гамильтонов граф. Известные из теории достаточные условия не помогают - задачу решать перебором :(

    Похоже любой путь через все вершины (кубики) должен проходить через центр - вырезанную вершину(несъедобный кубик)

    ОтветитьУдалить
  24. Этот граф имеет более 3-х вершин и валентность каждой не превосходит четырех, а 4<27/2, что по условию Дирака говорит, что граф - Гамильтонов, т.е. такой путь обхода есть.

    ОтветитьУдалить
  25. Vair, для условия Дирака должно быть >, а не <.
    Впрочем то, что условие Дирака не выполняется не гарантирует нам, что граф не Гамильтонов.

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

    (Ответов не читал, решение придумал почти сразу.)

    ОтветитьУдалить
  27. Еще подумал. Не работает мое решение. На последнюю грань так можно попасть только в середине одного из ребер, и тогда один кубик останется. Думаю дальше.

    ОтветитьУдалить
  28. После съедения верхней грани (едим начиная с центрального кубика), у нас получается корыто - центрального кубика ведь нет.

    Сначала сьедаем стенку корыта, а потом днище.

    Но центральный кубик в днище съесть не получится. Один кубик несьеденый останется.

    ОтветитьУдалить
  29. lord-corwin, у вас в оставшейся грани один кубик останется несъеденным.

    ОтветитьУдалить
  30. 2 LisandreL: Гм. Действительно. Пардоньте.

    ОтветитьУдалить
  31. Сергей, да, спасибо. До меня дошло через несколько минут, в следующем сообщении написал :)

    ОтветитьУдалить
  32. Анонимный23.09.2010, 15:21

    Кто в детстве играл во всякие математические олимпиады, должен с ходу решить, потому как первая попытка - "а не на чёт-нечёт ли эта задачка" :-)

    //aamonster

    ОтветитьУдалить
  33. Если мышь может начать поедание с центрального кубика, то задача решаема :)

    ОтветитьУдалить
  34. Олександр С., центральный кубик несъедобен, поэтому с него нельзя начинать.

    ОтветитьУдалить
  35. Не центральный-центральный, а центральный со стороны одной из слоев.

    ОтветитьУдалить
  36. Да если даже центральный кубик съедобен, то если мы с него начнём, задача будет не сильно отличаться от уже рассмотренной - ведь из центра куба он может пойти только в центр одной из граней, а оттуда (при условии, что центрального уже нет) - уже сказали.

    ОтветитьУдалить
  37. Олександр С, хорошо, пусть мышонок начнёт с центрального кубика одной из граней. Как ему съесть все 26 кусочков?

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний