52張撲克排，洗牌規則如下：
均勻的從中分成上下兩推各26張，
接著洗牌的時候交插放，
即原本上面那一堆洗完牌後會變成第1,3,5,....51張
下面那一堆洗完牌後會變成第2,4,6,...52張
這樣稱為一次洗牌，
問經過幾次洗牌後，整幅牌會恢復原來的排列。
==
這一題應該不難，但又不會太簡單吧，
若想清礎的話應該就可以作出來，
且我覺得這問題真得蠻有趣的。
題目應該沒有說不清礎的地方吧，若有不清礎在麻煩告訴我。
--
※ 發信站: 批踢踢(ptt.csie.ntu.edu.tw)
◆ From: arist.m7.ntu.edu.tw
> -------------------------------------------------------------------------- <
作者: vt (@@) 看板: puzzle
標題: Re: 洗牌(1000ptt幣)
時間: Sat Apr 7 21:47:40 2001
※ 引述《MurderKiller (可以叫我殺人者嗎?)》之銘言：
: 八？
: 這樣想，是不是太簡單了？？
: 我有可能把題目簡化簡化再簡化了…
: 唉…知其然而不知其所以然…><
嗯
答案是八沒錯
洗牌可以看成是換位置
某張牌目前的順序是第i個[i=0~51]
如果i<26 [也就是第一疊牌啦]
等一下他要換去第2i的位置
如果i>=26 [也就是第二疊牌]
等一下會換到第2i+1-52那個位置
所以呢
可以列出下列這樣的循環表 cycle length
0 0 cl=1
1 2 4 8 16 32 13 26 1 cl=8
3 6 12 24 48 45 39 27 3 cl=8
5 10 20 40 29 7 14 28 5 cl=8
9 18 36 21 42 33 15 30 9 cl=8
11 22 44 37 23 46 41 31 11 cl=8
17 34 17 cl=2
19 38 25 50 49 47 43 35 19 cl=8
51 51 cl=1
而
所有cl的最小公倍數是8
所以呢
經過了八次的洗牌之後
所有的牌都會回到原來的位置
這個方法可以用來對付不同的洗牌法
可以計算到底要洗幾次會跟原本一樣 [也有可能永遠洗不回去吧]
但是這題應該會有個很漂亮的解答法
--
※ 發信站: 批踢踢(ptt.csie.ntu.edu.tw)
◆ From: VT.m3.ntu.edu.tw
> -------------------------------------------------------------------------- <
作者: vt (@@) 看板: puzzle
標題: Re: 洗牌(1000ptt幣)
時間: Sun Apr 8 00:00:16 2001
※ 引述《MurderKiller (可以叫我殺人者嗎?)》之銘言：
: ※ 引述《vt (@@)》之銘言：
: : 可以列出下列這樣的循環表 cycle length
: : 0 0 cl=1
: : 1 2 4 8 16 32 13 26 1 cl=8
: : 3 6 12 24 48 45 39 27 3 cl=8
: : 5 10 20 40 29 7 14 28 5 cl=8
: : 9 18 36 21 42 33 15 30 9 cl=8
: : 11 22 44 37 23 46 41 31 11 cl=8
: : 17 34 17 cl=2
: : 19 38 25 50 49 47 43 35 19 cl=8
: : 51 51 cl=1
: 我也是這樣想的耶…
: 只是我是用i=1~52
: 1~i~26(包含26)，下個位置在2i-1
: 26~i~52，下個位置在(i-26)×2
: 其實是一樣的。
嗯
那是寫程式的習慣啦 從零開始^^
: 1： 1 cl=1
: 2： 3 5 9 17 33 14 27 2 cl=8
: 3： 5 9 17 33 14 27 2 3 cl=8
: (以下略過)
: 不過，不會有幾個位置的牌無法洗回去嗎？
: 我試了五個位置，隨機選的，
: 都是八次，
: 你是用了：1 3 5 9 11 17 19 51這幾個數字，
: 那其他位置沒有試耶…
: 會不會洗不回去？
: 那每個數字都要代入這個公式嗎？？
: 還是說表上的數字
可以任選一個來當初始位置？
: 有沒有更漂亮的解答法？
: 另外，不同洗牌法是指別種分發牌的方式嗎？？
所謂cycle
1 2 4 8 16 32 13 26 1 再下一個也是2呀
所以呢 2 的cycle lenth也是 8
換句話說
上面的表把每個位置都算過了
也就是因為我用的想法蠻笨的 [我愛暴力法^^]
所以期待有更漂亮的解法
--
※ 發信站: 批踢踢(ptt.csie.ntu.edu.tw)
◆ From: VT.m3.ntu.edu.tw
> -------------------------------------------------------------------------- <
作者: bypeng (愛寫程式的小子) 看板: puzzle
標題: Re: 洗牌(1000ptt幣)
時間: Fri Apr 20 03:18:58 2001
※ 引述《vt (@@)》之銘言：
: 這個方法可以用來對付不同的洗牌法
: 可以計算到底要洗幾次會跟原本一樣 [也有可能永遠洗不回去吧]
任何洗牌法，只要：
1. 步驟數是有限的﹔
2. 與任何 random variable 無關，
則只要洗有限次一定可以洗得回去哦。
這是基本的離散數學可以證明的結果。
--
蕭兮北風 地動天搖 天佑吾土 再興吾邦
----------------------------------------
b86077@mail.ee.ntu.edu.tw
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: home.ee.ntu.edu.tw