求分割邊條數(shù)的最小值．

192557

將5×5方格表中每個(gè)格染五種顏色之一，使得每種顏色的格的個(gè)數(shù)相同．若相鄰兩格的顏色不同，則稱(chēng)它們的公共邊為“分割邊”．求分割邊條數(shù)的最小值．

22568

先考慮5個(gè)正方形的邊界至少多長(zhǎng).
不連通時(shí)將其連通可以更省.
連通時(shí)若可用矩形axb覆蓋,顯然邊界至少2(a+b).
于是易知邊界最短是10(只有一種可能形狀),其它情況至少12(須嚴(yán)謹(jǐn)說(shuō)明).
但五個(gè)該形狀無(wú)法覆蓋5x5,故邊界總和至少10*4+12=52.

其中20在5x5邊界,不算,剩下的每條算了兩次,故所求最小為(52-20)/2=16.

以下為一種可行方案:
11122
11222
33344
33444
55555

210337

證：最小值=16，先證分割邊不能小于等于15。去除大方格外框，一共剩余40條邊，假如分割邊為15，又剩余25條邊，同色五個(gè)格子只有排成一種三格列貼著兩格列的形狀（設(shè)為形狀Q）才能使非分割邊達(dá)到最大值5，顯然五個(gè)形狀Q無(wú)法填入5乘5的大方格，同時(shí)分割邊可以是16（四個(gè)形狀Q在四個(gè)角，中間是五個(gè)格子組成的十字），證畢

166435

16吧

206035

最多40，最少20？

209484

20？