每日一题[2640]开关阵列

如图为一个开关阵列，每个开关只有“开”和“关”两种状态，按其中一个开关 $1$ 次，将导致自身和所有相邻的开关改变状态．例如，按 $(2,2)$ 将导致 $(1,2),(2,1),(2,2),(2,3),(3,2)$ 改变状态．如果要求只改变 $(1,1)$ 的状态，则需按开关的最少次数为_______．

$$\begin{array}{|c|c|c|}\hline (1,1)&(1,2)&(1,3)\\ \hline (2,1)&(2,2)&(2,3)\\ \hline (3,1)&(3,2)&(3,3)\\ \hline\end{array}$$

答案    $5$．

解析    可以将按动开关看作将某些格子染色，然后分别统计 $9$ 个格子自己以及相邻格子中的染色格数量（记数），题意即只有左上角的格子中数量为奇数，其他格子均为偶数，如图，为符合题意的方案，此时按开关次数（即染色格子总数）为 $5$．

记四个角的格为角格，每条边中间的格为边格，最中心的格为心格，分别统计三类格子的记数之和 $A,B,C$，应该为奇、偶、偶．每染一个角格，只改变 $A$ 的奇偶；每染一个边格，同时改变 $B,C$ 的奇偶；每染一个心格，只改变 $C$ 的奇偶．因此角格共染奇数格，边格共染偶数格，心格不染（心格只有 $1$ 个，染偶数格等于不染）．

容易证明，若某个格子记数为 $0$，那么不符合题意（按这个格是心格，角格，边格分类讨论即可），这样 $9$ 个格子记数之和至少为 $2\cdot 8+1=17$，而每个角格染色记数增加 $3$，每个边格染色记数增加 $4$，因此至少要染 $5$ 个格子，且只能是 $3$ 个角格 $2$ 个边格． 综上所述，需按开关的最少次数为 $5$．