这个问题我在知乎上也有发布，点击这里

问题描述

卡片插入问题 设有 $N = 2^n$ 张卡片，初始时按从上到下的顺序依次编号为：

\[1,2,3,\dots,2^n\]

定义一种操作 $A$，其步骤如下：

  1. 从当前牌叠的最上方取出前 $2^{n−1}$ 张卡片，将这若干张卡片作为一个整体进行上下翻转（即原在最上者变为最下，原在最下者变为最上）。
  2. 将翻转后的这 $2^{n−1}$ 张卡片，从最上方开始，以间隔摆放的方式依次放入新的排列位置中。具体而言，新序列的位置从上到下依次编号为 $1,2,…,2n$，将这些卡片依次放入位置 $1,3,5,…$（即所有奇数位置）。
  3. 取原牌叠中剩余的 $2^{n−1}$ 张卡片（即原下半部分），保持其原有相对顺序不变，从上到下依次插入新序列中的所有空隙中，即放入位置 $2,4,6,…$（所有偶数位置）。

求证：对于任意正整数 $n$，对初始顺序的 $2^n$ 连续执行 $n+1$ 次 $A$ 操作，卡片将恢复到初始的排列顺序：

\[1,2,3,\dots,2^n\]

问题解决

这个问题是在MNIOMath群里面提出来的，当时在和沙包讨论算法题，我问他有没有难题，于是他就给我丢了这么一个题目。我简单用 Python 实现了一下功能，发现这个结论有很大概率是对的。下面给出Python代码：

class Cards:  
    def __init__(self, n):  
        self.list = [i for i in range(2 ** n)]  
        self.len = 2 ** n  
  
    def flip_num(self):  
        self.list = list(reversed(self.list[:self.len // 2])) + self.list[self.len // 2:]  
        pass  
  
    def insert_num(self):  
        new_list = [0] * self.len  
        for i in range(self.len // 2):  
            new_list[2 * i] = self.list[i]  
  
        for i in range(self.len // 2, self.len):  
            new_list[2 * (i - self.len // 2) + 1] = self.list[i]  
  
        self.list = new_list  
        pass  
  
    def operation_a(self):  
        self.flip_num()  
        self.insert_num()  
        pass  
  
num = int(input())  
l = Cards(num)  
l_origin = Cards(num)  
  
l.operation_a()  
cnt = 1  
  
while l.list != l_origin.list:  
    cnt += 1  
    l.operation_a()  
  
print(cnt)

探路1 - 正面突破

在与群内的XuanYu等人讨论之后，我们构造了下面这一个函数：

\[x_{i,j} = \begin{cases} x_{(2^{n-1}+i/2),j-1} & i \equiv 0 \pmod{2} \\ x_{(2^{n-1}-(i-1)/2),j-1} & i \equiv 1 \pmod{2} \end{cases}\]

注意到问题与 $j$ 的取值并无关系，因此只需要证明

\[f(i) = \begin{cases} 2^{n-1} + i/2, & i \equiv 0 \pmod{2} \\[4pt] 2^{n-1} - (i-1)/2, & i \equiv 1 \pmod{2} \end{cases}\]

其满足

\[i=f^{n+1}(i)\]

XuanYu在尝试正面突破之后坠机了😭，不过其中他认可了将下标二进制化这条路。之所以会有这种想法，是因为题目的 $2^n$ 这个数十分特殊，很难不让人联想到二进制。再者，对下标奇偶性的判断，二进制也方便的多，只需要看尾位是 $0$ 还是 $1$ 即可。

探路2 - 反面突破

正面突破的另外一个难点在于 “如何判断其下标在前半段还是后半段”，这使得操作在数学表达上相当繁琐（事后想了想，好像就是看首位是 $0$ 还是 $1$，不过都大差不差）。XuanYu放弃后，我也没啥事干，就接起了这个工作。经过思考后，我认为倒推是一个比较可行的路子，即我们考虑上面函数的逆函数——$f^{-1}$。

符号规定

为了方便下标的二进制表示，我们记位置的取值范围为 $[0,2^n-1]$，即 $[(0\cdots0)_2,(1\cdots1)_2]$

一定要注意，这里的偶数和奇数是下标在 $[0,2^n-1]$ 的取值范围下的整数，原题下标取值范围是 $[1,2^n]$，所以奇偶性应该相反。

$f^{-1}$ 的规则

我们记 $f$ 为操作 $A$，下面考虑 $f^{-1}$ ，对于下标位 $b$ 的数 $x_b$，我们令 $b=(b_{n}\cdots b_1)_2$ ：

  • 如果 $b_1=0$，即为偶数，那么 $x_{b,j}$ 必定来自于 $x_{·,j-1}$ 的前半部分，具体位置在 $2^{n-1}-1-\frac{b}{2}$，体现在二进制上，也就是 $(b_n\cdots b_20) / 2=b_n\cdots b_2$ ，然后因为被 $2^{n-1}-1$ 减去，所以取反。也就得到 \(0\overline{b_n\cdots b_2}\quad或\quad b_1\overline{b_n\cdots b_2}\)
  • 如果 $b_1=1$，即为奇数，那么 $x_{b,j}$ 必定来自于 $x_{·,j-1}$ 的后半部分，具体位置在 $2^{n-1}+\frac{b-1}{2}$，体现在二进制上，也就是 $(b_n\cdots b_{2}0)/2=b_n\cdots b_2$，然后加上一个 $2^{n-1}$ ，也就得到 \(1b_n\cdots b_2\quad或\quad b_1b_n\cdots b_2\)

    逆操作与移位操作

    为了方便标记，我们把取反这个操作也规定为一个函数，就叫 $r$ 好了。关于 $r$ 的性质，显然有 $r·r=\textbf{id}$，且 $r$ 也满足基本的幂运算性质，即 $r(r(x))=r^2(x)$。实际上，$r$ 可以表示为下面这个运算

\(r^n(b_i)=b_i+n\pmod2\) 自证不难。

我们不妨把 $b$ 设为一个 $n$ 维向量 $[b_n,\cdots,b_1]^T$。我们注意到有一个将最后一位放到第一位的位移操作，这个位移的操作我们可以表示为一个矩阵 $L$：

\[L = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \end{pmatrix}\]

重新定义 $f^{-1}$ 并引入 $a_i$

原本抽象的 $f$ 可以被我们用 $L$ 和 $r$ 表示。进一步的，我们可以用矩阵来重新定义上面的两种情况。现在我们重新为上面逆操作的两种情况定义：

  • 对于 $b_1=0$ 的情况， \(f^{-1}(b)=b_1r(b_n)\cdots r(b_3)r(b_2)=r^0(b_1)r(b_n)\cdots r(b_3)r(b_2)\)
\[f^{-1}_{even}=\begin{pmatrix} 0 & r & 0 & \cdots & 0 \\ 0 & 0 & r & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & r \\ r^0 & 0 & \cdots & 0 & 0 \end{pmatrix}\]
  • 对于 $b_1=1$ 的情况， \(f^{-1}(b)=b_1b_n\cdots b_2=r^0(b_1)r^0(b_n)\cdots r^0( b_2)\)
\[f^{-1}_{odd}=\begin{pmatrix} 0 & r^0 & 0 & \cdots & 0 \\ 0 & 0 & r^0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & r^0 \\ r^0 & 0 & \cdots & 0 & 0 \end{pmatrix}\]

我们发现 $b_i$ 的值最终实际上由 $r$ 的指数项决定。现在我们为每一位二进制维护一个数字 $a_i$，专门记录它被反转了几次，即有：

\[f^{-(n+1)}(b)=r^{a_1}(b_1)r^{a_n}(b_n)\cdots r^{a_2}(b_2)\] \[f^{-(n+1)}=\begin{pmatrix} 0 & r^{a_n} & 0 & \cdots & 0 \\ 0 & 0 & r^{a_{n-1}} & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & r^{a_2} \\ r^{a_1} & 0 & \cdots & 0 & 0 \end{pmatrix}\]

很遗憾，因为 $n+1\equiv 1\pmod n$，而 $L^n=\mathbf{id}$ ，所以算下来会有一次位移。如果没有位移的话，只需要证明 $a_i\equiv 0\pmod 2$ 即可。但是但是，很可惜~

总结一下，想要知道 $b$ 在 $n+1$ 次逆操作之后是不是原来的数，只需要看 $b$ 的每一位是不是和原来一样的就行了。而 $b$ 的每一位的值取决于其反转了几次，即 $r$ 的指数项，我们上面将这个指数项规定为 $a_i$ 了，所以接下来，我们应该去研究 $a_i$ 要怎么算。

引入更多的符号

现在我们来研究 $a_i$，我们设有向量 $\alpha=[a_n,\dots,a_1]^T$ 那么就有递推公式：

\[\begin{pmatrix} a_1^{(t+1)} \\ a_2^{(t+1)} \\ \vdots \\ a_{n-1}^{(t+1)} \\ a_n^{(t+1)} \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \end{pmatrix} \begin{pmatrix} a_1^{(t)} \\ a_2^{(t)} \\ \vdots \\ a_{n-1}^{(t)} \\ a_n^{(t)} \end{pmatrix} + \beta_t \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \\ 0 \end{pmatrix}\]

其中 $t$ 表示第 $t$ 次逆操作后的数值，$\beta_t$ 表示第 $t$ 次逆操作后的”权重”，因为我们发现一次逆操作对 $a_i$ 的影响有两种情况：

  • 除了那一轮的 $b_1$，其他的 $a$ 都加一，对应 $\beta_t=1$
  • 全部都不加，对应 $\beta_t=0$。

进行完第 $t$ 次逆操作时的 $b_1$（我们记为 $b_1^{(t)}$ ）为 $1$ 时，$\beta_t=0$，反之则为 $1$。同样的，进行完第 $t$ 次逆操作时的 $b_i$ 所对应的 $a_i$，我们记为 $a_i^{(t)}$，其构成的向量组 $\alpha^{(t)}$ 同理。那么我们可以把 $\beta_i$ 严谨定义为：

\[\beta_i=r(b_1^{i})\]

接下来我们给每个矩阵一个符号，即有：

\(\alpha^{(t+1)} = L \alpha^{(t)} + \beta_t u\) 也就有：

\[\begin{align} &\alpha^{(0)}=0\\ &\alpha^{(1)} = \beta_0 u\\ &\alpha^{(2)} = L(\beta_0 u) + \beta_1 u = \beta_0 L u + \beta_1 u\\ &\alpha^{(3)} = L(a^{(2)}) + \beta_2 u = \beta_0L^2u+\beta_1Lu+\beta_2u\\ &...\\ &\alpha^{(n+1)} = \sum_{k=0}^n \beta_k L^{n-k} u= \beta_0 L^n u + \beta_1 L^{n-1} u + \dots + \beta_n u \end{align}\]

回忆我们上面提到的 $L^n=\mathbf{id}$，我们最终得到：

\[\alpha^{(n+1)} =\beta_0u + \beta_1 L^{n-1} u + \dots + \beta_n u\]

我们把 $L^xu$ 放在一起看，归纳一下，可以得到：

\[(L^{n-k} u)_i = \begin{cases} 0, & i \equiv n-k+1 \pmod n \\ 1, & \text{otherwise} \end{cases}\]

现在我们来求每一个分量 $a_i$。注意到，在 $L$ 的影响下，每一个分量实际上是 $\beta_i$ 的线性组合，即：

\[\begin{align} &a_1^{(n+1)} = \beta_0 + \beta_2 + \dots + \beta_{n} \pmod 2\\ &a_2^{(n+1)} = \beta_1 + \beta_3 + \dots + \beta_0 \pmod 2\\ &a_3^{(n+1)} = \beta_2 + \beta_4 + \dots + \beta_1 \pmod 2\\ &... \end{align}\]

$\beta$ 的下标的取值应该是 $[0,n]$ ，超出的话就取模。另外，我们上面也提到了 $r^2=\mathbf{id}$，所以我们也可以把 $a_i$ 放在 $\pmod 2$ 空间下考虑。总结一下，也就是说：

\[a_i^{(n+1)} =\sum_{k=0}^n \beta_k - \beta_i \pmod 2\]

在 $\pmod 2$ 空间下，$-\beta_i$ 相当于 $+\beta_i$，所以：

\[a_i^{(n+1)} =\sum_{k=0}^n \beta_k + \beta_i \pmod 2\]

现在，我们就把求 $a_i$ 的问题转化成求 $\beta$ 的问题了

$\beta$ 分析

我们来进一步分析一下 $\beta_t$，这里 $t$ 的定义和上面一样

\[\beta_t = r(b_1^{(t)})\equiv b_1^{(t)}+1 \pmod 2\]

我们从 $t=0$ 开始考虑：

\[\beta_0 = b_1^{(0)} + 1\pmod 2\]

$t=1$ 时，$b_1^{(1)}=r^{a_1^{(1)}}(b_2^{(0)}) = b_2^{(0)} + a_1^{(1)} \pmod 2$ ，那么就有（为了方便书写，我们下面把第 $b^{(0)}_i$ 写为 $x_i$）

\[\beta_1 = b_1^{(1)} + 1 \equiv x_2 + \beta_0 + 1 \pmod 2\]

同理可得 $t=2$ 时，有

\[\beta_2 = x_3 + \beta_0 +\beta_1+1\pmod 2\]

归纳可得递推公式（归纳过程略）：

\[\beta_t = x_{t+1} + \sum_{k=0}^{t-1} \beta_k + 1\pmod 2\]

注意到下面这个式子可以求出 $\beta_t$ 的通项公式

\[\beta_t + \beta_{t-1} = \left( x_{t+1} + \sum_{k=0}^{t-1} \beta_k + 1 \right) + \left( x_t + \sum_{k=0}^{t-2} \beta_k + 1 \right)\]

注意这里是模二，所以展开后系数为 $2$ 的项全部没了，只剩下

\[\begin{align} &\beta_t + \beta_{t-1}=x_{t}+x_{t-1}+\beta_{t-1} \end{align}\]

最终，我们得到了 $\beta_t$ 的通项公式

\[\beta_t=x_t+x_{t-1}\]

终结 $a_i^{(n+1)}$

回忆一下，我们有：

\[a_i = \left( \sum_{k=0}^n \beta_k \right) + \beta_i \pmod 2\]

代入 $\beta_t$ 的通项公式，也就有（注意一下 $\beta_0$ 的特殊性）：

\[\begin{align} a_i=& (x_1+x_n)+(x_2+x_1)+\cdots+(x_n+x_{n-1})+(x_i+x_{i-1})\equiv x_i+x_{i-1}\mod 2 \end{align}\]

现在我们将 $a_i$ 代入回我们一开始写的公式里：

\[f^{-(n+1)}(b)=r^{a_1}(b_1)r^{a_n}(b_n)\cdots r^{a_2}(b_2)\]

回忆一下我们一开始引入 $r$ 时候提到的公式，代入后，每一位即为：

\[b_i^{(n+1)}=x_{i+1}+a_i^{(n+1)}=x_{i+1}+x_{i+1}+x_i\equiv x_i\mod 2\]

证毕

感想

这道题从表面看是一个排列与置换的问题，但深入后发现其本质是二进制上的线性变换。（学了这么多线性代数，这回总算派上用场了）从二进制这个视角看问题，在某些情况下或许会是一个非常有力的工具。