数学研发论坛

 找回密码
 欢迎注册
查看: 923|回复: 63

[求助] 网格染色问题

[复制链接]
发表于 2020-7-10 20:57:34 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首帖奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-12 19:42:51 | 显示全部楼层
■■■■■■■■
■□□□□■□□
□□□□□□□□
□□□□□□□□
□□□□□□□□
■■■■■■■■
■□□□□■□□
□□□□□□□□


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

如果限制涂黑的正方形的个数或许还需要多想一想
不限制……
挨个涂就是了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-13 09:15:40 | 显示全部楼层
楼上显然不正确,简单比划了一下,至少需要涂黑28格。应该还可以上升。

4×5和5×4的长方形共有(4×5)×2=40个呢。每个长方形中的黑格密度为9/20。
40个应该有一定的代表性了,所以平均来说,黑格数=64×(9/20)=28.8.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-13 12:38:54 | 显示全部楼层
本帖最后由 .·.·. 于 2020-7-13 12:39 编辑
hujunhua 发表于 2020-7-13 09:15
楼上显然不正确,简单比划了一下,至少需要涂黑28格。应该还可以上升。

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


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

点评

我想题目原意就是只考虑尺寸,不考虑方向的。  发表于 2020-7-13 15:11
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-13 14:28:31 | 显示全部楼层
  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
复制代码

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

点评

不多啊,做个文件发出来看看。  发表于 2020-7-13 16:53
计算机搜索共108个解。如果考虑对称性之类的,应该可以减少很多,估计数目不会很多。  发表于 2020-7-13 16:12
经Mathematica检查正确  发表于 2020-7-13 15:08

评分

参与人数 2威望 +6 金币 +8 贡献 +6 经验 +6 鲜花 +6 收起 理由
KeyTo9_Fans + 3 + 4 + 3 + 3 + 3 很给力!
hujunhua + 3 + 4 + 3 + 3 + 3 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-13 16:58:06 | 显示全部楼层
我在3#说“最少要有28个黑格”有误,我的简单比划只能得出最少22格,应该不难上升到23格。
实际上求最值不简单,需要用单纯形法。Lingo的(0-1)规划应该是最方便的,可惜我不会,也没安装Lingo.
Mathematica对此编程好像不是很方便,因为它的domain貌似不能用Booleans。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-13 17:14:18 | 显示全部楼层
等@mathe的文件发出来了,我倒是很容易用Mathematica滤掉旋转和对称重复。

我估计本原解不会超过16个。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-13 18:41:36 来自手机 | 显示全部楼层
去除对称后应该还有25个

点评

比16个很多一点啊,我是低估对称度了。  发表于 2020-7-14 00:53
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-13 19:33:23 | 显示全部楼层
fc.tgz (1.3 KB, 下载次数: 8)

评分

参与人数 1威望 +12 金币 +12 贡献 +12 经验 +12 鲜花 +12 收起 理由
hujunhua + 12 + 12 + 12 + 12 + 12 连解带滤,很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-14 00:41:25 | 显示全部楼层
对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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-10-22 08:52 , Processed in 0.085343 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表