完美的「洗」牌？

01-30

（圖片版權歸視覺中國）

1954年，英國魔術發明家埃爾姆斯利發現，可以通過完美洗牌法將最上面一張牌洗到給定的任意位置 $x$ ：

1. 將 $x$ 的值表示為二進位表示；

2. 自左而右，將1看作內洗法，將0看作外洗法，按此順序洗牌即可。

例如 $x=18=(10010)_2$ 如圖所示，經過1次內洗法、2次外洗法、1次內洗法、1次外洗法就可將最初位置0的紙牌洗到給定的位置18：

假設目標位置 $x$ 的二進位表示為 $b_1b_2…b_k（1leq kleq6）$ ，使用歸納法證明上述方法的正確性。

證明

$k=1$ 時很容易驗證上述方法正確。

$k>1$ 時，設 $y=lfloor x/2 rfloor=b_1b_2…b_{k-1}$ ，由歸納假設上述方法可以將最初最上面一張牌洗到第 $y$ 個位置。

完成歸納法證明。

外洗法和內洗法置換的形式化
外洗法置換的形式化表示為： $f(2i)=i，f(2i+1)=26+i，0leq ileq 25$ ；

內洗法置換的形式化表示為： $g(2i+1)=i，g(2i)=26+i，0leq i leq 25$ 。