[數學]九宮格塗色問題

[數學]九宮格塗色問題

訪客 於 星期六 四月 19, 2008 4:59 pm


如題 用三種顏色塗九宮格 相鄰不同色 有幾種塗法

訪客

 

Re: [數學]九宮格塗色問題

G@ry 於 星期日 四月 20, 2008 10:11 pm


Anonymous 寫到:如題 用三種顏色塗九宮格 相鄰不同色 有幾種塗法

設三顏色依格數序為A,B,C (即顏色A為最多格的顏色)

{A,B,C}有以下6種組合:
{5,4,0}, {5,3,1}, {5,2,2}, {4,4,1}, {4,3,2}, {3,3,3}

而5,4,3格顏色的排列有以下情況:
5格:(1種) {圖5-1}
左鍵: 點擊縮放; 右鍵: 觀看原圖
4格:(3種) {圖4-1 - 4-3}
左鍵: 點擊縮放; 右鍵: 觀看原圖
3格:(6種) {圖3-1 - 3-3, 3-4 - 3-6}
左鍵: 點擊縮放; 右鍵: 觀看原圖
其他的情況為以上的反射對稱或是旋轉對稱組合


A=5

{5,4,0} - 很明顯,只有1個組合,就是 圖5-1 + 圖4-2

{5,3,1} - 剩下的4格中有1格為C,故有1種組合 (其餘的為對稱組合)

{5,2,2} - 剩下的4格中有2格各為B,C,同一顏色可以是(上+下) 或 非(上+下) 2種

小結:A=5 共有1+1+2=4種組合


A=4

{4,4,1} - 必定是 (圖4-1 / 圖4-3) + 圖4-2 + 剩下的一格為C  -- 2種

{4,3,2} - { 圖4-1 + (圖3-1 / 圖3-3) } 及  { 圖4-2 + (圖3-1 / 圖3-2 / 圖3-4) }   [註:圖4-3 無解] -- 2+3=5種

小結:A=4 共有2+5=7種組合


A=3

{3,3,3} - 由於所有顏色皆為3格,故只有一種顏色為中間格,故以此為A顏色,而A必定為 圖3-1 / 圖3-4,有以下組合:
  { 圖3-1 + 圖3-5 + 圖3-6 } 及 { 圖3-4 + 圖3-3 + 圖3-3 }**

小結:A=3 共有1種(組成各異)組合+1種(**組成含重覆)組合


組成各異的總共有 3! x ( 4+7+1 ) = 6x12 = 72種組合
組成含重覆的總共有 3!/2! x (1) = 3x1 = 3種組合
總共有72+3=75種總合
☆子 是也

G@ry
版 主
版 主
 
文章: 597
註冊時間: 2007-03-01
來自: 香港

J+W 於 星期一 三月 14, 2016 12:18 am


四同:     
藍:E   綠:BDHF    橘:AGCI

三同一異:
藍:E   綠:BDHF    橘:AGCI    粗體深綠:因為只有3色,所以只剩1選擇    紅:B,D,H,F擇一作為"一異"

二同二同:
(前面的BDHF、AGCI分類先省略)藍:BDHF顏色相同者不相對    綠:BDHF顏色相同者隔E相對    紅: (BD同,HF同)或(BF同,DH同) X 顏色分配=2 X 2 =4

二同二異:0




附暴力代码证实..
> s:=0:
> for a11 in{1,2,3}do
> for a12 in{1,2,3}minus{a11}do
> for a13 in{1,2,3}minus{a12}do
> for a21 in{1,2,3}minus{a11}do
> for a22 in{1,2,3}minus{a12,a21}do
> for a23 in{1,2,3}minus{a13,a22}do
> for a31 in{1,2,3}minus{a21}do
> for a32 in{1,2,3}minus{a22,a31}do
> for a33 in{1,2,3}minus{a23,a32}do
> s:=s+1 od od od od od od od od od:
> s;

                                 246

J+W
版 主
版 主
 
文章: 2161
註冊時間: 2003-12-30




機率及排列組合數學