這是2017年全國高中聯賽2試題第三題。我們注意到2007，2009，2011，2017這四年都是方陣問題，這意味著組合題目在2007-2018這些年中佔了組合題目的1/3，要充分引起高聯考生的重視.我感覺一些學校的教練老師對此重視不夠，需要特別加強，比題海硬算不等式好得的多。這裡發出來供老師同學參考。
題目
將33x33的方格紙中的每個小方格染三種顏色之一，使得每種顏色的小方格個數相同，若相鄰的小方格的顏色不同，則稱它們的公共邊為“分隔邊”，試求分隔邊條數的最小值。
解答
設三種顏色為k=1，2，3.對於6x1的方格情形，如果3種顏色中，相同的顏色放到一起，分隔邊會少，這是因為從上到下掃描方格，跳過相鄰的不同色的方格，分隔邊就增加一條。對於3x3的方格的情形，圖2的兩種情況分隔邊最少，都是6。
圖1.a 圖1.b
但是對於9x9方格的情形，圖2.b的情形比圖2a的情形分隔邊更少。前者為18，後者只有9+6+1=17.
圖2.a
圖2.b
對33x33的方格，我們猜測下面的塗色方式，分隔邊數最少。
合計為33+22+1=56條。
下面證明這個猜測。
對於一行來說，計數豎直方向的分隔邊數，可以由左向右掃描，設初始的分隔邊數為0.發現顏色變化了，分隔邊數加1。對一列計數水平分隔邊數，只需從上到下掃描。當不存在一行或者一列是同一個顏色時，每個行至少貢獻一個豎直分隔邊，一個列至少貢獻一個水平分隔邊，所以合計至少有33+33=66個分隔邊>56.因此至少有一個同色行或列。
令
圖4是k=2的一個示意圖，如果有顏色2方格的行編號最小是lmin，最大是lmax；列編號最小是cmin，最大是cmax，則所有的顏色為2的方格框在小實線矩形內。
圖4
由於我們認為分隔邊數出現分隔邊最少的時候，每行，每列顏色主要是發生了一次變化，最多是多發生兩次變化，只需按如下方式估計就能取到足夠好的分隔邊總數下界了。
行列含有的顏色數，可以用以下兩式記錄:
總的分隔線邊數滿足：
因此，總計分隔線最少為56.
評論：
此題也是個染色問題，採用的手法是經典的以色數為計數對象的手法法，東歐俄羅斯風格題目。標答基本上是不錯的，此處只是略微做了修改，採用啟發式分析，目的是為了教學，基本精神與標答一致。
閱讀更多 放手家長 的文章
