找回密码
 欢迎注册
查看: 746|回复: 16

[转载] 圆环染色(转自微信公众号单谈数学)

[复制链接]
发表于 2024-6-25 16:27:25 | 显示全部楼层 |阅读模式

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

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

×
懒得传图片了,改述如下:

一个正16边形的顶点标着0或者1,它的任意四个连续顶点形成的4位二进数(共16个)可否恰好包括0000~1111?
精华
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-6-25 18:26:36 | 显示全部楼层
这个会不会与格雷码(Binary Gray Code)有关?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-6-25 18:49:17 | 显示全部楼层
0000111101100101
圆环染色1.PNG
通过方向和颜色的组合,上述图案可以解释为四个不同的解。其它三解略。

点评

这个解是我从格雷码顺序表中手动搜出来的,只用了几分钟。感谢 hujunhua 精美配图。  发表于 2024-6-26 10:19
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-6-26 02:17:38 | 显示全部楼层
圆环染色2.PNG
通过颜色和方向的组合,这个图案也是能解释为 4 个不同的解。
顺时针方向,红=0,蓝=1:0000111101001011,化为16进数为0F4B

这个图案有一个特点:从任意位置断开化为16进数都得到两对互补数码,比如0F4B中,0+F=4+B=F.
以上述解释为例,四个16进数是:0F4B,1E96, 3D2C, 7A58, 正好验证包含0~F。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-6-26 03:13:35 | 显示全部楼层
还有两个图案,每个也是四解。然后应该是没有了(0000与1111对径无解)。

解3

解3

解4

解4
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-7-2 14:07:13 | 显示全部楼层
这个,可否推广出更一般的规律?感觉蛮有趣的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-7-3 02:56:11 | 显示全部楼层

本题的图论解法,转此留存

且将形成4位二进数的四个连续顶点称为一条边。
16边形的任意三个连续顶点都可以跟前端或者尾端的顶点合成一条边,这两条边视作相邻接,接点就是它们共同的三个顶点。
因此,这三个连续顶点就被视作一个点,编号就是它们对应的三位二进数。
以环的顺时针方向为正向,将方向过渡给上述边成为有向边,即出/入接点的边,其编码为在接点编码的右/左端加一位。
一个合格的正16边形顶点染色,显然包括全部8种可能的编码点,并且形成了一个8点16边的图,图中顺箭头方向存在一条单向欧拉回路。
这个图显然就是下图,如果其中真的存在单向欧拉回路,那么就对应了一种合格染色,本题就有了一解。
圆环染色网络图.png
图中,点000和111所带环形边既是出发边也是进入边。
由于每个接点都有两条进入边和两条出发边,所以必定存在单向欧拉回路,故本题有解。

点评

这也是通用解法,对于n个数,正n^k边形任意连续k个顶点情况都成立  发表于 2024-7-3 07:47

评分

参与人数 1威望 +6 金币 +6 贡献 +6 经验 +6 鲜花 +6 收起 理由
wayne + 6 + 6 + 6 + 6 + 6 这图是咋画的.很对称

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-7-4 17:51:18 | 显示全部楼层

正32边形染色的有向图

32边形染色路线图.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-7-5 05:52:18 | 显示全部楼层

正27边形染3色的有向图

居然还是一个可平面图。
27边形染3色.png

点评

所以64边形呢?是平面图吗?  发表于 2024-7-5 18:44
@wayne WPS Office的流程图工具  发表于 2024-7-5 14:06
啥工具画的这么好  发表于 2024-7-5 11:58

评分

参与人数 1威望 +8 金币 +8 贡献 +8 经验 +8 鲜花 +8 收起 理由
northwolves + 8 + 8 + 8 + 8 + 8 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-7-7 05:27:56 | 显示全部楼层

正64边形染4色的有向图局部

@mathe 包含K33子图,所以不是可平面图。
64点染4色的有向图局部.PNG

评分

参与人数 1威望 +12 鲜花 +12 收起 理由
mathe + 12 + 12 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-7-24 13:57 , Processed in 0.053791 second(s), 21 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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