每日一题[3614]转录与翻译

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$，命题得证．