Re: [問題] 完美洗牌

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (-858993460)時間15年前 (2011/01/06 19:49)推噓5(5推 0噓 9→)

留言14則, 5人參與討論串2/2 (看更多)

好了好了，數學課時間～雖然這麼快就破梗對原 PO 有點不好意思不過解答還是我來 PO 好了... (以下有全雷，要自己想的請左鍵) --- 其實什麼左手在上右手在上的這兩種情形已經有個專有名詞來講它了四張牌太少我們以六張牌做例子原順序是 1 2 3 4 5 6 其中一種組果是 4 1 5 2 6 3 這稱做 in shuffle 另外一種結果是 1 4 2 5 3 6 這稱做 out shuffle 這個 in 和 out 怎麼來的？看第一張和最後一張它們原本在牌堆的最外面如果洗完後跑到第二張(裡面)去就叫 in shuffle 如果洗完後還在外面就叫 out shuffle --- 雖然洗牌有 in shuffle 和 out shuffle 兩種但其實兩種是同一個情形... 這是怎麼回事呢？再看個例子: 這是 8 張牌的 out shuffle 結果: 1 5 2 6 3 7 4 8 這是 6 張牌的 in shuffle 結果: 4 1 5 2 6 3 注意到了嗎？因為 out shuffle 的頭尾兩張不變所以把這兩張拿掉不影響它的本質而拿掉之後正好是少兩張牌的 in shuffle... --- 好的這麼一來我們只要考慮 in shuffle 就可以了那麼對於 2n 張的 in shuffle 我們可以歸納出第 k 張牌洗牌後它們的位置: /第 2k 張, 如果 k≦n | \第 2k-2n-1 張, 如果 k＞n 這個只要多看幾個例子就能歸納出來了的就留做習題(?) --- 可是上面這個式子有個條件判斷有點討厭所以利用同餘運算我們可以把它去掉: 2n 張牌的 in shuffle 第 k 張牌洗牌後會在第 (2k mod (2n+1)) 張這個 mod 就是除了取餘數的意思那麼原來的問題就變成了: 給定 n, 問從任一個 1~n 之間的數開始每次乘 2 後再對 2n+1 取餘要做幾次才會回到原來的數？ --- 對抽象代數有點觀念的版友應該到這裡就知道答案了: 最後這個問題正是 2 對 2n+1 的 multiplicative order 的定義 (抱歉這個詞中文實在不太清楚該怎麼翻... 抽象代數裡(一個群的)的 order 這個詞有個翻譯叫做「目」或「階」但 multiplicative order 這個詞實在還沒看到過有什麼翻譯...乘法階?) 有了關鍵字就好找了以下這個數列就是答案: ( http://oeis.org/A002326 ) 1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, ... 其中 2n 張牌的答案 out shuffle 是第 n 項 in shuffle 是第 n+1 項 --- 同樣的方法也可以拿來解奇數張的問題不過奇數張就不分 in/out 了因為頭尾至少會有一張在外面那張在外面的牌拿掉並不影響調換的次序然後再仔細看你會發現它等同於少一張的 in shuffle... 例如 7 張牌的例子也許是 1 5 2 6 3 7 4 也許是 4 1 5 2 6 3 7 但它們都和 6 張的 in shuffle (4 1 5 2 6 3) 本質上是一樣的所以一樣查看上面數列的第 4 項就知道 7 張的答案是 3 次了推文提到的 Liar Game 裡的 17 張也是數列的第 9 項是 8 所以 17 張就是 8 次 --- 那麼回到這個數列有人可能會問那到底有沒有公式可以求呢？我得坦白說: 沒有顯表達式這個值數學上記做 ord (2) 2n+1 我們只能知道 ord (2) 會是 φ(2n+1) 的因數而已 2n+1 (φ(N) 是所謂的 Euler totient function, 表示小於 N 和 N 互質的正整數個數) 實際算還是得慢慢乘，但已經比一口氣看著 N 張牌好多了 (秋山深一：你的動態視力只能一次追一張，我的數學可以一次追 17 張！) --- 以上。本次數學課就到這裡，下課！ (頁末防雷) -- 実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」実琴：「難道你沒有男人的尊嚴了嗎?!」亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」－－プリンセス・プリンセス第二話 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.230.62