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)。
第 5/5 步：奇偶不变量决定答案
上一步下一步
L(k)=1002−(2k−100)2 (k even),L(k)=12(1002−(2k−100)2) (k odd)L(k)=100^2-(2k-100)^2\ (k\text{ even}),\qquad L(k)=\tfrac12\big(100^2-(2k-100)^2\big)\ (k\text{ odd})
详细分析

一次 kk-马着法使 x+yx+y 改变 ±(k−1)\pm(k-1) 或 ±(k+1)\pm(k+1)，两者与 k+1k+1 有相同的奇偶性。若 kk 为奇数，k+1k+1 为偶数，故 x+y mod 2x+y\bmod2 是不变量，只有 SS 之外与 (1,1)(1,1) 同色的 (1002−(2k−100)2)/2\big(100^2-(2k-100)^2\big)/2 个格子可达。若 kk 为偶数，k+1k+1 为奇数，故单单一步已能到达异色格子，对该颜色再用上一步的结论可知 SS 之外其余格子也都可达；因此 SS 之外全部 1002−(2k−100)2100^2-(2k-100)^2 个格子都可达。