MathLabs

第2题

考虑一个 100×100100\times100 的表格，将第 aa 行第 bb 列（1≤a,b≤1001\le a,b\le100）的格子等同于有序对 (a,b)(a,b)。设 kk 为满足 51≤k≤9951\le k\le99 的整数。一枚 kk-马是这样一种棋子：每次移动在竖直或水平方向走一格，在另一方向走 kk 格；即它从 (a,b)(a,b) 移动到 (c,d)(c,d)，使得 (∣a−c∣,∣b−d∣)(|a-c|,|b-d|) 等于 (1,k)(1,k) 或 (k,1)(k,1)。kk-马从格子 (1,1)(1,1) 出发并进行若干次移动。一个移动序列是指格子序列 (x0,y0)=(1,1),(x1,y1),…,(xn,yn)(x_0,y_0)=(1,1),(x_1,y_1),\ldots,(x_n,y_n)，使得对每个 i=1,2,…,ni=1,2,\ldots,n 都有 1≤xi,yi≤1001\le x_i,y_i\le100，且 kk-马能从 (xi−1,yi−1)(x_{i-1},y_{i-1}) 移动到 (xi,yi)(x_i,y_i)。此时每个格子 (xi,yi)(x_i,y_i) 称为可达的。对每个 kk，求可达格子的数目 L(k)L(k)。
第 3/5 步：两步使格子滑动2格
上一步下一步
(x,y)→(x±k,y−1)→(x,y−2)(x,y)\to(x\pm k,y-1)\to(x,y-2)
详细分析

对于都在 SS 之外的格子 (x,y)(x,y) 与 (x,y−2)(x,y-2)，两步路径 (x,y)→(x+k,y−1)→(x,y−2)(x,y)\to(x+k,y-1)\to(x,y-2) 或 (x,y)→(x−k,y−1)→(x,y−2)(x,y)\to(x-k,y-1)\to(x,y-2) 中必有一条留在棋盘内，因为 x≤100−kx\le100-k 或 x≥k+1x\ge k+1 使我们能选择 kk-跳跃的符号；对称地，(x,y)(x,y) 与 (x−2,y)(x-2,y) 也由交换坐标角色的两步路径相连。