高中奥数 2022-01-01

作者: 天目春辉 | 来源:发表于2022-01-01 09:05 被阅读0次

2022-01-01-01

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚第二数学归纳法 P011 例6）

设 $n\in \mathbb{N}^{*}$ ,函数 $f:\left\{1,2,3,\cdots,2^{n-1}\right\}\rightarrow\mathbb{N}^{*}$ 满足:对 $1\leqslant i\leqslant 2^{n-1}$ ,都有 $1\leqslant f\left(i\right)\leqslant i$ .证明:存在一个正整数数列 $a_{1},a_{2},\cdots ,a_{n}$ ,使得 $1\leqslant a_{1}<a_{2}<\cdots <a_{n}\leqslant 2^{n-1}$ ,且 $f\left(a_{1}\right)\leqslant \cdots\leqslant f\left(a_{n}\right)$ .

证明

对 $n$ 运用数学归纳法.

当 $n=1$ 时,命题显然成立.

现设命题对 $1,2,\cdots ,n-1$ 都成立,考察 $n$ 的情形.

对 $1\leqslant i\leqslant 2^{n-1}$ ,我们用 $t\left(i\right)$ 表示满足下述条件的最大正整数 $m$ :

存在正整数数列 $i=a_{1}<a_{2}<\cdots <a_{m}\leqslant 2^{n-1}$ ,使得

$f\left(a_{1}\right)\leqslant f\left(a_{2}\right)\leqslant \cdots\leqslant\left(a_{m}\right).$

如果命题对 $n$ 不成立,那么由 $t\left(1\right)=\max_{2}t\left(i\right)$ 可知,对任意 $1\leqslant i\leqslant 2^{n-1}$ 都有 $t\left(i\right)\leqslant n-1$ .记 $A_{j}=\left\{i\vert 1\leqslant i\leqslant 2^{n-1},t\left(i\right)=j\right\}$ , $j=1,2,\cdots n-1$ ,则任意两个 $A_{j}$ 不交,且 $\bigcup\limits_{j=1}^{n-1}A_{j}=\left\{1,2,3,\cdots,2^{n-1}\right\}$ ,所以 $\sum\limits_{j=1}^{n-1}\left|A_{j}\right|=2^{n-1}$ .

下面先证明:对任意 $1\leqslant j\leqslant n-1$ ,都有 $\left|A_{j}\right|\leqslant 2^{x-j-1}$ .

事实上,若存在 $j$ ,使得 $\left|A_{j}\right|> 2^{x-j-1}$ ,则存在 $1\leqslant i_{1}<i_{2}<\cdots <i_{r}\leqslant 2^{n-1}$ ,使得 $t\left(i_{1}\right)=t\left(i_{2}\right)=\cdots=t\left(i_{r}\right)=j$ ,这里 $r=2^{n-j-1}+1$ .这时,对任意 $1\leqslant p<q\leqslant r$ ,都应有 $f\left(i_{p}\right)>f\left(i_{q}\right)$ (否则,若 $f\left(i_{p}\right)\leqslant f\left(i_{q}\right)$ ,则在从 $i_{q}$ 出发的递增f数列的前面加入 $f\left(i_{p}\right)$ ,将导致 $t\left(i_{p}\right)\geqslant t\left(i_{q}\right)+1$ ,矛盾),故 $f\left(i_{1}\right)>f\left(i_{2}\right)>\cdots >f\left(i_{r}\right)$ ,进而 $f\left(i_{1}\right)\geqslant r=2^{n-j-1}+1$ ,结合 $1\leqslant f\left(i_{1}\right)\leqslant i_{1}$ ,得 $i_{1}\geqslant 2^{n-f-1}+1$ .

现在,由 $t\left(i_{1}\right)$ 的定义知,存在 $i_{1}=a_{1}<\cdots <a_{j}\leqslant 2^{n-1}$ ,使得 $f\left(a_{1}\right)\leqslant \cdot≤f\left(a_{j}\right)$ ,而由归纳假设可知,在 $\left\{1,2,3,\cdots ,2^{n-j-1}\right\}$ 中存在 $1\leqslant b_{1}<\cdots <b_{n-j}\leqslant \leqslant 2^{n-1-j}<i_{1}=a_{1}$ ,使得 $f\left(b_{1}\right)\leqslant \cdots\leqslant f\left(b_{m-j}\right)$ ,再结合 $f\left(b_{n-j}\right)\leqslant b_{n-j}\leqslant 2^{n-1-j}<r\leqslant f\left(i_{1}\right)=f\left(a_{1}\right)$ ,可知 $1\leqslant b_{1}<\cdots<b_{n-j}<a_{1}<a_{2}<\cdots<a_{j}\leqslant 2^{n-1}$ ,并且 $f\left(b_{1}\right)\leqslant\cdots\leqslant f\left(b_{n-j}\right)\leqslant f\left(a_{1}\right)\leqslant \cdots\leqslant f\left(a_{j}\right)$ ,这与 $n$ 时命题不成立的假设矛盾.所以 $\sum\limits_{j=1}^{n-1}\left|A_{j}\right|=2^{n-1}$ .