Re: [問題] 重排時鐘

[buffalobill (水牛比爾)]

推 michael7201: 大概是 Hamiltonian path
→ michael7201: 不對 要 cycle XD
推 arthurduh1: 意外地只有一組解 https://imgur.com/JJtsqqK.png
→ arthurduh1: 先砍掉 12 和 6，目標變成從 {5, 7} 到 {1, 11} 找
→ arthurduh1: 兩條 disjoint 的 paths
→ arthurduh1: 再砍 1, 5, 7, 11 發現就只剩兩條可能的
→ arthurduh1: [2, 9, 4] 和 [8, 3, 10]
推 arthurduh1: 咦，是四組XD
→ arthurduh1: 2, 4, 8, 10 都能各自接 1, 5, 7, 11
→ arthurduh1: 除了四個 [i, i+1] 的以外
→ arthurduh1: 還有 [5, 10]
答案就是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://www.ptt.cc/bbs/puzzle/M.1600830826.A.7D0.html
推 arthurduh1: 奇偶性有想到，可是沒細究下去XD
→ arthurduh1: 翻轉對稱可以讓可能性先再減半
→ buffalobill: 翻轉可以固定(7,12,5)或是固定不讓3區塊與9區堆互換
→ buffalobill: 我的算法是固定區塊，12->3->6->9這樣排除翻轉的
推 arthurduh1: 哦哦，16 種就排除過翻轉對稱了
推 walkwall: 真有趣的題目  幾乎是Puzzleup等級了
→ buffalobill: 感謝樓上的鼓勵，不過我又沒梗了qq