作者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/m.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