棋子走遍无穷棋盘问题

abababa

给定一个平面直角坐标系上的所有整点和一个棋子，规定棋子初始位置在$(0,0)$，棋子移动一步可以到达边长为$m,n$的矩阵的对顶点。其中$m,n$是整数。问哪类$m,n$能保证棋子遍历棋盘的所有整点。
例如当$m=n=1$时，因为棋子落点$(p,q)$一定满足$p+q$是偶数，所以一定不能遍历。

kuing

那 m+n 为偶数都不行了
由于“马”是可以的，所以只要能跳出“日”就行
所以 m 为偶数 n=1 时一定行，因为它一定可以跳到 (2,1)，像这样：

m 为奇数 n=2 时也是：

其他的就不知道了

kuing

哦 m, n 必须互质呢，否则如果 gcd(m,n)=d>1，则落点的坐标之和也一定是 d 的倍数，所以不可能到达 (1,0)。

kuing

感觉就这样好像已经可以归纳了……

假设对于所有满足 min{m,n}<=N 且 m+n 为奇数且 m,n 互质的都可以走遍棋盘，2# 已经证明 N=1,2 成立，
则当 min{m,n}=N+1（且和奇数、互质）时，不妨设 m>n=N+1，按 2# 的走法：
(0,0)->(m,n)->(*,*)->(m-2n,n)->……->(m-2kn,n)，
那么只要证明一定存在 k 使 |m-2kn|<=N，就可以推出结论了（m-2kn 仍满足与 n 之和为奇数且互质……

kuing

回复 4# kuing

|x|<=N 的两端距离是 2N，而 {m-2kn} 的相邻两点距离为 2n，即 2N+2，
要使这样的 k 不存在，只能是 |m-2kn| 的最小值刚好为 n，于是 n 整除 m，与互质矛盾！
所以这样的 k 一定存在，搞定

abababa

回复 5# kuing

前面几楼都明白了，就是最后这个证明存在$k$，我还是看不懂。我想的是就是证明关于$k$的不等式$\abs{m-2kn}\le N=n-1$有解。然后把这个展开就是不等式
\[\frac{m-n+1}{2n}\le k \le\frac{m+n+1}{2n}\]
然后用带余除法，可以设$m=qn+r$，因为$\gcd(m,n)=1,m>n$，所以$1\le r<n$，不等式就变成了
\[\frac{q-1}{2}+\frac{r+1}{2n}\le k\le\frac{q+1}{2}+\frac{r-1}{2n}\]
到这里因为$0<\frac{r+1}{2n}\le 1,0<\frac{r-1}{2n}<1$，我知道$k=\frac{q+1}{2}$是一个解，但这必须在$q$是奇数时才行，下面怎么做还没想好。

kuing

回复 6# abababa

我 5# 是从直观角度看的。
或者这样讲吧，如果 |m-2kn| 的最小值 = n，那就得出 n 整除 m，与互质矛盾。
如果 |m-2kn| 的最小值 > n，那就是说 m-2kn 取不了 -n, -(n-1), ..., n-1, n 这连续 2n+1 个整数，但 {m-2kn} 是公差为 2n 的数列，也矛盾。

abababa

回复 7# kuing

虽然这个我仍然没看懂，但前面不等式的方法我已经找到解了，我重新写一下：不等式就是
\[\frac{m-n+1}{2n}\le k\le\frac{m+n-1}{2n}\]

因为$m>n$，不妨设$m=qn+r$，其中$0\le r<n, 1\le q$，而$\gcd(m,n)=1$，因此$1\le r<n$，于是不等式变为
\[\frac{(q-1)n+r+1}{2n} \le k \le \frac{(q+1)n+r-1}{2n}\]
就是
\[\frac{q-1}{2}+\frac{r+1}{2n} \le k \le \frac{q+1}{2}+\frac{r-1}{2n}\]

然后在这里重新放缩一下左边那部分：由$r+1\le n$得$\frac{r+1}{2n}\le\frac{1}{2}$，于是$0<\frac{r+1}{2n}\le\frac{1}{2}$，而$0\le\frac{r-1}{2n}<1$，所以只要不等式
\[\frac{q-1}{2}+\frac{1}{2}\le k\le\frac{q+1}{2}\]
有解，原不等式即有解。显然当$q$为奇数时，$k=\frac{q+1}{2}$即为解，当$q$为偶数时$k=\frac{q}{2}$即为解，所以这个不等式总有解。

kuing

7# 看不懂我也没辙了