2023 年山东预赛

思路

等差权重满足两邻权重之和等于两倍中间权重。若终态为排列，则平方和保持；恒等式 $\sum (x_k-k{)}^2=\sum x_k^2+\sum k^2-2\sum k{x}_k$ 给唯一性。

想法从哪来：局部操作的系数是相邻两端加一、中间减二，正好像等差数列的二阶差分为零。于是给每格一个沿行与列都呈一次变化的权重，数字乘权重的总和就会守恒。选择原来格内的编号作为权重，还让初态恰好达到同序排列的最大加权和。终态又是同一组整数的排列，因此守恒不是普通限制，而是迫使它继续取唯一最大值。也可把排序等号改写成平方差：初、终平方和相同，守恒使所有“新数减原编号”的平方和为零，便逐格相等。这说明不变量为什么要挑原编号，而不是只用总和。

操作是某一行或某一列上的二阶差分，因此与格子原编号成线性权重的加权和保持不变。最终数字仍是 $1$ 到 $100$ 的一个排列，再用排序不等式刻画加权和取最大值的唯一情形。