Вот еще задачка.
На одномерную бесконечную ленту десантируют роботов. Лента поделена на ячейки. Требуется запрограммировать роботов так, чтобы они однажды собрались все вместе (в одной ячейке).
Каждый робот после посадки оставляет в месте приземления парашют.
Далее роботы начинают действовать в соответствии с заложенной в них программой. За один шаг программы робот может проверить, есть ли в его ячейке какой-нибудь парашют (но не может проверить, есть ли в ячейке другой робот!), и может при желании сдвинуться влево или вправо на одну ячейку. Программы всех роботов выполняются с одинаковой скоростью.
Количество роботов неизвестно. Но это количество — конечное число.
После того, как роботы соберутся вместе, не обязательно, чтобы они оставались в этом положении или остановились. Достаточно лишь, чтобы за конечное число шагов гарантированно наступила ситуация, когда все роботы находятся в одной и той же ячейке ленты.