网格染色问题

jominzheng

是否可以将8×8网格的部分格子染黑，使得任意4×5或5×4的长方形中都恰有9个黑格？

.·.·.

■■■■■■■■
■□□□□■□□
□□□□□□□□
□□□□□□□□
□□□□□□□□
■■■■■■■■
■□□□□■□□
□□□□□□□□

第一列全黑
第二列第1,6个元素涂黑
第三到第五列不涂色
第六列同第一列
第七列同第二列
第八列同第三列

如果限制涂黑的正方形的个数或许还需要多想一想
不限制……
挨个涂就是了

hujunhua

楼上显然不正确，简单比划了一下，至少需要涂黑28格。应该还可以上升。

4×5和5×4的长方形共有(4×5)×2=40个呢。每个长方形中的黑格密度为9/20。
40个应该有一定的代表性了，所以平均来说，黑格数=64×(9/20)=28.8.

.·.·.

hujunhua 发表于 2020-7-13 09:15
楼上显然不正确，简单比划了一下，至少需要涂黑28格。应该还可以上升。

4×5和5×4的长方形共有(4×5)× ...

……在我回答问题的时候
好像只有4x5

mathe

1. 0    1    0    0    1    1    0    0
   
2. 1    0    1    0    0    1    1    0
   
3. 0    1    0    1    0    0    1    1
   
4. 1    0    0    1    1    0    0    0
   
5. 0    1    1    0    0    1    0    1
   
6. 0    0    1    0    1    0    1    0
   
7. 1    0    0    1    0    1    0    1
   
8. 1    1    0    0    1    0    1    0

复制代码

□ ■ □ □ ■ ■ □ □
■ □ ■ □ □ ■ ■ □
□ ■ □ ■ □ □ ■ ■
■ □ □ ■ ■ □ □ □
□ ■ ■ □ □ ■ □ ■
□ □ ■ □ ■ □ ■ □
■ □ □ ■ □ ■ □ ■
■ ■ □ □ ■ □ ■ □

hujunhua

我在3#说“最少要有28个黑格”有误，我的简单比划只能得出最少22格，应该不难上升到23格。
实际上求最值不简单，需要用单纯形法。Lingo的(0-1)规划应该是最方便的，可惜我不会，也没安装Lingo.
Mathematica对此编程好像不是很方便，因为它的domain貌似不能用Booleans。

hujunhua

等@mathe的文件发出来了，我倒是很容易用Mathematica滤掉旋转和对称重复。

我估计本原解不会超过16个。

mathe

去除对称后应该还有25个

mathe

fc.tgz (1.3 KB, 下载次数: 8)

2020-7-13 19:32 上传

点击文件名下载附件

原始数据和过滤后数据都在附件

hujunhua

对25个本原解进行了解剖，统计了黑格数，对称性，结果如下表所示。

黑格数	对称性				合计
	镜像	镜像+中心	旋转	无
27	5	0	0	0	5
28	2	1	1	4	8
29	7	0	0	1	8
30	0	4	0	0	4
合计	14	5	1	5	25
对称重复	14×4=56	5×2=10	1×2=2	5×8=40	108