http://acm.hdu.edu.cn/showproblem.php?pid=1210

開始尋找規(guī)律，找了好久想不出，最終想到了追蹤第一張牌來進(jìn)行求解！O(∩_∩)O~


雖然做時(shí)不知道為什么！但是事后我在網(wǎng)上搜到了證明方法！

洗牌問題：
很多人都是跟蹤第一張牌來完成的，大家會(huì)不會(huì)證明呢？

定理1：當(dāng)?shù)谝粡埮?牌1)回到初始位置時(shí)，所有的牌都回到了初始位置。

證明：設(shè)有一次操作，某牌在操作前處于位置r(1<=r<=2*N)，那么，操作后，如果r原來是前一半的，顯然r'=r*2; 否則，r'=(r-n)*2-1，即r'='r*2-(N*2+1);
將兩個(gè)式子綜合，可以得到r'= (r*2)%(N*2+1);
根據(jù)同余定理之一 ((i%m)*j)%m=(i*j)%M，可以整理出公式：i次操作后，該牌的位置為：
(r*(2^i))%(N*2+1);其中^表示乘方。
現(xiàn)在，我們假設(shè)經(jīng)過M次操作后，牌1回到了初始位置，即(1*(2^M))%(N*2+1)=1時(shí)，再次應(yīng)用同余定理，可以證明對(duì)于任意的k(1<=k<=2*N)，有(k*(2^M))%(N*2+1)=k，翻譯成自然語言就是：當(dāng)?shù)谝粡埮苹氐匠跏嘉恢脮r(shí)，所有的牌都回到了初始位置。命題得證。

定理2：一定存在某次操作M，這次操作后，所有的牌都回到了初始位置。
證明：我們已經(jīng)證明了牌1回到初始位置時(shí)，所有的牌都回到初始位置，所以我們只需要證明牌1可以回到初始位置，即(2^M)%(N*2+1)=1一定有正整數(shù)解。證明這個(gè)定理前我們首先證明這樣一個(gè)定理：
定理2.1：(2*r)%(2*n+1)==t
當(dāng)t確定為1到2*n中的某值時(shí)(1<t<=2*n)，r在1到2*n間有唯一解
因?yàn)?*n+1是奇數(shù)，我們只要看一下就會(huì)發(fā)現(xiàn)r到t是一個(gè)一一映射，當(dāng)t為偶數(shù)時(shí)，顯然r=t/2，當(dāng)t為奇數(shù)時(shí)，r=(t+1)/2+n，

現(xiàn)在我們來證明定理2。運(yùn)用反正法，若牌1永遠(yuǎn)不能回到初始位置，根據(jù)鴿籠定理，牌1必然陷入了某個(gè)不包含位置1的循環(huán)，因?yàn)橄乱粻顟B(tài)僅和當(dāng)前狀態(tài)有關(guān)，當(dāng)前狀態(tài)最多只有2*N種，所以顯然一定在不超過2*N+1次操作內(nèi)出現(xiàn)重復(fù)狀態(tài)。而重復(fù)狀態(tài)則意味著循環(huán)。
因?yàn)槲覀兗僭O(shè)這一循環(huán)不包括位置1，我們?cè)O(shè)f(i)為循環(huán)中某狀態(tài)，f(0)=1,f(n+1)=(f(n)*2)%(2*N+1)，f(j)為若干次循環(huán)后出現(xiàn)的重復(fù)狀態(tài)，即f(i)=f(j)。因?yàn)檠h(huán)一直持續(xù)，不妨假設(shè)j>i+i。又因?yàn)檠h(huán)不包括狀態(tài)1，即對(duì)于任意的k>=i，f(k)!=1
根據(jù)定理2.1，我們可以根據(jù)當(dāng)前狀態(tài)推出上一狀態(tài)，換句話說，若f(i)=f(j)，則f(i-1)=f(j-1)。繼續(xù)套用定理2.1，可以得到f(i-i)=f(j-i)，即：f(j-i)=f(0)=1。又有假設(shè)j>i+i，即j-i>i，與另一假設(shè)對(duì)于任意的k>=i，f(k)!=1矛盾。
因此，可以證明，牌1所陷入的循環(huán)，必然是包含位置1的，即一定有某次操作，操作后牌1回到了初始狀態(tài)。而且顯然的，初始狀態(tài)就是這循環(huán)中的一個(gè)狀態(tài)。
因此命題得證。