- 始点からうさぎ(fast)と亀(slow)を走らせる
- 出発からm秒後に出会ったとする
- ループがあるときは上記の状態になっている
- ループの始点をOとする
- ループの一周の長さ:μ
- ループに入るまでの道の長さ:λ
- Oからd進んだところでうさぎと亀が出会ったとする
- 出会った位置からλだけ移動すると、d+λ = m = aμ なので(!?)Oに(何週かするかもしれないが)到達する
- ∵ d = m - λ
- そこからλ進むとmなので、Oからm進んだことになる
- m = aμなので、Oに到着する
- これらの考察を用いると、下記の値 λ, μが求まる
λの求め方
- 出会った位置と始点に速度1で動く人を置き、衝突するまで進める
- Oで衝突する
- ぶつかった時までにかかった時間がλである
μの求め方
- もう1度出会うまでの時間を数えればいい
- 出会った位置(O+d)からさらに継続して
- を続けると、μ秒後にまた出会うので、
- μ = 2回目に出会った時間 - 1回目に出会った時間
https://ja.wikipedia.org/wiki/%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E3%81%AE%E5%BE%AA%E7%92%B0%E6%A4%9C%E5%87%BA%E6%B3%95
Floyd's Tortoise and Hare
とも言われる。https://en.wikipedia.org/wiki/Cycle_detection