How to prove the first part of Floyd's algorithm for cycle detection?

Question

In the first part of Floyd's algorithm, the hare moves two steps for every step of the tortoise. If the tortoise and hare ever meet, there is a cycle, and the meeting point is part of the cycle, but not necessarily the first node in the cycle.

I cannot understand why two pointers must meet sometime if the circle exist? How about replace "two steps" with "three steps"?

I hope someone could prove it to me...

Answer 1

Note that when both tortoise and hare are in the cycle, their relative speed becomes 1, virtually hare chases standing tortoise with this speed, so hare will meet tortoise in N <= Cycle_Len steps.

You can replace "two steps" with "three steps", but you have to check whether they meet at every hare substep