2024年10月北京人大附中高三月考数学试卷 #21
已知集合\[\Omega_n=\left\{X\mid X=\left(x_1,x_2,\cdots,x_n\right),x_i\in\{0,1\},i=1,2,\cdots,n\right\},\]对于任意 $X\in\Omega_n$，
操作一：选择 $X$ 中某个位置（某两个数之间或第一个数之前或最后一个数之后），插入连续 $k$ 个 $1$ 或连续 $k$ 个 $0$，得到 $Y\in\Omega_{n+k}$（$k\geqslant 1$）；
操作二：删去 $X$ 中连续 $k$ 个 $1$ 或连续 $k$ 个 $0$，得到 $Y\in\Omega_{n-k}$（$1\leqslant k\leqslant n-1$）；
进行 $1$ 次操作一或者操作二均称为 $1$ 次变换，在第 $n$ 次（$n\in\mathbb N^{\ast}$）变换的结果上再进行 $1$ 次变换称为第 $n+1$ 次变换．
1、若对 $X=(0,1,0)$ 进行两次变换，依次得到 $Y\in\Omega_4$，$Z\in\Omega_2$．直接写出 $Y$ 和 $Z$ 的所有可能情况．
2、对于 $X=\underbrace{(0,0,\cdots,0)\in\Omega_{100}}_{100~\text{个}~0}$ 和 $Y=\underbrace{(0,1,0,1,\cdots,0,1)\in\Omega_{100}}_{50~\text{组}~0,1}$ 至少要对 $X$ 进行多少次变换才能得到 $Y$？说明理由．
3、证明：对任意 $X,Y\in\Omega_{2 n}$，总能对 $X$ 进行不超过 $n+1$ 次变换得到 $Y$．
解析
1、根据题意，有\[\begin{array}{c|c|c}\hline \text{情形}&Y&Z\\ \hline 1&(0,0,1,0)&(1,0)\\ \hline 2&(0,1,1,0)&(0,0)\\ \hline 3&(0,1,0,0)&(0,1)\\ \hline\end{array}\]
2、对 $A\in \Omega_n$，且 $A=(a_1,a_2,\cdots,a_n)$，定义\[S(A)=\sum_{k=2}^n|x_k-x_{k-1}|,\]即将序列 $A$ 中连续的 $0$ 或者 $1$ 看作“段落”，$S(A)$ 即 $X$ 中的段落总数．设 $A$ 经过 $1$ 次操作一后得到 $A_1$，经过 $1$ 次操作二后得到 $A_2$，则\[S(A_1)-S(A)=0,1,2,\quad S(A_2)-S(A)=0,-1,-2,\]而 $S(X)=1$，$S(Y)=100$，因此至少需要 $50$ 次变换． 若 $X$ 经过 $50$ 次变换后得到 $Y$，则这 $50$ 次变换均为操作一且每次均插入均为段落 $1\cdots$，此时操作一不会改变序列中的 $0$ 的个数，因此不可能． 下面给出 $X$ 经过 $51$ 次变换后得到 $Y$ 的构造：第 $k$（$k=1,2,\cdots,50$）变换依次在序列中第 $k$ 个 $0$ 后增加一个 $1$，第 $51$ 次变换把序列最后的 $50$ 个 $0$ 全部删除即可． 综上所述，至少需要 $51$ 次变换．
3、设 $X,Y$ 中的段落数分别为 $a,b$，由于变换可逆，于是不妨设 $1\leqslant b\leqslant a\leqslant 2$，进一步由于问题关于 $0,1$ 对称，于是不妨设 $Y$ 中的段落 $0\cdots$ 数不超过段落 $1\cdots$ 数，即 $Y$ 中段落 $0\cdots$ 数不超过 $\dfrac b2$． 如果 $X$ 不含 $ 1$，则只需要一次操作使 $X$ 含 $1 $ 的个数与 $Y$ 相等且第一个段落类型一致，然后再插入至多 $\dfrac{b}{2}-1$ 个连续的 $0$ 构成的段落，最后清除末尾多余的 $0$ 即可，由\[\dfrac{b}{2}+1 \leqslant \dfrac{2 n}{2}+1=n+1,\]知结论成立． 下面考虑 $X$ 含 $1$ 的情况，进行如下操作：
第一步 如果 $X$ 的 1 的个数小于 $Y$，则在 $X$ 的任意一个 $1$ 右侧增加若干个 $ 1$ 使得二者含 $1$ 数量相等，否则跳过该步骤； [[sol]]第二步[[/sol]]我们不断对 $X$ 进行增加或删除连续若干个 $ 0$ 的操作． [[sol]]准备工作[[/sol]]如果 $X$ 和 $Y$ 开头的数码不同，则在开头增加或删去若干个 $0$，否则跳过该步骤． 然后反复进行以下步骤：
情况一 如果当前的 $X$ 的第一个和 $Y$ 不一致的段落对应的数字是由 $1$ 组成的，则在 $X$ 的该段落中间添加若干个 $ 0$（数量与 $Y$ 的下一个段落的 $0$ 的个数相等），或者在该段落末尾删去 $X$ 的下一个由 $ 0 $ 组成的段落；
情况二 如果当前的 $X$ 的第一个和 $Y$ 不一致的段落对应的数字是由 $ 0 $ 组成的，则在 $X$ 的该段落中间添加或删去若干个 $0$，使得该段的 $ 0 $ 的个数与 $Y$ 的该段落的 $ 0$ 的个数相等． 如此反复后，如果第一步进行了操作，则最终 $X$ 和 $Y$ 一致；如果第一步没有进行操作，则最终 $X$ 相比 $Y$ 在末尾多出若干个 $1$．
第三步 如果 $X$ 相比 $Y$ 在末尾多出若干个 $ 1$，则删除多余的 $ 1$，否则跳过该步骤． 至此，我们就将 $X$ 操作变成了 $Y$． 由于每执行一次第二步的操作时，使得段落数增加 $ 1$ 的准备工作和段落数减少 $2 $ 的删除 $0$ 的操作的总次数不超过 $\dfrac{a-b+1}{2}$，而增加 $ 0$ 的操作的次数不超过 $\dfrac{b}{2}$，同时第一步和第三步不可能同时进行操作，所以总的操作次数不会超过\[\frac{a-b+1}{2}+\frac{b}{2}+1=\frac{a}{2}+\frac{3}{2} \leqslant \frac{2 n}{2}+\frac{3}{2}=n+1+\frac{1}{2},\]故需要的操作次数不超过 $n+1$，命题得证．