每日一题[3697]反复洗牌

2025年1月广东省佛山市高三数学质检试卷 #19

将 $2 N$ 项数列 $\left(a_1,a_2\cdots,a_N,b_1,b_2,\cdots,b_N\right)$ 重新排序为 $\left(b_1,a_1,b_2,a_2,\cdots,b_N,a_N\right)$ 的操作称为一次洗牌，即排序后的新数列以 $b_1$ 为首项，将 $a_i$ 排在 $b_i$ 之后，将 $b_{i+1}$ 排在 $a_i$ 之后．对于数列 $(1,2,\cdots,2 N)$，将洗牌后得到的新数列中数字 $k$ 的位置定义为 $f(k)$．例如，当 $N=3$ 时，数列 $(1,2,3,4,5,6)$ 经过一次＂洗牌＂后变为 $(4,1,5,2,6,3)$，此时 $f(1)=2$，$f(2)=4$，$f(3)=6$，$f(4)=1$，$f(5)=3$，$f(6)=5$．

1、写出数列 $(1,2,3,4,5,6,7,8)$ 经过 $3$ 次洗牌后得到的新数列；

2、对于满足 $1\leqslant k\leqslant 2 N$ 的任意整数 $k$，求经过一次洗牌后 $f(k)$ 的解析式；

3、当 $N=2^{n-1}$（其中 $n\in\mathbb N^{\ast}$）时，数列 $(1,2,\cdots,2 N)$ 经过若干次洗牌后能否还原为 $(1,2,\cdots,2 N)$？如果能，请说明至少需要多少次洗牌；如果不能，请说明理由．

解析

1、根据题意，有 $$\begin{split} & (1,2,3,4,5,6,7,8) \\ \to& (5,1,6,2,7,3,8,4)\\ \to&(7,5,3,1,8,6,4,2)\\ \to&(8,7,6,5,4,3,2,1). \end{split}$$

2、根据题意，有 $$f(k)=\begin{cases} 2k,&k=1,2,\cdots,N,\\ 2k-2N-1,&k=N+1,N+2,\cdots,2N.\end{cases}$$

3、将洗牌 $m$ 次后得到的新数列中数字 $k$ 的位置定义为 $f_m(k)$，则 $$f_m(k)\equiv 2^m\cdot k\pmod{2N+1},$$ 于是 $$f_m(k)=k\iff 2^m\equiv 1\pmod{2N+1}\iff 2^m\equiv 1\pmod{2^n+1},$$ 也即 $$2^m-1=p(2^n+1)\iff 2^m-p\cdot 2^n=p+1,$$ 其中 $p\in\mathbb N^{\ast}$，可得 $$2^n\mid (p+1)\implies p\geqslant 2^n-1,$$ 当 $m=2n$ 时，$p=2^n-1$ 符合题意，至少需要 $2n$ 次洗牌可以还原．