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)。
第 1/5 步：何时一个格子有合法着法
上一步下一步
(x,y) has a legal move  ⟺  x≤100−k∨x≥k+1∨y≤100−k∨y≥k+1(x,y)\text{ has a legal move}\iff x\le100-k\lor x\ge k+1\lor y\le100-k\lor y\ge k+1
详细分析

一次 kk-马着法使一个坐标改变 ±1\pm1，另一个坐标改变 ±k\pm k，而 ±1\pm1 部分的符号总可以选取，使已经在 [1,100][1,100] 内的坐标仍留在范围内。因此 (x,y)(x,y) 至少有一个合法着法，当且仅当 kk 部分能作用于 xx 或 yy，即 x≤100−kx\le100-k 或 x≥k+1x\ge k+1 或 y≤100−ky\le100-k 或 y≥k+1y\ge k+1 成立。由于每步都可逆，同一条件也决定 (x,y)(x,y) 是否有任何进出的合法着法。