Головоломки

на форуме периодически публикуются разные задачки (головоломки), предлагаю объединить все это тему в одну тему (посмотрел, вроде единой такой темы нет). и выкладывать сюда интересные задачи.
мне вот эта задачка очень нравится:
Перед котом Леопольдом пять мышиных норок, расположенных в ряд. В одной из этих норок спряталась мышка. Леопольд может засунуть лапу в любую из норок и попробовать поймать мышку. Мышка боится кота, поэтому после каждой его попытки обязательно перебегает в соседнюю норку справа или слева. Может ли кот гарантированно поймать мышку? Если да, то как он должен действовать?

Fuagra @ 12.1.2012
Перед котом Леопольдом пять мышиных норок, расположенных в ряд. В одной из этих норок спряталась мышка. Леопольд может засунуть лапу в любую из норок и попробовать поймать мышку. Мышка боится кота, поэтому после каждой его попытки обязательно перебегает в соседнюю норку справа или слева. Может ли кот гарантированно поймать мышку? Если да, то как он должен действовать?

Мне вот эта понравилась задачка:

Поспорили три мудреца между собой, кто из них мудрее. Но т.к. никто не мог доказать, что он мудрее всех,то решили они пойти к другому четвёртому мудрецу. Четвёртый мудрец выслушал их и сказал: "Вот здесь у меня в шкафу стоит пять колпаков: три чёрных и два белых. Встаньте так, чтобы образовался равносторонний треугольник, а я буду по очереди каждому из вас надевать колпаки. Каждый должен видеть те колпаки, которые я надеваю на других, но никто не имеет право смотреть, какой колпак я надеваю на него самого. Кто из вас первым догадается, какой на нём колпак, и правильно объяснит, как он догадался, тот и мудрее." Выслушали три мудреца и сказали четвёртому мудрецу: "Быть по-твоёму!". И встали три мудреца в вершинах равностороннего треугольника. Закрыли глаза три мудреца, а чётвёртый мудрец надел им на головы три чёрных колпака. Открыли три мудреца глаза и долго-долго молчали. Вдруг один из них сказал: "На мне чёрный колпак!". Как он догадался?

Pr1ntScreen, допустим мышь изначально находилась в 5 норке, она будет бегать 4-5-4-5 и так до бесконечности.

https://forum.gipsyteam.ru/index.php?viewtopic=1858&hl=%D0%B3%D0%BE%D0%BB%D0%BE%D0%B2%D0%BE%D0%BB%D0%BE%D0%BC%D0%BA%D0%B8

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

Fuagra @ 12.1.2012
Перед котом Леопольдом пять мышиных норок, расположенных в ряд. В одной из этих норок спряталась мышка. Леопольд может засунуть лапу в любую из норок и попробовать поймать мышку. Мышка боится кота, поэтому после каждой его попытки обязательно перебегает в соседнюю норку справа или слева. Может ли кот гарантированно поймать мышку? Если да, то как он должен действовать?

ответ на задачу про кота леопольда:

Что-то тут не так. С чего бы ей быть обязательно в 4 норке, если её нет в норке 2? Из норки 3 она спокойно перебегает в норку 2 после первой попытки. Надо уточнить условие. Что называется попыткой? Кот вытащил лапу, или лапа остаётся в норке в момент, когда мышка перебегает?

Не предполагаем вообще, где она может быть. Кот суёт лапу в норку 2. Если там нет, то снова суёт в норку 2. Таким образом исключается вариант, что мышь была в норке 1. Далее у нас остаются три норки, в которых мышь "стартовала".

Если она была в норке 3, то могла попасть либо в 2, где её благополучно ловят со второй попытки, либо в 4. Кот суёт в 3. Мышь может попасть в 3 или 5 после третьей попытки. Снова суёт в 3. Мышь гарантированно попадается на пятой попытке, так как либо она уже в 3 после четвёртой, либо в 4 после пятой.

Если она была в норке 4, то могла попасть в 3 или 5. Кот суёт в 3. Мышь попадается или оказывается в 4. Снова суёт в 3. Мышь оказывается в 5. Кот в 4. Мышь в 4. С шестой попытки мышь попалась.

Если она была в норке 5, то могла попасть только в 4. Кот в 3. Мышь в 3 или 5. Кот в 3. Мышь или попадается сразу, или перебегает в 4, где ловится на следующем ходе. Поэтому схема такова: 2-2-3-3-4-4. Количество попыток зависит от начальной норки мыши. И, конечно же, правильно ли я принял условие задачи. Потому что если так, то по схеме 2-3-4-2-3-4 мышь может бегать бесконечно, наверное, и кот сдохнет с голода.

occean, 2-3-4-2-3-4 решение правильное и самое быстрое.
мы предполагаем изначально что мышь сидит либо в норе 2, либо в норе 4 и наш алгоритм позволяет ее поймать 2-3-4 (т.е. мы ловим мышь если она сидит в четной норе)
если мышь сидела изначально в норе 1,3 или 5. то ее движения были следующими:
1 - 2 - 1(3) - 2(4), т.е. она оказывается в четной норе;
3 - 2(4) - 1(3) 5(3) - 2 (2,4) 4 (2,4) тоже самое.
5 по аналогии с 1 норой.

Я не понимаю, с каких херов мы изначально принимаем, что она либо в 2, либо в 4?

Ещё раз прошу уточнить условие. Что такое попытка? Кот сунул лапу, проверил и высунул? Или лапа остаётся в норке, тогда мышь может при перебегании попасть в лапу? И что, это однолапый кот (если считать передние)?

кот засунул проверил и высунул и только после этого мышь может перебежать в другую нору.
а предполагаем мы для определения наиболее короткого алгоритма для решения этой задачи.
2-2-3-3-4-4 неверная схема, поскольку мышь может бегать 1-2-3-2-1.

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

Fuagra @ 12.1.2012
кот засунул проверил и высунул и только после этого мышь может перебежать в другую нору.
а предполагаем мы для определения наиболее короткого алгоритма для решения этой задачи.
2-2-3-3-4-4 неверная схема, поскольку мышь может бегать 1-2-3-2-1.

Тоже верная, но с большим числом попыток. Если мышь в 1 сидела, то на второй попытке она попадётся, так как будет сидеть уже в норке 2.

а против 4-3-2-1 эта схема не действует.
я по этой задаче не один десяток листов А4 расчертил пока доперло, на мой взгляд довольно интересная задачка:)
есть еще пару головоломок, могу выложить сюда или в общий топик, как удобно?

Да. Согласен. Перелевелил что-то.

Fuagra, давай в тот, а этот пора закрыть.

а разве система 3-5-3-1 не быстрее?

получилось максимум 5 ходов, в то время как максимальное число ходов по системе 2-3-4-2-3-4 равно 6

3-5-3-1

мышка будет бегать 1-2