网格染色问题
是否可以将8×8网格的部分格子染黑，使得任意4×5或5×4的长方形中都恰有9个黑格？好问题；并深挖背后的本质■■■■■■■■
■□□□□■□□
□□□□□□□□
□□□□□□□□
□□□□□□□□
■■■■■■■■
■□□□□■□□
□□□□□□□□
第一列全黑
第二列第1,6个元素涂黑
第三到第五列不涂色
第六列同第一列
第七列同第二列
第八列同第三列
如果限制涂黑的正方形的个数或许还需要多想一想
不限制……
挨个涂就是了
楼上显然不正确，简单比划了一下，至少需要涂黑28格。应该还可以上升。
4×5和5×4的长方形共有(4×5)×2=40个呢。每个长方形中的黑格密度为9/20。
40个应该有一定的代表性了，所以平均来说，黑格数=64×(9/20)=28.8. 本帖最后由 .·.·. 于 2020-7-13 12:39 编辑
hujunhua 发表于 2020-7-13 09:15
楼上显然不正确，简单比划了一下，至少需要涂黑28格。应该还可以上升。
4×5和5×4的长方形共有(4×5)× ...
……在我回答问题的时候
好像只有4x5 0 1 0 0 1 1 0 0
1 0 1 0 0 1 1 0
0 1 0 1 0 0 1 1
1 0 0 1 1 0 0 0
0 1 1 0 0 1 0 1
0 0 1 0 1 0 1 0
1 0 0 1 0 1 0 1
1 1 0 0 1 0 1 0
□ ■ □ □ ■ ■ □ □
■ □ ■ □ □ ■ ■ □
□ ■ □ ■ □ □ ■ ■
■ □ □ ■ ■ □ □ □
□ ■ ■ □ □ ■ □ ■
□ □ ■ □ ■ □ ■ □
■ □ □ ■ □ ■ □ ■
■ ■ □ □ ■ □ ■ □ 我在3#说“最少要有28个黑格”有误，我的简单比划只能得出最少22格，应该不难上升到23格。
实际上求最值不简单，需要用单纯形法。Lingo的(0-1)规划应该是最方便的，可惜我不会，也没安装Lingo.
Mathematica对此编程好像不是很方便，因为它的domain貌似不能用Booleans。 等@mathe的文件发出来了，我倒是很容易用Mathematica滤掉旋转和对称重复。
我估计本原解不会超过16个。 去除对称后应该还有25个
原始数据和过滤后数据都在附件 对25个本原解进行了解剖，统计了黑格数，对称性，结果如下表所示。
黑格数对称性合计
镜像镜像+中心旋转无
2750005
2821148
2970018
3004004
合计1451525
对称重复14×4=565×2=101×2=25×8=40108