Алгоритмы без обратной связи (с сайта А.В.Шаповалова)

[sergey1]

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


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


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


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


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


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


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


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



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


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


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

[TOTAL]

Цитата:

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

Полицейские знают скорость вора и свою скорость?

[Dendr]

TOTAL в сообщении #1613642 писал(а):

Полицейские знают скорость вора и свою скорость?

Ну, поскольку "фольклор", то, мне кажется, следует предполагать, что полицейские знают следующее:
а. Угонщик находится в точке с конечной координатой, но знак неизвестен
б. Его максимальная скорость $v$
в. Их машина способна перемещаться со скоростью $u>v$

В итоге, задача немедленно решается ...

(Оффтоп)

... в пространстве $(t, x)$: вор гарантированно находится в области, ограниченной двумя прямыми, а траектория полицейских имеет такой наклон, что они гарантированно могут достичь границы из любой стартовой точки за конечное время, так что не они могут даже устраивать перерывы (в частности, требование мгновенного разворота несущественно).

Вторая - это уже классика, в разных формах встречается повсеместно. Мое первое знакомство с задачей состоялось в формулировке о крысе, бегающей по 100 картонным коробкам, и охотнике. Ютуберы-математики тоже разбирали ее.

А дальше вроде незнакомые, посоображать надобно.

[EUgeneUS]

Dendr в сообщении #1613648 писал(а):

в. Их машина способна перемещаться со скоростью $u>v$

В итоге, задача немедленно решается ...

ИМХО, полицейским нужно знать насколько их скорость гарантированно превышает скорость вора.
Иначе не решается.

[Geen]

EUgeneUS в сообщении #1613649 писал(а):

полицейским нужно знать насколько их скорость гарантированно превышает скорость вора.

Они на каждом шаге могут уменьшать предполагаемую разницу вдвое....

[Dendr]

EUgeneUS в сообщении #1613649 писал(а):

ИМХО, полицейским нужно знать насколько их скорость гарантированно превышает скорость вора.

Тьфу ты. Точно. Им же неизвестна фора вора перед ними, поэтому они должны строить гипотезу, какова она, и при каждом развороте увеличивать ее по какому-нибудь закону. Но для этого им (в рамках текущей гипотезы) нужно понимать, когда развернуться.
Если им известны числа, то проблема закрыта.

sergey1 в сообщении #1613636 писал(а):

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

А вот тут как будто бы ответ "нет".

Пусть у Васи есть таблица чисел, которые могут быть в данный момент на уме у Пети. Изначально в ней все натуральные числа.

Далее, пусть у Васи есть алгоритм, по которому он выбирает число $v$, которое называть (и оно не обязательно находится в таблице, оно может даже повторяться). Предположим, что он не угадал, тогда он производит эту же самую операцию с каждым числом в таблице, а если $v$ было в таблице, он его вычеркивает.

Если $v=1$, то оно по определению взаимно просто с $p$, поэтому Петя увеличит свое число на $2$. Соответственно, и Вася увеличит все числа в таблице на $2$.
Если $v>1$, то не существует таких $p_1, p_2$, что $p_1v+1=p_2v+2$. Поэтому все числа в таблице по-прежнему различны.

Таким образом, на каждом шаге Вася вычеркивает не больше одного числа из таблицы, то есть в ней так и останется бесконечное количество записей. Таким образом, стратегии назвать число нет, он может его только случайно угадать (подозреваю, что примерно за число Грэма ходов)

[TOTAL]

Цитата:

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

Здесь задача догнать (не обязательно наибыстрейшим способом) может быть решена так. Предполагаем, что воры исходно справа на расстоянии 1 км, гоним вправо сколько надо. Если не догнали, то предполагаем, что исходно воры слева на расстоянии 2 км, гоним налево сколько надо. Если не догнали, то предполагаем, что исходно воры справа на расстоянии 4 км, гоним ...

Цитата:

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

Про мэра не знаю, но я всегда добьюсь одного цвета. Задача может быть сведена к $10$ столбам. Подсказка: конечный цвет предопределён начальной раскраской.

[Rak so dna]

По первой задаче. $v_0$ — скорость полиции, $v_1$ — скорость вора. Я взял следующие куски пути для полицейских: $S_n=a^nS_0$ (т.е. они едут $S_0$, разворачиваются, едут $S_1$, разворачиваются, едут $S_2$ и т.д.). Тогда (если я правильно посчитал), рассматривая одно из направлений, достаточно найти такое $a,$ что бы неограниченно возрастала функция $ \frac{a^{2x+1}+1}{a+1} - \frac{v_1}{v_0}\cdot\frac{a^{2x+1}-1}{a-1}.$ Для $\frac{v_1}{v_0}=0.8$ достаточно взять, например, $a=12.$ Интуитивно кажется, что если взять нечто, растущее сильно быстрее чем $S_n=a^nS_0,$ то будет достаточно лишь условия $\frac{v_1}{v_0}<1.$ То бишь куски пути для полиции не будут зависить ни от чего. Но так ли это?

[TOTAL]

10. Инструкция мэру по перекрашиванию столбов.

1.
$(1,2), (3,4), (5,6), (7,8), (9,10), $
$(2,3), (1,4), (6,7), (5,8), (4,5), (3,6), (2,7), (1,8),$
$(8,9), (7,8), (6,9), (5,6), (4,7), (3,8), (2,9), (1,10)$

2. Так поступаем с каждой десяткой.
3. На десяти процессорах параллельно и одинаково завершаем работу.

[mihaild]

Dendr в сообщении #1613651 писал(а):

Таким образом, на каждом шаге Вася вычеркивает не больше одного числа из таблицы, то есть в ней так и останется бесконечное количество записей

Важно же чтобы любое число было вычеркнуто на каком-то шаге, а не чтобы на каком-то шаге были вычеркнуты все числа.
Петя просто перебирает все числа, которые могли быть у Васи, и на $n$-м шаге называет то число, в которое сейчас бы превратилось $n$.
Точные правила преобразований чисел неважны - они могут зависеть от исходного числа, предыдущих шагов и номера шага произвольным образом, важно лишь чтобы Петя знал, во что сейчас превратилось каждое число.

Четвертая решается аналогично - перебираем все начальные конфигурации, для каждой пишем программу, учитывающую, где мы в этой конфигурации сейчас.

[sergey1]

TOTAL в сообщении #1613642 писал(а):

Цитата:

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

Полицейские знают скорость вора и свою скорость?

Да.

[Dendr]

mihaild в сообщении #1613655 писал(а):

Важно же чтобы любое число было вычеркнуто на каком-то шаге, а не чтобы на каком-то шаге были вычеркнуты все числа.

Упс. Да, теперь понял.
Числа Вася будет называть довольно быстро безумные, но в условностях задачи - строго определенные, ну а число, которое Петя задумал, конечно.

[Rak so dna]

mihaild в сообщении #1613655 писал(а):

Четвертая решается аналогично - перебираем все начальные конфигурации, для каждой пишем программу, учитывающую, где мы в этой конфигурации сейчас.

Не совсем понял. Допустим, мы находимся в некоторой клетке поля. Запустили программу для предполагаемой конфигурации лабиринта и она не сработала (все доступные клетки не были пройдены). Нам нужно как-то вернуться в начальную клетку, что бы запустить следующую программу для следующей предполагаемой конфигурации лабиринта. Но как это сделать? Цепочка ходов ведь необратима.
Если же мы фиксируем конфигурацию лабиринта и для неё начинаем перебирать все возможные начальные позиции, то опять же непонятно, как возвращаться в исходную клетку.

[EUgeneUS]

Geen в сообщении #1613650 писал(а):

Они на каждом шаге могут уменьшать предполагаемую разницу вдвое....

И действительно.
Задача стала лучше, задаача стала веселее.

-- 17.10.2023, 12:19 --

Rak so dna в сообщении #1613653 писал(а):

То бишь куски пути для полиции не будут зависить ни от чего. Но так ли это?

В "пошаговом алгоритме", без явного выражения значений в виде последовательности, от выбора начального шага ничего не зависит. Точнее: от выбора начального шага зависят все остальные, но его можно выбрать любым.

[mihaild]

Rak so dna в сообщении #1613662 писал(а):

Нам нужно как-то вернуться в начальную клетку, что бы запустить следующую программу для следующей предполагаемой конфигурации лабиринта

Не нужно, но можно.
Мы уже прошли некоторое множество конфигураций (конфигурация - схема лабиринта + начальное положение). Теперь мы предполагаем, что настоящая конфигурация $X_n$. Зная, какие шаги мы уже сделали, мы определяем, в какой клетке мы находимся, если настоящая конфигурация $X_n$, и запускаем обход из неё.
Тут важно следующее свойство: для любой конфигурации, любая последовательность шагов продолжается до полного обхода. Если бы по краям доски была не стена, а болото, то метод бы не работал.