Re: [問題] 完美洗牌

[LPH66 (-858993460)]

好了好了，數學課時間～

雖然這麼快就破梗對原 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
推 puzzlez:..................................................
→ puzzlez:這跟你個版的文章一樣....很深奧=   =
推 walkwall:起立  敬禮  (謝謝老師)  各位同學回去記得做習題喔(?)
→ walkwall:其實拿來做高中科展也不錯
推 flamerecca:突然好像看懂了 突然又好像沒看懂@@"
推 SansWord:這題我有自己想過，也是用循環群的想法。
→ SansWord:簡單的來說我們的值域會位於 Z52之中，如果Operator得當
→ SansWord:那就勢必會循環。
→ LPH66:嗯, 說起來我這裡其實是證明了它在 Z53* 當中
→ LPH66:所以由乘法群的結論就能直接得到循環
→ LPH66:不過一般的情況有個置換群的概念  這題只是特例而已
推 SansWord:應該說的確是用Permutation Group來跑，只是我現在只追蹤
→ SansWord:第一張是否會到原位。
→ SansWord:總之我想我們的想法是類似的....^^(話說我卡第六關了)