每日一题[3332]递推构造

已知布尔数集 $A=\{0,1\}$，$p$ 为大于 $1$ 的奇数，考虑以下定义：

定义一    称由 $p^2$ 个属于集合 $A$ 的数构成的 $p$ 行 $p$ 列的数表为 $p$ 型布尔数表，记为 $\Gamma_p$，其第 $i$ 行第 $j$ 列的数被记为 $\Gamma_p(i,j)$，$(i,j)$ 被称为该数的坐标；

定义二    称满足 $\{|a-c|-1,|b-d|-1\}=A$ 的坐标 $(a,b),(c,d)$ 互为 $H$ 交换坐标；

定义三    若对于任意位于 $(x,y)$ 的 $H$ 交换坐标的数 $x_0$，都有 $x_0\cdot\Gamma_p(x,y)=0$，则称坐标 $(x,y)$ 是单次 $H$ 完备的．称所有坐标都是单次 $H$ 完备的的数表 $\Gamma_p$ 为 $H$ 数表．

1、直接写出每行每列都只有一个 $1$ 的所有 $H$ 数表 $\Gamma_3$；

2、记 $S_p$ 为 $H$ 数表 $\Gamma_p$ 中所有数的和；

① 写出 $S_3$ 和 $S_5$ 的最大值并证明；

② 试猜想 $S_p$ 的最大值与 $p$ 的关系式，并证明你的猜想．

解析

1、互为 $H$ 交换坐标即在数表中横纵坐标分别相差 $1,2$ 或者 $2,1$，类似于中国象棋中的马的走法．根据题意，互为 $H$ 交换坐标中的一对坐标中的数至少有 $1$ 个为 $0$．将 $\Gamma_3$ 中的坐标连成环： $$(1,1)\to (2,3)\to (3,1)\to (1,2)\to (3,3)\to (2,1)\to (1,3)\to (3,2)\to (1,1),$$ 则此环中相邻的位置不能同时为 $1$，又每行每列都只有 $1$，则 $(1,1)$ 位置的数确定后其余各数都确定，从而满足条件的所有 $H$ 数表 $\Gamma_3$ 为 $$\begin{bmatrix}1&0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix},\begin{bmatrix}0&0&1\\ 0&1&0\\ 1&0&0 \end{bmatrix}.$$

2、$S_p$ 的最大值为 $\dfrac 12(p^2+1)$，证明如下．

构造    对 $(i,j)$ 位置，若 $i+j$ 为偶数，则填 $1$；若 $i+j$ 为奇数，则填 $0$，这样就得到了 $S_p=\dfrac 12(p^2+1)$ 的例子 $$\Gamma_p=\begin{bmatrix}1 & 0 & 1 & 0 &\cdots & 1\\0 & 1 & 0 & 1 &\cdots & 0\\1 & 0 & 1 & 0 &\cdots & 1\\0 & 1 & 0 & 1 &\cdots & 0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots\\1 & 0 & 1 & 0 &\cdots & 1\end{bmatrix}.$$

论证    对于 $p=3,5$ 的情形，如图配为 $\dfrac{p^2-1}2$ 对，每对格子中至多有 $1$ 个 $1$，因此 $S_p$ 的最大值为 $\dfrac{p^2-1}2+1=\dfrac{p^2+1}2$．

对于 $p\geqslant 7$ 的情形，考虑递推构造．如图，将方阵分割为 $4$ 个区域，分别进行配对： 左下为 $1\sim (p-4)$ 行到 $1\sim (p-4)$ 列的 $(p-4)\times (p-4)$ 方阵，由递推即可配为 $\dfrac{(p-4)^2-1}2$ 对； 右上为 $5\times 5$ 去掉左下角的方阵，根据对 $\Gamma_5$ 的配对方案，可配为 $12$ 对； 剩下的两个区域均为一边为 $4$ 格，另一边为偶数 $(p-5)$ 格的矩形区域，可以如图配对．

综上所述，方阵可以配为 $\dfrac{p^2-1}2$ 对，因此 $S_p$ 的最大值为 $\dfrac{p^2+1}2$．

这样就得到了 ① $S_3=5$，$S_5=13$；② $S_p=\dfrac{p^2+1}2$．