Project Euler 331
Project Euler 331
题目
Cross flips
\(N\times N\) disks are placed on a square game board. Each disk has a black side and white side.
At each turn, you may choose a disk and flip all the disks in the same row and the same column as this disk: thus \(2\times N-1\) disks are flipped. The game ends when all disks show their white side. The following example shows a game on a \(5\times5\) board.
It can be proven that \(3\) is the minimal number of turns to finish this game.
The bottom left disk on the \(N\times N\) board has coordinates \((0,0)\);
the bottom right disk has coordinates \((N-1,0)\) and the top left disk has coordinates \((0,N-1)\).
Let \(C_N\) be the following configuration of a board with \(N\times N\) disks:
A disk at \((x,y)\) satisfying \(N-1 \le \sqrt{x^2+y^2} \lt N\), shows its black side; otherwise, it shows its white side. \(C_5\) is shown above.
Let \(T(N)\) be the minimal number of turns to finish a game starting from configuration \(C_N\) or \(0\) if configuration \(C_N\) is unsolvable.
We have shown that \(T(5)=3\). You are also given that \(T(10)=29\) and \(T(1 000)=395253\).
Find \(\sum \limits_{i = 3}^{31} {T(2^i - i)}\).
解决方案
把每个格子的颜色用 \(0/1\) 表示（白 \(0\)，黑 \(1\)），所有格子组成向量空间 \(\mathbb F_2^{N^2}\)。
用 \(X_{ij}\in\{0,1\}\) 表示是否在 \((i,j)\) 按一次（按两次等于没按，所以只需 \(0/1\)）。设初始棋盘为矩阵 \(B\)，操作集合为矩阵 \(X\)，最终棋盘为 \(B+\Phi(X)\)（加法在 \(\mathbb F_2\) 中即异或）。要清空棋盘等价于\(\Phi(X)=B.\)
关键是写出线性算子 \(\Phi\)。按一次 \((i,j)\) 会翻转整行 \(i\) 与整列 \(j\)，在 \(\mathbb F_2\) 下“翻转”就是加 \(1\)。因此对任意 \(X\)，令 \[R_i=\sum_{k=0}^{N-1}X_{ik}\bmod 2, C_j=\sum_{k=0}^{N-1}X_{kj}\bmod 2.\] 那么 \((i,j)\) 这个格子被翻转的次数，正是“本格子是否被按”加上“本行按的个数”加上“本列按的个数”（交点在行与列里被算两次，在 \(\mathbb F_2\) 中自动抵消，最终仍留下 \(X_{ij}\) 这一项）。于是得到非常核心的公式： \[(\Phi(X))_{ij}=(X_{ij}+R_i+C_j)\bmod 2 \tag{1}\]
接下来研究算子平方 \(\Phi(\Phi(X))\)。令 \(Y=\Phi(X)\)，其行列和为\(\displaystyle{R'_i=\sum_{j=0}^{N-1} Y_{ij} \bmod 2, C'_j=\sum_{i=0}^{N-1} Y_{ij} \bmod 2.}\)
由 \((1)\) 有
\[ R'_i=\sum_j\left(X_{ij}+R_i+C_j\right)=\underbrace{\sum_j X_{ij}}_{R_i}+\underbrace{\sum_j R_i}_{N R_i}+\underbrace{\sum_j C_j}_{S}, \]
其中\(\displaystyle{S=\sum_{i,j}X_{ij}\bmod 2}\)是 \(X\) 中 \(1\) 的总个数的奇偶性。于是\(R'_i=((1+N)R_i+S)\bmod 2.\)同理 \(C'_j=((1+N)C_j+S)\bmod 2.\)
再套一次 \((1)\)：
\[ (\Phi^2(X))_{ij} =Y_{ij}+R'_i+C'_j =\bigl(X_{ij}+R_i+C_j\bigr)+R'_i+C'_j. \]
若 \(N\) 偶数，则 \(1+N\equiv 1\pmod 2\)，所以\(R'_i=R_i+S, C'_j=C_j+S.\)代回去：\((\Phi^2(X))_{ij}=X_{ij}+R_i+C_j+(R_i+S)+(C_j+S)=X_{ij}.\)
因此，当\(N\)为偶数时，有
\[\Phi^2=\mathrm{Id} \tag{2}\]
其中\(\mathrm{Id}\)是指恒等映射。因此可直接推出：\(\Phi\) 可逆且 \(\Phi^{-1}=\Phi\)。所以方程 \(\Phi(X)=B\) 的唯一解是
\[X=\Phi(B) \tag{3}\]
这点非常强：偶数阶时解不仅存在且唯一，而且就是把同一个算子再作用回去。
若 \(N\) 奇数，则 \(1+N\equiv 0\pmod 2\)，于是\(R'_i=S, C'_j=S.\)代回去：\((\Phi^2(X))_{ij}=X_{ij}+R_i+C_j+S+S=X_{ij}+R_i+C_j=(\Phi(X))_{ij}.\)
所以，当\(N\)为奇数时，有
\[\Phi^2=\Phi\tag{4}\]
这就是“奇数阶出现不可解约束”的根源：\(\Phi\) 不再是可逆算子，而是一个投影（idempotent）。于是对任何可达局面 \(B=\Phi(X)\)，必满足 \(\Phi(B)=\Phi(\Phi(X))=\Phi(X)=B.\)也就是说，奇数阶可解的充要条件为：
\[\Phi(B)=B \tag{5}\]
把 \((1)\) 套在 \(B\) 上，令\(\displaystyle{r_i=\sum_j B_{ij}\bmod 2, c_j=\sum_i B_{ij}\bmod 2,}\)则\((\Phi(B))_{ij}=B_{ij}+r_i+c_j.\)因此 \(\Phi(B)=B\) 等价于对所有 \(i,j\) 都有\(r_i+c_j=0\bmod 2.\)也就是所有行奇偶必须相同、所有列奇偶也必须相同，并且两者相同：
\[\exists t\in\{0,1\}\text{s.t.}\forall i,r_i=t;\forall j,c_j=t \tag{6}\]
这就是奇数阶的可解的必要条件——它是由 \((4)\) 导致的代数必然性。
回到本题的棋盘\(C_N\)。本题初始 \(B\) 为圆环格点：\((N-1)^2\le x^2+y^2 < N^2.\)
先看最底行 \(y=0\)：黑格满足\((N-1)^2\le x^2 < N^2.\)因为 \(0\le x\le N-1\)，唯一满足的是 \(x=N-1\)，所以底行黑格数为 \(1\)（奇数）。因此若 \(N\) 为奇数且可解，根据 \((6)\) 必须取 \(t=1\)，也就是每一行都必须有奇数个黑格。
现在取题目真正会遇到的奇数尺寸：\(N=2^i-i\)，其中\(i\)是奇数。
考虑最顶行 \(y=N-1\)：黑格条件变为\((N-1)^2\le x^2+(N-1)^2 < N^2\iff x^2 < N^2-(N-1)^2=2N-1.\)
所以顶行黑格个数是
\[ b_{\text{top}}=\left|{x\in\mathbb Z:0\le x\le N-1,x^2<2N-1}\right|=\left\lceil\sqrt{2N-1}\right\rceil \tag{7} \]
将 \(N=2^i-i\) 代入：\(2N-1=2^{i+1}-2i-1.\)令\(a=2^{\frac{i+1}{2}}, a^2=2^{i+1}\)，这是因为\(i\)是奇数，需要保持指数为整数。则 \(2N-1=a^2-(2i+1)<a^2 \Rightarrow\sqrt{2N-1}<a \Rightarrow b_{\text{top}}\le a.\)
再证明 \(\sqrt{2N-1}>a-1\)（从而天花板恰为 \(a\)）。只需证\((a-1)^2<2N-1.\)展开：\((a-1)^2=a^2-2a+1=2^{i+1}-2^{\frac{i+3}{2}}+1.\)因此 \((a-1)^2<2N-1\) 等价于\(2^{\frac{i+3}{2}}>2i+2.\)
当 \(i\ge 5\) 时，左边指数增长、右边线性增长，且基例 \(i=5\) 时\(2^{\frac{8}{2}}=16>12,\)所以对所有奇数 \(i\ge 5\) 成立。于是 \((a-1)^2<2N-1<a^2 \Rightarrow\left\lceil\sqrt{2N-1}\right\rceil=a.\)
结合 \((7)\)，得到结论：当\(i\ge 5\)且为奇数时，\(b_{\text{top}}=2^{\frac{i+1}{2}}\)为偶数但底行黑格数为 \(1\)（奇数），因此“所有行都奇数”被顶行直接打破，故不可解。
结论：
对题目范围 \(i=3,5,7,\dots,31\)（奇数）：
- \(i=3\) 时 \(N=5\)：可解，题目给出 \(T(5)=3\)；
- 所有 \(i\ge 5\)：由上述结论的顶行偶数黑格，必不可解，故 \(T(N)=0\)。
偶数阶时由 \((3)\) 唯一解为 \(X=\Phi(B)\)。写成分量形式：令 \(B\) 的行列奇偶为\(\displaystyle{r_i=\sum_j B_{ij}\bmod 2, c_j=\sum_i B_{ij}\bmod 2,}\)则由 \((1)\)得：\(X_{ij}=(B_{ij}+r_i+c_j)\bmod 2.\)这意味着：
- 若 \(r_i=c_j\)，则 \(X_{ij}=B_{ij}\)；
- 若 \(r_i\ne c_j\)，则 \(X_{ij}=1-B_{ij}\)。
最少步数就是 \(X\) 中 \(1\) 的个数。将其拆开可以整理成非常实用的形式。记\(s=\#\{i:r_i=1\}, t=\#\{j:c_j=1\}.\)
则满足 \(r_i\ne c_j\) 的格子总数为\(s(N-t)+(N-s)t.\)再把黑格的“加一/减一”修正并入，可写为
\[ \boxed{T(N)=s(N-t)+(N-s)t+\sum_{(x,y)\in\mathcal B}\bigl(1-2\cdot \mathbf{1}\{r_x\ne c_y\}\bigr)} \tag{9} \]
其中 \(\mathcal B\) 为黑格集合，\(\mathbf{1}\{\cdot\}\) 为指示函数。
本题圆环满足 \(B_{xy}=B_{yx}\)，故每行黑格数等于对应列黑格数，从而\(r_i=c_i, s=t.\)于是 \((9)\) 简化为
\[ \boxed{T(N)=2s(N-s)+\sum_{(x,y)\in\mathcal B}\begin{cases} +1,& r_x=r_y,\\ -1,& r_x\ne r_y. \end{cases}} \tag{10} \]
所以偶数 \(N\) 的任务变成两件事：
- 统计 \(s\)：有多少个行（等价列）黑格数为奇数；
- 统计黑格上的符号和：每个黑格看 \(r_x\) 与 \(r_y\) 是否相等，等则 \(+1\)，不等则 \(-1\)。
如图所示，是\(C_{2^6-6}\)的棋盘：
定义区间\(I=[(N-1)^2,N^2).\)任意黑格 \((x,y)\) 满足 \(x^2+y^2\in I\)。注意到 \(I\) 的长度为\(|I|=N^2-(N-1)^2=2N-1.\)
若某个黑格同时存在左邻 \((x-1,y)\) 与上邻 \((x,y+1)\) 也为黑格，则两者对应的平方半径之差为\((x^2+(y+1)^2)-((x-1)^2+y^2)=2(x+y).\)
但这两者都落在区间 \(I\) 中，故差值必须小于 \(|I|\)，即\(2(x+y)\le 2N-2\Rightarrow x+y\le N-1.\)
另一方面，由 \(x^2+y^2\ge (N-1)^2\) 且 \(x,y\ge 0\) 有\((x+y)^2\ge x^2+y^2\ge (N-1)^2\Rightarrow x+y\ge N-1.\)
合并得 \(x+y=N-1\)。但当 \(x+y=N-1\) 时，\(x^2+y^2\le (x+y)^2=(N-1)^2,\)要达到 \(\ge (N-1)^2\) 只能取等号，而等号仅在 \(xy=0\) 时成立，即只能是端点 \((0,N-1)\) 或 \((N-1,0)\)。在端点处显然不可能同时有“左邻”和“上邻”都在棋盘内成为黑格。
因此得到结论：对任意非端点黑格 \((x,y)\)，左邻与上邻不可能同时为黑格。所以沿着“能走就向左，否则能走就向上，否则走对角”的规则，路径是确定的，并且会恰好遍历每一个黑格一次。
这使得可以用一次遍历完成所有统计。
遍历顺序从 \((N-1,0)\) 走到 \((0,N-1)\)，每步只可能是
- 上：\((x,y)\to(x-1,y)\)
- 左：\((x,y)\to(x,y+1)\)
- 对角线：\((x,y)\to(x-1,y+1)\)
在遍历过程中：
- “当前行 \(y\) 的黑格个数奇偶”用变量维护（每遇到一个黑格异或 \(1\)）；
- “当前列 \(x\) 的黑格个数奇偶”用变量维护。
当发生向上或者是对角线方向时时，意味着当前行结束，此时行奇偶就是该行的 \(r_y\)，于是可以把它计入 \(s\)。
难点在于计算\(\displaystyle{\sum_{(x,y)\in\mathcal B}(\pm 1)}\)。其中符号取决于该黑格所在行与列的最终奇偶（即 \(r_x,r_y\)）。在遍历过程中，有时一边的奇偶已确定、另一边还没确定，需要“暂存贡献”。但由于路径结构的特殊性：
- 当向上走（结束一行）时，除了当前格子所在的那一列外，该行中其它黑格所在的列都已经被完全走完（列奇偶已知）；
- 当向左走（结束一列）时，除了当前格子所在的那一行外，该列中其它黑格所在的行都已经被完全走完（行奇偶已知）。
因此只需要常数个“待结算计数”即可：
- 当前行中，列奇偶已知的黑格数，按“列奇偶为 \(0/1\)”分类；
- 当前列中，行奇偶已知的黑格数，按“行奇偶为 \(0/1\)”分类。
当一行结束时（得到 \(r_y\)），可以立刻结算\(\text{same}-\text{diff}\)（同奇偶贡献 \(+1\)，不同奇偶贡献 \(-1\)），并清空该行的待结算计数。当一列结束时（得到对应的列奇偶），同理结算并清空该列的待结算计数。
最后用 \((10)\)：
\[T(N)=2s(N-s)+\text{corr}.\]
代码
1 |
|