MathLabs

第5問

Larry と Rob は1台の車を運転して Argovia から Zillis へ向かう2台のロボットである。両者は操舵を制御し、次の規則に従う。Larry は出発から ℓ\ell km 走るごとに90°左折し、Rob は rr km 走るごとに90°右折する。ただし ℓ\ell と rr は互いに素な正整数とする。両方の旋回が同時なら車は方向を変えずに進む。地面は平らで車は任意の方向に動けるとする。車は Argovia から Zillis に向いて出発する。Argovia からの距離に関係なく必ず Zillis に到達するのはどの組 (ℓ,r)(\ell,r) か。
ステップ 1/6: 旅を区間に分ける
前のステップ次のステップ
one section=ℓr km,Δθ≡ℓ−r(mod4)\text{one section}=\ell r\text{ km},\quad \Delta\theta\equiv\ell-r\pmod4
詳しい解説

長さ ℓr\ell r km の連続する区間を考える。1区間には r−1r-1 回の左折と ℓ−1\ell-1 回の右折があり、終点で同時に起こる旋回は相殺される。従って正味の回転は ℓ−r\ell-r の 44 を法とする剰余で決まり、向きを変えて同じ挙動が繰り返される。