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)。
第 2/5 步：没有着法的中心方块
上一步下一步
S={(x,y):101−k≤x,y≤k},∣S∣=(2k−100)2S=\{(x,y):101-k\le x,y\le k\},\qquad|S|=(2k-100)^2
详细分析

对上一步的条件取否定，格子 (x,y)(x,y) 完全没有合法着法，恰好当 101−k≤x≤k101-k\le x\le k 且 101−k≤y≤k101-k\le y\le k 时成立；这是一个边长为 k−(101−k)+1=2k−100k-(101-k)+1=2k-100 的方块 SS，故 ∣S∣=(2k−100)2|S|=(2k-100)^2。SS 中的格子是孤立的，而其余 1002−(2k−100)2100^2-(2k-100)^2 个格子各自至少有一个着法。因为当 k≤99k\le99 时 101−k≥2101-k\ge2，起点 (1,1)(1,1) 永远不属于 SS。