2019年第60届IMO试题

• 知识点

  >

  二试组合部分

略

证法一
（1）假设哈利有个无聊的好朋友叫波特，波特也无聊地做另一种操作：
假设有 $k$ 枚硬币 $H$ 朝上，那么波特将从左至右的第 $k+1$ 枚硬币翻转过来．
我们将通过归纳法证明：哈利可以在有限次操作之后将硬币全部变成 $T$ 朝上，而波特可以在有限次操作之后将硬币全部变成 $H$ 朝上．
当 $n=1$ 时，显然．
若 $n-1$ 时成立，在 $n$ 枚硬币的情况下．
对哈利来说，如果 $n$ 枚硬币中最右一枚是 $T$，那么此时我们完全可以忽略最右一枚 $T$，前面 $n-1$ 枚硬币可以通过有限次全部变成 $T$．
而若最右一枚硬币是 $H$ 的时候，哈利在这种情况下做的操作等价于波特在 $n-1$ 的情况下做的操作，所以哈利可以在有限次之后将硬币全部变成 $H$．
接下来，由于全部硬币都是 $H$ 朝上，哈利将把翻转最右一枚硬币，成 $H \ldots HT$，此时由前面知道哈利将在有限次将所有硬币变成 $T$．
对波特来说，若左边第一枚硬币是 $H$，我们考虑一个镜像的世界，在镜像的世界中伏地魔有一排硬币，且右起的第 $i$ 枚硬币改好是波特手中左起第 $i$ 枚硬币的反面，那么这个时候伏地魔手中的硬币应该为 $\ldots T$ 的形式．
若此时波特手上有 $k$ 枚 $H$ 朝上，那么这个时候伏地魔手上有 $n-k$ 枚 $T$ 朝上，波特操作的时候将左起第 $k+1$ 枚硬币反过来，那么伏地魔则将右起第 $k+1$ 枚硬币反过来，即将左起 $n+1-(k+1)=n-k$ 枚硬币反过来．
也就是说伏地魔的操作即是哈利在刚好搞反所有 $HT$ 时候的操作．
那么由上一段，我们知道哈利可以将所有硬币变成 $H$（注意这句话中哈利把所有 $HT$ 都搞反了），也就是说伏地魔可以将所有硬币变成 $T$，也就是说镜像中的波特可以将所有硬币变成 $H$．
而若左边第一枚硬币是 $T$，那么波特所做的所有操作，等价于在忽略第一枚硬币的时候哈利在 $n-1$ 的情况下所做的操作，那么在经过有限次之后波特可以将所有硬币都变成 $T$．
接下来由于没有 $H$ 朝上的硬币，波特将把第一枚硬币变成 $H$，即 $HT\ldots T$ 的状态．
那么接下来波特将通过 $(HTT \ldots T)\rightarrow(HHT \ldots T)\rightarrow(HHH \ldots T)\rightarrow\ldots\rightarrow(HHH \ldots H)$ 将所有硬币变成 $H$ 朝上．
（2）记 $n$ 枚硬币的时候题设中的平均值为 $a_n$，而波特对应的平均值是 $b_n$，我们现在考虑 $a_n,b_n$ 的递推公式．
首先 $a_1 =b_1 =\frac{1}{2}\times (1+0)=\frac{1}{2}$．
在 $n$ 的情况中，按照第一问我们分两种情况考虑，若哈利手中最右一枚硬币是 $T$，那么这 $2^{n-1}$ 种情况与 $n-1$ 时的情况一模一样．
若哈利手中最右一枚硬币是 $H$，那么在先将所有硬币变为 $H$ 之后，哈利再通过 $(H \ldots HH)\rightarrow(H \ldots HT)\rightarrow\ldots\rightarrow(T \ldots TT)$ 一共 $n$ 步变为全 $T$，也就是说 $a_n =\dfrac{1}{2^n}\times\left(2^{n-1} a_{n-1} + 2^{n-1} (b_{n-1}+n)\right)$ 而对于波特而言，若开始时波特手上最左的硬币为 $H$，这个时候波特将通过伏地魔的方法将硬币变成 $H$ 之后全 $H$，而伏地魔的方法完全等价于哈利在 $n-1$ 时候的方法，此时平均下来每一种状态贡献的次数为 $a_{n-1}$．
而若开始时波特手上最左的硬币为 $T$ 时，波特将按照哈利的方法将硬币变为全 $T$，而后通过 $n$ 步将硬币全变为 $H$．
所以 $b_n =\dfrac{1}{2^n}\times\left(2^{n-1}a_{n-1}+2^{n-1} (a_{n-1}+n)\right)$
解出来有 $a_n =b_n =\dfrac{1}{4}n(n+1)$．
证法二
设 $V_n=\{H,T\}^n$ 是所有长度为 $n$ 的 $H-T$ 序列构成的集合，即所有 $2^n$ 种硬币序列的状态．对 $n$ 归纳证明：对任意 $C\in V_n,L(C)$ 有限，且 $\displaystyle \sum\limits_{C\in V_n}L(C)=2^{n-2}n(n+1)$．
当 $n=1$ 时，$V_1=\{H,T\},L(H)=1,L(T)=0$．当 $n=2$ 时，$V_2=\{HH,HT,TH,TT\}$，$L(HH)=2,L(HT)=3,L(TT)=0$，结论在 $n=1,2$ 时均成立．
假设 $n\geqslant 3$，且结论在 $n$ 较小时均成立．对两个 $H-T$ 序列 $A,B$，用 $A\cdot B$ 表示将 $A,B$ 按顺序拼接在一起得到的 $H-T$ 序列．令
$X=\{C\cdot T|C\in V_{n-1}\},Y=\{H\cdot C|C\in V_{n-1}\}$
$Z=\{T\cdot C\cdot H|C\in V_{n-2}\},W=\{H\cdot C\cdot T|C\in V_{n-2}\}$
显然 $V_n=X\bigcup Y\bigcup Z,X\bigcap Y=W$．
对 $C\cdot T\in X$，由于最后一位始终是 $T$，操作过程就如同只对 $C$ 进行操作，因此操作 $L(C)$ 次后全变为 $T$，故 $L(C\cdot T)=L(C)$．
对 $H\cdot C\in Y$，设 $C$ 中恰有 $k$ 个 $H$，则 $H\cdot C$ 中恰有 $k+1$ 个 $H$，而 $H\cdot C$ 的第 $k+1$ 位恰是 $C$ 中的第 $k$ 位，因为一开始的操作就如同只对 $C$ 进行操作，操作 $L(C)$ 次后变为 $HTT\cdot T$，再进行一次操作后全变为 $T$，故 $L(H\cdot C)=L(C)+1$．
对 $T\cdot C\cdot H\in Z$，设 $C$ 中恰有 $k$ 个 $H$，则 $T\cdot C\cdot H$ 中恰有 $k+1$ 个 $H$，而 $T\cdot C\cdot H$ 的第 $k+1$ 位恰是 $C$ 中的第 $k$ 位，因此一开始的操作就如同只对 $C$ 进行操作，在进行了 $L(C)$ 次操作后变为 $TT\cdots TH$，此后依次将第 $1,2,\cdots,n-1$ 个 $T$ 变为 $H$，再依次将第 $n,n-1,\cdots,1$ 个 $H$ 变为 $T$，操作停止，因此 $L(T\cdot C\cdot H)=L(C)+2n-1$．
对 $H\cdot C\cdot T\in W$，由前两种情形的讨论，我们有 $L(H\cdot C\cdot T)=L(H\cdot C)=L(C)+1$．
至此，已经证明了对每个 $C\in V_n,L(C)$ 是有限的．最后，利用归纳假设可得
$\begin{aligned}
\sum_{C\in V_n}&=\sum_{C\cdot T\in X}L(C\cdot T)+\sum_{H\cdot C\in Y}L(H\cdot C)+\sum_{T\cdot C\cdot H\in Z}L(T\cdot C\cdot H)-\sum_{H\cdot C\cdot T\in W}L(H\cdot C\cdot T)\\
&=\sum_{C\in V_{n-1}}L(C)+\sum_{C\in V_{n-1}}(L(C)+1)+\sum_{C\in V_{n-1}}(L(C)+2n-1)-\sum_{C\in V_{n-1}}(L(C)-1)\\
&=2\sum_{C\in V_{n-1}}L(C)+2^{n-1}+(2n-2)2^{n-2}=2\cdot 2^{n-3}(n-1)n+2n\cdot 2^{n-2}\\
&=2^{n-2}n(n+1)
\end{aligned}$
因此，所有 $L(C)$ 的平均值为 $\dfrac{1}{4}n(n+1)$．
证法二
若 $C$ 全为 $T$，则 $L(C)=0$．假设 $C$ 含有 $i$ 个 $H$，$0<i\leqslant n$，设 $H$ 所在位置为 $0<a_1<a_2<\cdot <a_i\leqslant n$．令 $a_0=0$，由于 $a_i\geqslant i$，故存在唯一的 $0<j\leqslant i$，满足 $a_{j-1}<i\leqslant a_j$．由操作方法可知，第 $1,\cdots,a_j-i$ 次操作依次将第 $i$ 位至第 $a_j-1$ 位上的 $T$ 改为 $H$，第 $a_j-i+1$ 次操作将 $a_j$ 位的 $H$ 改为 $T$，接着的 $a_j-i$ 次操作又依次将第 $a_j-1$ 位至第 $i$ 位上的 $H$ 改为 $T$．故经过总共 $2a_j-2i+1$ 次操作的结果恰将第 $a_j$ 位上的 $H$ 改为 $T$，视作第一组操作．重复上面过程，经过 $i$ 组操作后，所有 $H$ 都变为 $T$，因此结论（$a$）成立．
设第 $k$ 组的操作结果是将 $a_{j(k)}$ 位上的 $H$ 改为 $T$，第 $k$ 组操作开始前共有 $i+1-k$ 个 $H$，故第 $k$ 组操作共进行了 $2a_{j(k)}-2(i+1-k)+1$ 次操作．由于 $j(1),j(2),\cdots,j(i)$ 恰是 $1,2,\cdots,i$ 的排列，因此 $\displaystyle L(C)=\sum\limits_{k=1}^i(2a_j(k)-2(i+1-k)+1)=2\left(\sum_{k=1}^ia_k\right)-i^2$．
若设 $A=\{a_1,\cdots,a_i\}\subset\{1,2,\cdots,n\}$，并记 $S(A)$ 为 $A$ 中元素之和，则 $L(C)=2S(A)-|A|^2$，这对 $A=\varnothing$ 也成立．设 $\overline{A}=\{1,2,\cdots,n\}\setminus A$，则 $S(A)+S(\overline{A})=\dfrac{1}{2}n(n+1),|A|+|\overline{A}|=n$．
将 $A$ 与 $\overline{A}$ 配对计算，可知 $\displaystyle \sum\limits_AS(A)=2^{n-2}n(n+1),\sum\limits_A|A|=2^{n-1}n$．于是
$\begin{aligned}
\sum_CL(C)&=\sum_A2S(A)-\sum_A|A|^2\\
&=2^{n-1}n(n+1)-\sum_A|A|-\sum_A|A|(|A|-1)\\
&=2^{n-1}n(n+1)-2^{n-1}n-\sum_{i=0}^ni(i-1)C_n^i=2^{n-1}n^2-\sum_{k=0}^{n-2}n(n-1)C_{n-2}^k\\
&=2^{n-1}n^2-2^{n-2}n(n-1)=2^{n-2}(n^2+n)
\end{aligned}$
因此，所有 $L(C)$ 的平均值为 $\dfrac{1}{4}n(n+1)$．