Чтобы ходить с шагом x нужно все равно иметь где-то счетчик на log(x) бит.
А доказывается, что вероятность меньше 1/2 так: Роботы в паре образуют конечный автомат (на 2*x битов). Автомат начинает путешествовать в неизвестной точке d (где d - исходное расстояние между роботами) и ему надо найти 0. Поскольку число доступных битов ограничено, то в какой-то момент состояния обеих роботов зациклятся, при этом они могут оказаться ближе, чем сначала (и тогда в конце концов встречаются), либо нет (тогда встреча им не светит). Для каждого варианта, когда они сближаются, существует вариант, когда они удаляются (роботов меняем местами и запускаем с теми же исходными данными), отсюда вероятность успеха никак не может быть больше 1/2
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2007-08-05 04:29 pm (UTC)А доказывается, что вероятность меньше 1/2 так:
Роботы в паре образуют конечный автомат (на 2*x битов). Автомат начинает путешествовать в неизвестной точке d (где d - исходное расстояние между роботами) и ему надо найти 0. Поскольку число доступных битов ограничено, то в какой-то момент состояния обеих роботов зациклятся, при этом они могут оказаться ближе, чем сначала (и тогда в конце концов встречаются), либо нет (тогда встреча им не светит). Для каждого варианта, когда они сближаются, существует вариант, когда они удаляются (роботов меняем местами и запускаем с теми же исходными данными), отсюда вероятность успеха никак не может быть больше 1/2