求分割边条数的最小值．

192557 · 发表于 2022-12-12 08:39:06

将5×5方格表中每个格染五种颜色之一，使得每种颜色的格的个数相同．若相邻两格的颜色不同，则称它们的公共边为“分割边”．求分割边条数的最小值．

22568 · 发表于 2023-1-21 14:27:35

先考虑5个正方形的边界至少多长.
不连通时将其连通可以更省.
连通时若可用矩形axb覆盖,显然边界至少2(a+b).
于是易知边界最短是10(只有一种可能形状),其它情况至少12(须严谨说明).
但五个该形状无法覆盖5x5,故边界总和至少10*4+12=52.

其中20在5x5边界,不算,剩下的每条算了两次,故所求最小为(52-20)/2=16.

以下为一种可行方案:
11122
11222
33344
33444
55555

210337 · 发表于 2022-12-12 18:31:53

证：最小值=16，先证分割边不能小于等于15。去除大方格外框，一共剩余40条边，假如分割边为15，又剩余25条边，同色五个格子只有排成一种三格列贴着两格列的形状（设为形状Q）才能使非分割边达到最大值5，显然五个形状Q无法填入5乘5的大方格，同时分割边可以是16（四个形状Q在四个角，中间是五个格子组成的十字），证毕

166435 · 发表于 2022-12-12 12:02:54

16吧

206035 · 发表于 2022-12-12 08:46:59

最多40，最少20？

209484 · 发表于 2022-12-12 09:01:22

20？

[数学趣题] 求分割边条数的最小值．