Question

【題目】將3333的方格表中毎個格染三種顏色之一,使得每種顏色的格的個數(shù)相等.若相鄰兩格的顏色不同,則稱其公共邊為“分隔邊".試求分隔邊條數(shù)的最小值。

Answer 1

【答案】56

【解析】

記分隔邊的條數(shù)為L。首先,將方格表按圖分成三個區(qū)域，分別染成三種顏色，粗線上均為分隔邊。將方格表的行從上至下依次記為,列從左至右依次記為。行中方格出現(xiàn)的顏色數(shù)記為,列中方格出現(xiàn)的顏色個數(shù)記為。三種顏色分別記為，對于一種顏色設(shè)為含有色方格的行數(shù)與列數(shù)之和。

定義 類似地定義.計(jì)算得到

，再證明，再證明対任意均有最后求出分隔邊條數(shù)的最小值.

記分隔邊的條數(shù)為L。首先,將方格表按圖分成三個區(qū)域，分別染成三種顏色，粗線上均為分隔邊。

此時,共有56條分隔邊，即L=56。

其次證明:L≥56。

將方格表的行從上至下依次記為,列從左至右依次記為。行中方格出現(xiàn)的顏色數(shù)記為,列中方格出現(xiàn)的顏色個數(shù)記為。三種顏色分別記為，對于一種顏色設(shè)為含有色方格的行數(shù)與列數(shù)之和。

定義

類似地定義.

所以

由于染色的格有個,設(shè)含有色方格的行有a個、列有b個,則色的方格一定在這a行和b列的交叉方格中。

從而,

所以 ①

由于在行中有種顏色的方格，于是,至少有條分隔邊。

類似地,在列中,至少有條分隔邊。

則 ②

③

下面分兩種情形討論。

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

不妨設(shè)有一行均為色則方格表的33列中均含有色的方格，又色方格有363個，故至少有11行含有色方格.于是， ④

由式①、③、④得

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

則対任意均有

從而，由式②知;

綜上，分割邊條數(shù)的最小值為56.