Re: [问题] 重排时钟

楼主: buffalobill (水牛比尔)   2020-09-23 11:13:44
推 michael7201: 大概是 Hamiltonian path 09/23 00:51
→ michael7201: 不对 要 cycle XD 09/23 00:52
推 arthurduh1: 意外地只有一组解 https://imgur.com/JJtsqqK.png 09/23 10:43
→ arthurduh1: 先砍掉 12 和 6,目标变成从 {5, 7} 到 {1, 11} 找 09/23 10:44
→ arthurduh1: 两条 disjoint 的 paths 09/23 10:44
→ arthurduh1: 再砍 1, 5, 7, 11 发现就只剩两条可能的 09/23 10:46
→ arthurduh1: [2, 9, 4] 和 [8, 3, 10] 09/23 10:46
推 arthurduh1: 咦,是四组XD 09/23 10:48
→ arthurduh1: 2, 4, 8, 10 都能各自接 1, 5, 7, 11 09/23 10:50
→ arthurduh1: 除了四个 [i, i+1] 的以外 09/23 10:54
→ arthurduh1: 还有 [5, 10] 09/23 11:00
答案就是4,令人意外的少
https://i.imgur.com/tXiFzjQ.png
也许有人一看到12个数字排列
就以为要计算12!种情形,然后打开了IDE准备写程式...
nononono这题其实稍微推理一下就可以将数字大幅删减:
.因互质故所有偶数不得相邻,六奇六偶一定会排成奇偶奇偶....
.12旁边只能放7跟5,同理6旁边只能放1跟11
.承上可推理出3旁边只能放8跟10,9旁边只能放2跟4
整个时钟就变成(7,12,5)(8,3,10)(1,6,11)(2,9,4)四个区块
每个区块只有两种变化,只需计算16种情形
附带一提,如果时钟没有12,只有1~11的话
那答案数量会爆增,有35个:
https://i.imgur.com/L75ZAmR.png
然后1~10的话会无解
作者: michael7201 (燮)   2019-09-23 00:51:00
大概是 Hamiltonian path不对 要 cycle XD
作者: arthurduh1 (arthurduh1)   2019-09-23 10:43:00
意外地只有一组解 https://imgur.com/JJtsqqK.png先砍掉 12 和 6,目标变成从 {5, 7} 到 {1, 11} 找两条 disjoint 的 paths再砍 1, 5, 7, 11 发现就只剩两条可能的[2, 9, 4] 和 [8, 3, 10]咦,是四组XD2, 4, 8, 10 都能各自接 1, 5, 7, 11除了四个 [i, i+1] 的以外还有 [5, 10]奇偶性有想到,可是没细究下去XD翻转对称可以让可能性先再减半
楼主: buffalobill (水牛比尔)   2020-09-23 11:19:00
翻转可以固定(7,12,5)或是固定不让3区块与9区堆互换我的算法是固定区块,12->3->6->9这样排除翻转的
作者: arthurduh1 (arthurduh1)   2020-09-23 11:23:00
哦哦,16 种就排除过翻转对称了
作者: walkwall (会走路的墙)   2020-09-23 21:27:00
真有趣的题目 几乎是Puzzleup等级了
楼主: buffalobill (水牛比尔)   2020-09-24 11:58:00
感谢楼上的鼓励,不过我又没梗了qq

Links booklink

Contact Us: admin [ a t ] ucptt.com