Question

【题目】将3333的方格表中毎个格染三种颜色之一,使得每种颜色的格的个数相等.若相邻两格的颜色不同,则称其公共边为“分隔边".试求分隔边条数的最小值。

Answer 1

【答案】56

【解析】

记分隔边的条数为L。首先,将方格表按图分成三个区域，分别染成三种颜色，粗线上均为分隔边。将方格表的行从上至下依次记为,列从左至右依次记为。行中方格出现的颜色数记为,列中方格出现的颜色个数记为。三种颜色分别记为，对于一种颜色设为含有色方格的行数与列数之和。

定义 类似地定义.计算得到

，再证明，再证明対任意均有最后求出分隔边条数的最小值.

记分隔边的条数为L。首先,将方格表按图分成三个区域，分别染成三种颜色，粗线上均为分隔边。

此时,共有56条分隔边，即L=56。

其次证明:L≥56。

将方格表的行从上至下依次记为,列从左至右依次记为。行中方格出现的颜色数记为,列中方格出现的颜色个数记为。三种颜色分别记为，对于一种颜色设为含有色方格的行数与列数之和。

定义

类似地定义.

所以

由于染色的格有个,设含有色方格的行有a个、列有b个,则色的方格一定在这a行和b列的交叉方格中。

从而,

所以 ①

由于在行中有种颜色的方格，于是,至少有条分隔边。

类似地,在列中,至少有条分隔边。

则 ②

③

下面分两种情形讨论。

1.有一行或一列所有方格同色。

不妨设有一行均为色则方格表的33列中均含有色的方格，又色方格有363个，故至少有11行含有色方格.于是， ④

由式①、③、④得

(2)没有一行也没有一列的所有方格同色.

则対任意均有

从而，由式②知;

综上，分割边条数的最小值为56.