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

[Утундрий]

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

Есть кротчайший маршрут,

Кротом прорытый?

[Rak so dna]

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

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

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

-- 17.10.2023, 16:09 --

Утундрий в сообщении #1613696 писал(а):

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

Есть кротчайший маршрут,

Кротом прорытый?

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

ладья может передвигаться по всей доске, не перепрыгивая через перегородки.

[mihaild]

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

Если маршрут зациклился, то на некоторой итерации, неизбежно сокращение "расстояния" (нового кратчайшего пути) между нашими клетками

Да, так работает. Формально, возьмем пару клеток, которые нельзя синхронизировать, и из всех пар выберем с минимальной длиной пути между клетками, а из всех таких - в которых при шахматной лексикографической нумерации бОльшая клетка как можно позже. Заметим, что если мы по кратчайшему пути ведем меньшую клетку в большую, то на каждом шаге расстояние между ними не увеличивается (потому что меньшая клетка на каждом шаге приближается к изначальному положению большей на $1$, а большая удаляется от него не больше чем на $1$), причем сохраняется оно только если большая клетка ни разу не упирается в стену. Ну и дальше противоречие: у нас либо большая клетка хоть раз упиралась в стену (и тогда расстояние уменьшилось), либо ни разу не упиралась (и тогда она сдвинулась на тот же вектор, что и меньшая, и стала лексикографически больше).

Итого на текущий момент решены вроде бы 1,2,3,4, 6а и 9.

-- 17.10.2023, 16:47 --

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

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

Вроде то же самое. Предполагаем, что она в квадрате $N \times N$, очерчиваем его с отступами, заполняем сеткой с шагом $1 / 2$, дальше предполагаем, что была в квадрате $2N \times 2N$, очерчиваем квадрат, куда могла упрыгать, и т.д.

Еще пропустил решение 10 от TOTAL. Остались 5, 6б, 7.

[TOTAL]

Цитата:

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

1. На одну клетку ПЕРВОЙ доски ставим полицейского, на остальные преступников. Полицейский выбирает преступника и приходит на клетку, где тот стоит. Точнее, где тот стоял, ведь все преступники должны повторять ходы полицейского. Потом опять и опять. Очевидно, преступника он догонит. Так переловит всех.

2. На одной клетке ВТОРОЙ доски тоже стоял полицейский со своими преступниками в других клетках. На другой доске все действующие лица повторяли ходы полицейского с первой доски. Когда преступники первой доски будут переловлены, второй полицейский, уже по своему плану, отлавливает своих, а затем идёт в нужный угол. (Полицейский с первой доски все ходы копирует.)

3. Затем первый полицейский идёт в нужный угол, а второй копирует его ходы. Затем второй идёт в нужный угол, а первый копирует. Суммарное расстояние до угла уменьшается, в результате оба окажутся где надо.

[mihaild]

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

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

Очевидно, преступника он догонит

Я бы не сказал, что очевидно, но да, верно.

Если я нигде не ошибся, то осталась седьмая задача.

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

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

[TOTAL]

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

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

Очевидно, преступника он догонит

Я бы не сказал, что очевидно, но да, верно.

Если преступник не упирается в перегородку, то точки прицеливания полицейского равномерно расположены на прямой, которая не может зайти за край доски. Поэтому преступник упрётся в перегородку и расстояние до него сократится.

Полицейский из своего исходного положения до исходного положения преступника $P_0$ идёт любым путём. Стараясь копировать ходы полицейского, преступник попадает из $P_0$ в $P_1$. А далее полицейский уже идёт точно по следам преступника из $P_0$ в $P_1$. Поскольку для полицейского путь известен, пройден ранее преступником, полицейский не тратит ходы на тыкание в стенки. А для преступника, вынужденного копировать ходы, путь из $P_1$ в $P_2$ из-за стенок может отличаться от пути из $P_0$ в $P_1$.

[Rak so dna]

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

Если я нигде не ошибся, то осталась седьмая задача.

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

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

вроде ещё вторую не решали.

Касательно седьмой задачи:
0 ход. На одну клетку вниз ;

1 ход. По диагонали вправо-вверх на три клетки ;
2 ход. На три клетки вниз.

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

[TOTAL]

Цитата:

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

Положения ферзя по вертикали (включая начальное положение $0$): $0, -1, 2, 1,-1$.
Теперь король, если ещё жив, находится на $0$. Но ферзь ещё может, попеременно занимая $1,-1$, двигаться вправо и влево с двойной королевской скоростью (за счет диагоналей).

Или убежит? Да, в одной полосе. похоже, не удержать.

[mihaild]

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

вроде ещё вторую не решали

Вторая (и первая) уже фольклор.

[Rak so dna]

Коль уж все задачи ТС в той или иной степени решены, предлагаю доказать это:

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

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

Я понимаю, что особого интереса её решать уже нет, но, тем не менее, пусть будет.

[sergey1]

Быстро здесь!
Еще на ту же тему.
По экватору планеты едет замкнутый поезд. Вагоны неразличимые, в некоторых горит свет. Доступ к включателям-выключателям есть. Как находясь внутри поезда посчитать количество вагонов.
(Видимо фольклор)

[Geen]

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

Как находясь внутри поезда посчитать количество вагонов.

А поиском не пробовали?
topic71733.html

[sergey1]

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

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

Как находясь внутри поезда посчитать количество вагонов.

А поиском не пробовали?
topic71733.html

Писатель, не читатель я

[lel0lel]

(Оффтоп)

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

[Rak so dna]

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

По первой задаче. $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.$ То бишь куски пути для полиции не будут зависить ни от чего. Но так ли это?

Если взять $S_{n-1}=n\cdot n!,$ то полиция всегда догонит вора, ничего не предполагая вообще ( кроме очевидного $v_0>v_1$ ). Наверное, даже $S_n=n!$ подойдёт.