好了好了，數學課時間～
雖然這麼快就破梗對原 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 張！)
---
以上。本次數學課就到這裡，下課！
(頁末防雷)
--
実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」
亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」
実琴：「難道你沒有男人的尊嚴了嗎?!」
亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」
－－プリンセス・プリンセス 第二話
--
All Comments