数学研发论坛

 找回密码
 欢迎注册
查看: 1823|回复: 67

[原创] 六边形上19个黑点上不同数字求所有的解!

[复制链接]
发表于 2019-5-9 14:16:17 | 显示全部楼层 |阅读模式

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

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

x
19个黑点上,放上1到19共19个不同数字,使得每个小三角形(注意有6个小三角形)的每边上的三个数加起来都是22. Good luck!
程序求所有的解!

1

1
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-10 09:00:30 | 显示全部楼层
除了暴力搜索,还有什么好办法吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-10 09:36:15 | 显示全部楼层
风云剑 发表于 2019-5-10 09:00
除了暴力搜索,还有什么好办法吗?


除了暴力搜索,就是人肉分析罗。为了人肉方便,推荐按下面图1对19个黑点进行分组编号标记。

图1   19个点的分组和编号标记
这贴原先的内容只是一些数据罗列,现在将后面的标记图提前到此,以便简化人肉分析的表述
------hujunhua, 2019-5-16, 16:45

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-5-10 10:30:21 | 显示全部楼层
风云剑 发表于 2019-5-10 09:00
除了暴力搜索,还有什么好办法吗?

期待大佬程序
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-10 11:17:11 | 显示全部楼层
风云剑 发表于 2019-5-10 09:00
除了暴力搜索,还有什么好办法吗?



图2     一些和为常数的导出组合
人肉分析离不开一些特定的和为常数的导出组合,如图2所示。
组号表示组元之和,设A=2a。
一、边心大三角组合:图2所示俩大三角形顶点之和相等。即
        E12+E34+E56=E23+E45+E61=E/2=29+5a
        显然,对于给定的E组,分成两个大三角组合的划分是唯一的。
二、菱形组合:图2所示三色菱形顶点之和相等,即
         R1+E23+R4+E56=R2+E34+R5+E61=E12+R3+E45+R6=(R+E)/3=51+a
三、小三角形组合:Ri+Rj-Eij=22-2A
四、径向双数组合:Ri+Vi=22-A
         由A+(22-2A)=22-A, (11-a)+(11-a)=22-A 知 22-2A 和 11-a 属于E组。
五、V=37-5a, R=95-7a, E=58+5A

这贴原先的内容只是一些数据罗列,现在将后面的导出组合提前到此,以便简化人肉分析的表述
------hujunhua, 2019-5-16, 16:45

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-10 22:08:17 | 显示全部楼层
手工分析不难,因为结构和数据都比较特殊。
结构的特殊表现在中心重数高,数据的特殊在于 22 是最小的幻方数,故我们A>2时一开始就可以如下图填好五个数:

1

19
2

18
O
O
O
3
O
O
O
O

O
O
O
O

O
O
O

由楼上2V=74-5A 化为 A=(74-2V)/5因 V ≥1+2+...+6=21, 所以 A≤(74-42)/5=32/5。由此得出中心数 A 只能是2, 4, 6三者之一。
易证 A=6 时无解。这时始图可以翻开更多的格进化为

1

19
2

18
15
14
O
3
13
6
O
O

O
O
O
O

O
O
O
(图的进化标识:黑色为已知数,红色为新填数,蓝色为根据新填数的推导填数。以下相同)
考察17必带1+4 或者2+3,但上图中 1 已满邻,2、3异边,故知17已经不可安排。
A=4时, 始图进化为

1

19
2

18
17
16
O
3
15
4
O
O

O
O
O
O

O
O
O

A=4时,22-2A=14, 11-a=9, 这两个属于E组,由于14必带2+6或者3+5,故始图进化出以下两个分枝:
分枝1:14+3+5
119 2

18
17
16
O
3
15
4
O
O

14
13
O
6

5
O
O
14二分之后,9在分化图中只有两个可选格,故亦二分。分枝2:14+2+6

1

19
2

18
17
16
14
3
15
4
12
6

O
O
O
O

O
7
O
14二分之后,9在分化图中只有两个可选格,故亦二分。
分枝1.1:9+2+11

1

19
2

18
17
16
9
3
15
4
7
11

14
13
13
6

5
12
5
5, 13重复,舍弃
分枝1.2:9+5+8

1

19
2

18
17
16
12
3
15
4
10
8

14
13
10
6

5
9
8
8, 10重复,舍弃
分枝2.1:9+6+7

1

19
2

18
17
16
14
3
15
4
12
6

11
10
11

9

8
7
7
7, 11重复,舍弃
分枝2.2:9+3+10

1

19
2

18
17
16
14
3
15
4
12
6

9
8
13
11


10
7
5
唯一解。


最后A=2的情况,始图如下:

1

18
3

O
19
17
O
O
O
2
O
O

O
O
O
O

O
O
O

11-a=10属于E组,10可带1+11, 3+9, 4+8, 5+7,分枝较多,应该还需要计算机枚举。

点评

用表格编着玩,看效果时应该点掉“纯文件”的√, 结果点了个保存。 ^_^^_^^_^  发表于 2019-5-16 22:38
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-11 09:32:17 | 显示全部楼层
风云剑 发表于 2019-5-10 09:00
除了暴力搜索,还有什么好办法吗?

在一个合格的填法中,将所有的数都对2取余,不考虑对称的区别,容易得出奇偶分布只有以下两种
1 0 1
11 1 1
0 0 0 0 0
0 0 1 1
0 1 1
A=4, R, V, E/2皆为奇数
1 0 1
1 1 1 0
0 0 0 1 1
0 0 1 0
0 1 1
A=2, R, V, E/2皆为偶数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-11 14:47:41 | 显示全部楼层
mathe 发表于 2019-5-10 22:08
手工分析不难,因为结构和数据都比较特殊。
...


接6楼,中心为2的比较特殊,在于 Ri+Vi=20, 正好是互补对。
一共是9个互补对,5奇4偶。
除了2+18还剩8个,所以E组有两个互补对,一奇一偶(由楼上奇偶图知)。
18和10属于E组,易知两者必属于同一个E/2三角组,否则两个E/2组必定各含一奇一偶的互补对,但这样一个和为20+18,一个和为20+10,不相等。
18和10所在E/2组剩下一角为6 → 另一个E/2组为14+奇互补对。
1、如此一来,径向双数组合 Ri+Vi=20还有以下7选6
19+1(始图所含,必选)
17+3(始图所含,必选)
16+4(偶对,必选)
12+8(偶对,必选)
15+5(以下奇对3选2)
13+7
11+9
其中前4必选,后面3个奇对选其2,剩1个奇对归入14所在E/2组。
2、V=32去掉含 10, 6 的还有3解
         =1+3+4+5+7+12
         =1+3+4+5+8+11
         =1+3+4+7+8+9
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-11 19:09:28 | 显示全部楼层
风云剑 发表于 2019-5-10 09:00
除了暴力搜索,还有什么好办法吗?


用线性规划来做,不过,好像是无解。
  1. data={{1,2,3},{1,4,8},{1,5,10},{3,6,10},{3,7,12},{8,9,10},{10,11,12},{8,13,17},{10,14,17},{10,15,19},{12,16,19},{17,18,19}};
  2. m=SparseArray[Flatten[Table[Map[{d,#}->1&,data[[d]]],{d,Length[data]}],1],{12,19}];
  3. LinearProgramming[PadRight[{1},19],Join[m,Table[RotateRight[PadRight[{-1,1},19],i],{i,0,17}]],Join[ConstantArray[22,12],ConstantArray[1,18]],ConstantArray[{1,19},19]]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-11 19:26:35 | 显示全部楼层
wayne 发表于 2019-5-11 19:09
用线性规划来做,不过,好像是无解。

就这么4个基本解(如果不计旋转,翻转,填法是唯一的)。
1
19
2
18
17
16

14
3
15
4
12
6
9
8
13
11
10
7
5
1
183
9191714
1282155
616
13
10
4117
1
183
13191714
8122155
1016
9
6

4711
1
183
14191715
7132164
611
12
10
958

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

本版积分规则

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

GMT+8, 2019-11-19 12:40 , Processed in 0.085785 second(s), 23 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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