задача

[juan_gandhi]

На прямую высаживаются два робота с идентичной программой. Свои координаты они не знают. Как их запрограммировать так, чтобы они обязятельно встретились?

Кто-нибудь знает эту задачу? Или её решение? Мое решение было такое - случайные блуждания. Но мой коллега, malaya_zemlya, заметил, что совершенно неочевидно, что роботы имеют доступ к датчику случайных чисел, а внутренний генератор... ну вы поняли, он их синхронизирует.

Есть идейки? Мне эту задачку задавали года три назад; я предложил случайные блуждания, но интервьюёры моё решение не поняли. Ну не учили их вероятности. Неважно, однако. Меня больше интересует наличие решения.

Comments

[malaya-zemlya.livejournal.com]

Чтобы ходить с шагом x нужно все равно иметь где-то счетчик на log(x) бит.

А доказывается, что вероятность меньше 1/2 так:
Роботы в паре образуют конечный автомат (на 2*x битов). Автомат начинает путешествовать в неизвестной точке d (где d - исходное расстояние между роботами) и ему надо найти 0. Поскольку число доступных битов ограничено, то в какой-то момент состояния обеих роботов зациклятся, при этом они могут оказаться ближе, чем сначала (и тогда в конце концов встречаются), либо нет (тогда встреча им не светит). Для каждого варианта, когда они сближаются, существует вариант, когда они удаляются (роботов меняем местами и запускаем с теми же исходными данными), отсюда вероятность успеха никак не может быть больше 1/2

[kot-ivanovich.livejournal.com]

Oh, dear...

Чтобы ходить с шагом x нужно все равно иметь где-то счетчик на log(x) бит.

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

А доказывается, что вероятность меньше 1/2 так...

Вы не очень прочли, что я написал. ОК, подробнее: перейдя в систему координат одного из роботов, мы получаем процесс случайных блужданий статистически эквивалентный каноническим случайным блужданиям, с шагом 2 и частотой 1/2. Давайте забудем про эти двойки для простоты – такие мелочи нас сейчас не волнуют. Период совместного генератора двух роботов всё равно L (а не L², кстати). Допустим, что исходное расстояние между роботами d = 1. Какова вероятность того, что они разминутся? При L >> 1 это просто вероятность невозврата в начало координат, т.е., кажется, exp(-L^1/2) (тут я мог слегка наврать – нет учебника под рукой, а искать в сети лень). Это не ноль, но это фантастически маленькое число для любого разумного L. А если d > 1 то вероятность всё равно такая же, поскольку по исчерпании цикла я удваиваю шаг. Всё.