高中奥数 2022-01-01

2022-01-01 本文已影响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}$ .

但这时,将导致

$2^{n-1}=\sum\limits_{j=1}^{n-1}\left|A_{j}\right|\leqslant \sum\limits_{j=1}^{n-1}2^{n-1-j}=1+2+\cdots+2^{n-2}=2^{n-1}-1.$

矛盾.所以,命题对 $n$ 成立.

综上可知,命题获证.

说明

这里在证命题对 $n$ 成立时,采用的是反证法,在运用数学归纳法证明问题时应充分地与其他证明方法结合.

高中奥数 2022-01-01

猜你喜欢

热点阅读