推 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的话会无解