完美洗牌 - 拼圖

好了好了，數學課時間～

雖然這麼快就破梗對原 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 張！)


---









以上。本次數學課就到這裡，下課！

(頁末防雷)









--
実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」
亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」
実琴：「難道你沒有男人的尊嚴了嗎?!」
亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」
－－プリンセス・プリンセス 第二話

--