MathLabs

第5题

Larry 和 Rob 是乘一辆车从 Argovia 前往 Zillis 的两个机器人。两者都能控制方向盘并按如下算法驾驶：Larry 从出发起每行驶 ℓ\ell 千米左转 90°；Rob 每行驶 rr 千米右转 90°，其中 ℓ\ell 和 rr 是互素正整数。若两次转弯同时发生，车辆继续行驶而不改变方向。设地面平坦且车辆可向任意方向行驶。车辆从 Argovia 出发时朝向 Zillis。对于哪些数对 (ℓ,r)(\ell,r)，无论两地相距多远，车辆都必定到达 Zillis？
第 4/6 步：计算余数为 1 时的位移
上一步下一步
∑k=0ℓr−1mk=∑a=0ℓ−1(−i)a∑b=0r−1ib=1(ℓ≡r≡1(mod4))\sum_{k=0}^{\ell r-1}m_k=\sum_{a=0}^{\ell-1}(-i)^a\sum_{b=0}^{r-1}i^b=1\quad(\ell\equiv r\equiv1\pmod4)
详细分析

因 ell,r 互素，中国剩余定理说明 (a_k,b_k) 双射遍历所有数对，故位移和可分解。若 ell≡r≡1 (mod 4)，两个等比和均为 1，所以一段位移为向东 1 千米。