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) か。
ステップ 2/6: 異なる剰余を排除する
前のステップ次のステップ
ℓ−r≡2,1,3(mod4)⟹bounded path\ell-r\equiv2,1,3\pmod4\Longrightarrow\text{bounded path}
詳しい解説

ℓ−r≡2(mod4)\ell-r\equiv2\pmod4 なら1区間後に向きが反転し、2区間目で出発点へ戻る。ℓ−r≡1\ell-r\equiv1 または 3(mod4)3\pmod4 なら4方向を巡り、4区間後に出発点へ戻る。いずれも軌道は有界なので、任意に遠い目的地には到達できない。