Two identical robots on a loop that must meet
Asked at Jump Trading, Hudson River Trading
Two identical robots are dropped on different stations of a circular track with stations. They run the exact same program. Each second, a robot may step one station clockwise, step one station counterclockwise, or stay put, and both act at the same instant. They want to guarantee they will one day both sit on the same station at the same second.
First: show that no fixed (deterministic) identical program can guarantee a meeting. Then: give a plan that succeeds with probability 1.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.