作者buffalobill (水牛比尔)
看板puzzle
标题Re: [问题] 重排时钟
时间Wed Sep 23 11:13:44 2020
1F：推 michael7201: 大概是 Hamiltonian path 09/23 00:51
2F：→ michael7201: 不对 要 cycle XD 09/23 00:52
4F：→ arthurduh1: 先砍掉 12 和 6，目标变成从 {5, 7} 到 {1, 11} 找 09/23 10:44
5F：→ arthurduh1: 两条 disjoint 的 paths 09/23 10:44
6F：→ arthurduh1: 再砍 1, 5, 7, 11 发现就只剩两条可能的 09/23 10:46
7F：→ arthurduh1: [2, 9, 4] 和 [8, 3, 10] 09/23 10:46
8F：推 arthurduh1: 咦，是四组XD 09/23 10:48
9F：→ arthurduh1: 2, 4, 8, 10 都能各自接 1, 5, 7, 11 09/23 10:50
10F：→ arthurduh1: 除了四个 [i, i+1] 的以外 09/23 10:54
11F：→ 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的话会无解
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 60.251.148.94 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1600830826.A.7D0.html
12F：推 arthurduh1: 奇偶性有想到，可是没细究下去XD 09/23 11:17
13F：→ arthurduh1: 翻转对称可以让可能性先再减半 09/23 11:18
14F：→ buffalobill: 翻转可以固定(7,12,5)或是固定不让3区块与9区堆互换 09/23 11:19
15F：→ buffalobill: 我的算法是固定区块，12->3->6->9这样排除翻转的 09/23 11:20
16F：推 arthurduh1: 哦哦，16 种就排除过翻转对称了 09/23 11:23
17F：推 walkwall: 真有趣的题目 几乎是Puzzleup等级了 09/23 21:27
18F：→ buffalobill: 感谢楼上的鼓励，不过我又没梗了qq 09/24 11:58