Увлекательна задачка

[Sicker]

Допустим есть 10 комнат с двумя дверями напротив друг друга.
Есть вы, и еще один игрок. Вы по очереди (но можно и нет) выбираете любую из пронумерованных комнат, и входите в нее, Если вы нашли второго бегуна, то победили) Бегун может использовать любые стратегии хождения по комнатам, или даже оставаться на месте.
Вопрос - какой стратегии движения по комнатам надо придерживаться, чтобы гарантированно поймать бегунка?

[atlakatl]

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

[Sicker]

atlakatl в сообщении #1239854 писал(а):

Если игрок предпочитает посещать одну из комнат чаще других, то следует оставаться в ней.

А как вы отследите перемещения другого игрока? Никакой информации о посещении комнат нет.

atlakatl в сообщении #1239854 писал(а):

Если он равновероятно выбирает места, то ваша стратегия безразлична:

А если нет? Существует еще сто500 способов хождения.

[atlakatl]

Sicker в сообщении #1239855 писал(а):

Существует еще сто500 способов хождения.

Тогда включаем свой карманный ГСЧ и следуем его указаниям. Преследуемый может выбирать любую стратегию, - поймаем мы его в среднем за одинаковое число ходов.

[EUgeneUS]

Sicker в сообщении #1239845 писал(а):

Вопрос - какой стратегии движения по комнатам надо придерживаться, чтобы гарантированно поймать бегунка?

А его можно поймать гарантированно?

[FomaNeverov]

Как соединены комнаты? Если двери напротив друг друга - это или кольцо или прямая линия. Если прямая линия - куда ведут две двери по краям?

Раз уж задаёте задачу - формулируйте точно её условия.

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

Если прямая линия, то тут элементарно: дойдите до одного края, и если не угадали - до другого. Деваться ему некуда.

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

[atlakatl]

FomaNeverov в сообщении #1239872 писал(а):

Раз уж задаёте задачу - формулируйте точно её условия.

Условий хватает. Закольцовывать комнаты или нет дело автора.

[Munin]

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

А его можно поймать гарантированно?

Нельзя. Но способ

atlakatl в сообщении #1239857 писал(а):

Тогда включаем свой карманный ГСЧ и следуем его указаниям. Преследуемый может выбирать любую стратегию, - поймаем мы его в среднем за одинаковое число ходов.

приводит к поимке в 100 % случаев (это не то же самое, что гарантированно). И это лучшее, чего можно добиться.

[realeugene]

Sicker в сообщении #1239845 писал(а):

Допустим есть 10 комнат с двумя дверями напротив друг друга.

Можно ли ознакомиться с чертежом подобной конструкции? Как эти две двери распределены между десятью комнатами?

[atlakatl]

realeugene

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

[Dmitriy40]

Munin в сообщении #1239891 писал(а):

в 100 % случаев (это не то же самое, что гарантированно).

Интересно, чем же утверждение о 100% отличается от утверждения "гарантированно"? Что вероятность непоимки уменьшается с увеличением количества попыток понятно, даже про предел на бесконечности пожалуй понятно, непонятно почему $100\% \ne \text{гарантированно}$.

[realeugene]

Dmitriy40 в сообщении #1240022 писал(а):

Интересно, чем же утверждение о 100% отличается от утверждения "гарантированно"?

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

[Dmitriy40]

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

[realeugene]

Dmitriy40 в сообщении #1240054 писал(а):

ведь это аналогично несуществованию

Нет, не аналогично. Вероятность - это конечная мера на множестве событий. То, что мера множества равна нулю не означает, что множество пустое. Например, рациональные числа имеют на отрезке $\left[0, 1\right]$ лебегову меру нуль, но они существуют. Точно так же, существуют бесконечные пути охотника и жертвы, когда охотник никогда не ловит жертву, но вероятность случайного возникновения таких бесконечных путей равна нулю.

[worm2]

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