题面
现有 \((3k+1)\times(3k+2)\) 大小的网格, 需要在每个网格中填写 \(0,1,2\) 中的一个数字, 使得网格中任意一行数字之和、任意一列数字之和均为 \(3\) 的倍数. 求网格中 \(1\) 的数量的最大值.
原题目 \(k=668\), 我们可以扩展至任意 \(\newcommand{\mbb}{\mathbb}k\in\mbb N\).
题解
由于 \(2\equiv-1\pmod3\), 故图中的所有 \(2\) 和 \(-1\) 互换仍满足要求. 而对图中所有元素取相反数后仍满足要求. 故求图中 \(1\) 的数量的最大值等价于求图中 \(2\) 的数量的最大值.
对于图 \(\newcommand{\mfk}{\mathfrak}\mfk D\) 记图中数字之和为 \(S(\mfk D)\). 图中 \(2\) 的数量为 \(C(\mfk D)\).
记 \(\newcommand{\bgf}{\displaystyle}A:=\bgf\max_{\mfk D} S(\mfk D)\), \(\bgf G:=\max_{\mfk D}C(\mfk D)\). \(G\) 即为所求.
对一列元素全填 \(2\), 此列的数字之和为 \(2(3k+1)\). 故一列的数字之和不超过 \(2(3k+1)\). 而一列的数字之和需为 \(3\) 的倍数, 故一列的数字之和不超过 \(6k\). 故 \(A\le 6k(3k+2)\).
现考虑一行的数字之和. 一行的数字全填 \(2\), 此时的数字之和为 \(2(3k+2)\). 故一行的数字之和不超过 \(2(3k+2)\). 而一行的数字之和需为 \(3\) 的倍数, 故一行的数字之和不超过 \(6k+3\).
现在考虑任意一行的数字之和至少为 \(6k\) 的图, 称作均匀图. 均匀图只有以下两类行:
- 数字之和和为 \(6k+3\). 这一行有且仅有 \(3k+1\) 个 \(2\) 和 \(1\) 个 \(1\). (I 类行)
- 数字之和为 \(6k\). 这一行最多有 \(3k\) 个 \(2\). (II 类行)
由于 \(A\le 6k(3k+2)\), 设图中有 \(x\) 个 I 类行, 则有不等式: \[ (6k+3)x+6k(3k+1-x)\le A\le6k(3k+2) \] 整理得: \[ (6k+3)x-6kx\le6k \] 解得: \[ x\le2k \] 若存在均匀图 \(\mfk B\), 其有 \(2k\) 个 I 类行, 其他行为 II 类行, 则称 \(\mfk B\) 为和最大图, 有: \[ S(\mfk B)=6k(3k+2) \]
\[ C(\mfk B)\le2k(3k+1)+(k+1)3k=3k(3k+1)+2k\tag1 \]
\((1)\) 式取等号的条件为, \(\mfk B\) 中每个 II 类行都恰好有 \(3k\) 个 \(2\) 和 \(2\) 个 \(0\). 考虑 \((1)\) 式满足取等条件的和最大图 \(\mfk A\), 称做和量最大图. 直觉上, 若和量最大图 \(\mfk A\) 存在, 则 \(C(\mfk A)=G\).
若 \(\mfk A\) 存在, 则根据行的限制条件, \(\mfk A\) 中有 \(2(k+1)\) 个 \(0\) 和 \(2k\) 个 \(1\), 其余位置全部为 \(2\). 再考虑 \(\mfk A\) 的列的限制条件: 由于 \(S(\mfk A)=A\), 故任意一列的和均为为 \(6k\), 则一列有两种情况:
- 有 \(3k\) 个 \(2\) 和 \(1\) 个 \(0\). (I 类列)
- 有 \(3k-1\) 个 \(2\) 和 \(2\) 个 \(1\). (II 类列)
根据行的限制, 可知 \(0\) 和 \(1\) 的数量对应 \(2(k+1)\) 个 I 类列和 \(k\) 个 II 类列. 由于 \(2(k+1)+k=3k+2\), 即 I 类列的数量和 II 类列的数量之和恰好等于图的列数, 行的限制和列的限制不矛盾, 可以构造出 \(\mfk A\). 构造 \(\mfk A\) 的方法为: \(2k\) 个 I 类行分为 \(k\) 对, 每对 I 类行的 \(1\) 放在同一个 II 类列; \(k+1\) 个 II 类行的 \(2(k+1)\) 个 \(0\) 放在 \(2(k+1)\) 个 I 类列即可. 一个 \(\mfk A\) 的构造为: \[ \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}}\mfk A=\pmat{ 1\\ 1\\ &1\\ &1\\ &&\ddots\\ &&&1\\ &&&1\\ &&&&0&0\\ &&&&&&0&0\\ &&&&&&&&\ddots\\ &&&&&&&&&0&0 } \] 其中空白位置均为 \(2\).
由于和量最大图确实存在, 根据 \((1)\) 式有 \(G\ge C(\mfk A)=3k(3k+1)+2k\). 现在尝试证明 \(C(\mfk A)=G\). 即对于任意一个不是和量最大图的图 \(\mfk D\), \(C(\mfk D)\le C(\mfk A)\).
若 \(S(\mfk D)<6k(3k+1)\), 则 \(C(\mfk D)<S(\mfk D)/2<C(\mfk A)\). 否则, 设 \(S(\mfk D)=6k(3k+1)+3s\), 且 \(\mfk D\) 中有 \(x\) 个行数字之和为奇数. 记第 \(i\) 行的数字之和为 \(L(i)\), 则有: \[ \newcommand{\algn}[1]{\begin{aligned} #1 \end{aligned}}\algn{6k(3k+1)+3s=S(\mfk D)&=\sum_{L(i)\text{ is odd}}L(i)+\sum_{L(i)\text{ is even}}L(i)\\&\le\sum_{L(i)\text{ is odd}}(6k+3)+\sum_{L(i)\text{ is even}}6k\\&=(6k+3)x+6k(3k+1-x)\\&=6k(3k+1)+3x} \] 故 \(s\) 确定时, \(x\) 有下限: \[ s\le x \] 而 \(s\) 的上限为: \[ s=\frac{S(\mfk D)-6k(3k+1)}3\le\frac{A-6k(3k+1)}{2}=2k \]
最后可得 \[ \algn{C(\mfk D)&\le\sum_{L(i)\text{ is odd}}\frac{L(i)-1}2+\sum_{L(i)\text{ is even}}\frac{L(i)}2\\ &=\frac12\sum_iL(i)-\frac x2\\&=\frac{S(\mfk D)-x}2\\&=\frac{6k(3k+1)+3s-x}2\\&\le3k(3k+1)+s\\&\le3k(3k+1)+2k=C(\mfk A)} \]
故可知结论:
\[ G=C(\mfk A)=3k(3k+1)+2k \]