给定正整数 $n$，有 $2n$ 张纸牌叠成一堆，从上到下依次编号为 $1$ 到 $2n$．我们进行这样的操作：每次将所有从上往下数偶数位置的牌抽出来，保持顺序放在牌堆下方．例如 $n=3$ 时，初始顺序为 $123456$，操作后依次得到 $135246$，$154326$，$142536$，$123456$．证明：对任意正整数 $n$，操作不超过 $2n-2$ 次后，这堆牌的顺序会变回初始状态．
【难度】
【出处】
2016年北京大学数学学科夏令营初赛
【标注】
【答案】
略
【解析】
我们证明一个等价的命题，将每次操作改为先从上往下取后一半的数出来，然后与前一半交叉放置（类似于洗扑克牌），如初始顺序为 $123456$，操作后依次得到 $142536$，$154326$，$135246$，$123456$．将纸牌按顺时针摆放，使得第一张牌和最后一张牌（它们始终为 $1$ 和 $2n$）重合，将第一张牌的位置记为 $1$，顺时针旋转将其他牌的位置依次记为 $2,3,\cdots ,2n-1$．定义纸牌 $m$ 顺时针旋转到纸牌 $n$ 时旋转的步数为纸牌 $m$ 到 $n$ 的距离，记为 $d(m\to n)$，如图中 $d(2\to 3)=3$．
下面证明经过 $k$ 次操作（$k\in\mathbb N^*$）后 $d(1\to 2)=d(2\to 3)=\cdots =d(2n-1\to 2n)$，用数学归纳法．
归纳基础 当 $k=1$ 时，有$$d(1\to 2)=d(2\to 3)=\cdots =d(2n-1\to 2n)=1,$$命题成立．
归纳假设与递推证明 设当 $k=p$ 时，有 $d(1\to 2)=d(2\to 3)=\cdots =d(2n-1\to 2n)=q$．不难计算得经过操作后位置 $x$ 的纸牌将会移动到位置$$f(x)=(2x-1)\%(2n-1),$$其中 $t\%s$ 表示 $t$ 模 $s$ 的余数，因此原来距离为 $q$ 的纸牌在操作后距离为 $(2q)\%(2n-1)$．因此经过 $p+1$ 次操作后，仍然有$$d(1\to 2)=d(2\to 3)=\cdots =d(2n-1\to 2n).$$综上所述，经过 $k$ 次操作（$k\in\mathbb N^*$）后 $d(1\to 2)=d(2\to 3)=\cdots =d(2n-1\to 2n)$．这就意味着当纸牌 $2$ 的位置确定时，其他所有纸牌的位置都可以依靠该性质确定．而纸牌 $2$ 至多只有 $2n-2$ 种可能的位置（纸牌 $2$ 的所在的位置不可能出现不包含位置 $2$ 的循环．这是因为操作是可以反向的，因此如果出现不包含位置 $2$ 的循环，那么可以断定最初的状态纸牌 $2$ 所在的位置不可能为 $2$），因此经过不超过 $2n-2$ 次操作后，纸牌 $2$ 必然回到位置 $2$，原命题得证．
下面证明经过 $k$ 次操作（$k\in\mathbb N^*$）后 $d(1\to 2)=d(2\to 3)=\cdots =d(2n-1\to 2n)$，用数学归纳法．
答案
解析
备注
