2017年高中数联二试第三题

将方格纸中每个小方格染三种颜色之一，使得每种颜色的小方格的个数相等，若相邻两个小方格的颜色不同，则称它们的公共边为“分隔边”。试求分隔边条数的最小值.

解：记三种颜色为，分隔边条数为.

设第行有种颜色，第列有种颜色.

对于颜色，将的矩阵中不含的行及列抽走，平移成连通无间隙的矩形，记为.

的行数记为，列数记为，则有

及

又

若，由

若存在，使

则.

不妨设，由

，同理，.

.

如图给出的染色方法，，故.