重排時鐘 - 拼圖

By Margaret
at 2020-09-23T11:13

Table of Contents

推 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