Алгоритмы без обратной связи, или поиск «втёмную»

Трудно найти чёрную кошку в тёмной комнате. Если увидеть её нельзя, то мы узнаем где она только когда найдём. Есть задачи на поиск, когда о результатах наших действий мы узнаём только достигнув результата. Бывает и хуже: мы и это не узнаём, но должны гарантировать, что результат достигнут.

1. На бесконечном шоссе находятся полицейская машина (ездит со скоростью до 100 км/ч) и вор на угнанном мотоцикле (ездит со скоростью до 80 км/ч). Полицейские не знают, в каком месте шоссе находится вор. Как им действовать, чтобы наверняка догнать вора? (Вор не может съехать с шоссе или спрятаться). (фольклор)

2. В одном из 1000 окопов, расположенных в ряд, спрятался робот-пехотинец. Автоматическая пушка может одним выстрелом накрыть любой окоп. В каждом промежутке между выстрелами робот (если уцелел) обязательно перебегает в соседний окоп (быть может, только что обстрелянный). Сможет ли пушка наверняка накрыть робота? (А.Шаповалов, В.Шорин)

3. Петя задумал натуральное число. Вася каждым ходом называет натуральное число. Если он называет текущее Петино число, то Петя говорит «Я проиграл». Иначе Петя меняет текущее число по такому правилу: если его текущее число p не взаимно просто с названным Васей числом v, то он меняет p на p^v+1, иначе – на p^v+2. Может ли Вася действовать так, чтобы наверняка выиграть за конечное число ходов? (А.Шаповалов)

4. Назовем лабиринтом шахматную доску 8x8, где между некоторыми полями вставлены перегородки. По команде ВПРАВО ладья смещается на одно поле вправо или, если справа край доски или перегородка, остается на месте; аналогично выполняются команды ВЛЕВО, ВВЕРХ и ВНИЗ. Петя пишет программу - конечную последовательность указанных команд, и дает ее Васе, после чего Вася выбирает лабиринт и помещает в него ладью на любое поле. Докажите, что Петя может написать такую программу, что ладья обойдет все доступные поля в лабиринте при любом выборе Васи. (В.Уфнаровский, А.Шаповалов)

5. Капитан Врунгель в своей каюте разложил перетасованную колоду из 52 карт по кругу, оставив одно место свободным. Матрос Фукс с палубы, не отходя от штурвала и не зная начальной раскладки, называет карту. Если эта карта лежит рядом со свободным местом, Врунгель ее туда передвигает, не сообщая Фуксу. Иначе ничего не происходит. Потом Фукс называет еще одну карту, и так сколько угодно раз, пока он не скажет "стоп".
а) Может ли Фукс добиться того, чтобы после "стопа" каждая карта наверняка оказалась не там, где была вначале?
б) Может ли Фукс добиться того, чтобы после "стопа" рядом со свободным местом наверняка не было туза пик? (Л.Медников, А.Шаповалов)

6. Назовем лабиринтом шахматную доску 100x100, где между некоторыми полями вставлены перегородки, но так, что ладья может передвигаться по всей доске, не перепрыгивая через перегородки. По команде ВПРАВО ладья смещается на одно поле вправо или, если справа край доски или перегородка, остается на месте; аналогично выполняются команды ВЛЕВО, ВВЕРХ и ВНИЗ. Конечную последовательность таких команд назовем программой.
а) Дан лабиринт. Докажите, что есть программа, выполнив которую, ладья окажется в верхней правой клетке лабиринта независимо от того, где она стояла вначале.
б) Даны два лабиринта. Докажите, что есть программа, выполнив которую, ладья окажется в верхней правой клетке лабиринта независимо от того, в каком из двух лабиринтов и на какой клетке она стояла вначале. (А.Шаповалов)

7. На бесконечной шахматной доске стоят ферзь и невидимый король. Известно, что ферзь дал шах по горизонтали, и король ушел из под шаха. Докажите, что ферзь может ходить так, чтобы король наверняка ещё раз попал под шах. (А.Шаповалов)

Дополнительные задачи

8. Левша и невидимая блоха на плоскости играют, ходя по очереди. Очередным ходом Левша проводит прямую, а блоха совершает прыжок длины 1, не пересекающий ни одной прямой. Если таких прыжков нет, блоха проигрывает. Может ли Левша выиграть, как бы не играла блоха? (А.Шаповалов)

9. На бесконечной шахматной доске находятся ферзь и невидимый король, которому запрещено ходить по диагонали. Они ходят по очереди. Может ли ферзь ходить так, чтобы король рано или поздно попал под шах? (Е.Черепанов)

10. Вдоль дороги стоит 100 пронумерованных подряд столбов, как то покрашеных в три цвета. Мэр столбов не видит. Он может назвать пару номеров, и если столбы разного цвета, их перекрасят в третий цвет, а если одинакового – то так и оставляют. В любом случае мэру ничего не докладывают. Всегда ли мэр может с помощью таких операций добиться, чтобы все столбы стали одинакового цвета? (С.Волченков)