Вот вам задачка, которую мне пару дней назад задал товарищ, и которая очень мне понравилась. Задачка в действительности не сложная, но интересная.
Есть пять норок, расположенных подряд. В одной из них прячется мышка, но кошка не знает в какой именно. Кошка сует лапу в какую-либо норку. Если поймала мышку — молодец. Если не поймала — мышка перебегает в соседнюю норку, и кошка опять засовывает лапу в какую-то норку.
То есть игра сводится к тому, что попеременно кошка пытается угадать в какой норке находится мышка, а затем, когда кошка уже вытащила лапу, мышка перебегает в соседнюю норку. Остаться на месте мышка не может, обязательно должна перебежать.
Теперь вопрос: какая должна быть тактика кошки для того, чтобы гарантированно поймать мышку за какое-то разумное (конечное) число попыток.
Ответ наверняка кто-то приведет в комментариях, либо если никто не приведет, то я напишу его в следующем году.
Для одной норки: суём лапу в норку №1;
для 2-х: в норку №1, потом в норку №1;
3: №2, №2;
4: 2, 3, 3, 2;
остаётся проверить, что для 5-ти норок подходит стратегия
5: 2, 3, 4, 4, 3, 2;
или
5: 2, 3, 4, 2, 3, 4.
Следующий комментатор пусть объясняет, почему так, и каково множество стратегий в общем виде.
По-идее, такую задачу нужно предлагать решить без карандаша, иначе из математической она превращается в механический поиск шаблона.
1,1,2,2,3,3,4,4,5,5
просто прижимаем ее к краю,перепроверяя каждую норку,чтобы не убежала
@ naon:
Прижать не получится. Если на 2 шаге мышь в норе 2, на 3 шаге она будет в норе 1, т.е. проскочила.
да,лоханулся)
Уточни условия:
1. Она может через норку пробегать? Т.е. если кошка полезло во вторую, а мышка была в третьей, она может убежать в первую? Она вроде как не соседняя, если мы точно подходим к определениям.
2. Считаются ли норки 1 и 5 соседними?
@ anton:
1. Нет, не может. Бегать она может только в смежную норку. Причем она бежит в тот момент, когда кошка лапу уже вытащила. То есть если лапа кошки была в норке 3, а мышка в норке 4, то потом мышке ничто не мешает побежать в норку 3.
2. Норки 1 и 5 соседними не считаются.
любая, 2 или 4, 2 или 4, 2 или 4, 3 до бесконечности
хотя возможно там за счет отражения вероятностей резонанс возникает не на каждом шагу так что бесконечная стратегия будет выглядет как смена «2 или 4, 3″, как то считать лениво
@ LaFut:
Поймать мышку можно за конечное число шагов.
Подсказка )
Поймать мышку можно меньше чем за 6 ходов.
Ответ не публикую, ибо уже решил её давным-давно.
@ HaskellX:
«Меньше» чем за 6, или «меньше либо равно»? Как «меньше» я не знаю.
ну значит каких то условий в задаче не хватает
@ LaFut:
Первый же комментарий приводит стратегию в шесть шагов, которая работает. Остается только доказать почему она работает.
обои эти стратегии обходятся
2, 3, 4, 4, 3, 2
5 4 3 2 3 4
2, 3, 4, 2, 3, 4
5 4 3 4 3 2
а, был не прав. что то не то в голове крутил
просто идем от второй до предпоследней в которую тыкаемся дважды, после чего возвращаемся ко второй. так вроде при любом количестве нор сработает.
Я, конечно, полный профан в математике, но я удивлен, почему никто еще не предложил вариант, в котором кошка все время проверят третью норку? Пример: [o] — мышка в норке, [x] — лапа кошки в норке, [0-9] — норка.
Итерация 1:
[o] [2] [x] [4] [5]
Итерация 2:
[1] [o] [x] [4] [5]
Итерация 3:
[1] [2] [ox] [4] [5]
Вуаля! :) Видимо, я упустил что-то очень очевидное, что никто даже и не подумал рассматривать такой вариант.
из соображений симетрии, начиная бомбить с середины меньше надо будет рассматривать. Перебрав абсолютно все(не так уж это геморно), получаем, что надо 8 ходов.
33234432 ну или 33432234
@ kyrylo:
Мышка вполне может побежать после второй итерации обратно в первую норку.
@ lawenan-law:
Да, вроде тоже решение, хотя тут вот приводили в шесть ходов.
Как доказать минимальность?
@ lawenan-law:
Довольно не сложно — я напишу об этом в заметке.
lawenan-law написал:
Я рисовал ориентированный граф возможных перемещений мышки для каждого хода, за (n-2) ходов переводил его в направленный и ещё (n-2) ходов убирал из него вершины. Нарисовав граф, становится интуитивно понятно, что такая стратегия оптимизирует worst case scenario. Но формально мне это доказывать было лень, т.к., по-видимому, существует более простое комбинаторное или числовое доказательство.
К тому же возникает два других вопроса:
1) Какая стратегия оптимизирует average case (мат. ожидание числа попыток поймать мышь)?
2) Как изменится стратегия и мат. ожидание, если мышь будет пытаться оттянуть свою кончину?
Вот, кстати, эта же задача от 2001 года.
действующее решение на 8 ходов: 22332244
442244
или наоборот
Eugene написал:
не подходит
мышка легко убегает: 323432
234234.
234432.
И симметричные.
В 15 каменте ошибка, эти стратегии не обходятся.
Если мышка изначально в «четной» норке, ловится за три хода.
Иначе — за три хода она гарантированно попадает в «четную» норку и ловится по вышесказанному.
Вот так?
44333221
:-)
Ход1: суем лапку в случайную норку
междуходие: смотрим в какую норку бежит мышка
Ход2: суем лапу в ту самую норку
=)
244322 также подходит
Допустим нужно N шагов для поимки. Точно загнать мы можем лиш ьв норки 2 и 4 (предварительно зная что мышь в 1 или 5). Нужно идти от обратного хода (предположить что мышь на N-ом ходе в 4 или 2). далее стриом обратное дерево на основе того из каких норок мышь могла попасть в текущую допустимую и просчиытвая какой ход нужно было сделать чтобы предотвратить иные варианты. Вот мои последние 3 хода к примеру
2 3 4
_____
2 3 4
5
4
Надеюсь, логика более-менее ясна. Далее на ходу N-3 есть равноценные ходы 2 и 4. Сделав один из них получаем возможность ходов 2135 либо 4135 и понимаем, что за один ход нам в такое положение мышь не загнать, т.е. к имеющимся 4-м шагам нужно добавить еще минимум два.
Приятно удивлюсь, если окажется возможным решение в 5 шагов за счет какой-нибудь четности.
блин, неправильно таблица отобразилась
2 3 4
_____
2-3-4
4-5
Паравозик написал:
Дальше не читал. Для мыши: 321234.
6 ходов
норки:
1
2 а)»проверяем» / б)»проверяем» / е»поймали»
3 д)»проверяем»
4 в)»проверяем» / г»проверяем»
5
комментарий:
а) Проверили норку 2 — мышь или в норке 1 или в 3-5, .
б) Если мышь была в норке 1 то должна перейти в 2, проверяем там.
Соответственно мышь сейчас в норке 3 или 4-5
в) Сначала проверяем 4-5; если в 4, то поймали.
г) Если в 5, то поймали след. ходом, так как должна перейти на 4.
Соответственно мышь была в норке 3. За два хода (когда мы 2 раза проверяли норку 4) мышка могла сходить 3-2-1 или 3-2-3.
д) Проверяем норку 3. Если мышки нету, значит она сходила 3-2-1. И сейчас находится в норке 2.
е) Поймали в норке 2.
[...] к задачке, которую недавно публиковал. Там в принципе в [...]