高中奥数 2022-01-12

作者: 不为竞赛学奥数 | 来源:发表于2022-01-12 16:10 被阅读0次

高中奥数 2022-01-12
奥数！奥数！
高中奥数 2022-03-16
高中奥数 2022-03-14
高中奥数 2022-02-17
高中奥数 2022-02-24
高中奥数 2022-02-25
高中奥数 2022-03-11
高中奥数 2022-03-10
高中奥数 2022-03-13

2022-01-12-01

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

用 $A_{n}$ 表示一些由 $a$ 、 $b$ 、 $c$ 组成的字长为 $n$ 的词组成的集合,其中每一个词中都没有连续两个字同时为 $a$ 或者同时为 $b$ ; $B_{n}$ 表示一些由 $a$ 、 $b$ 、 $c$ 组成的字长为 $n$ 的词组成的集合,其中每一个词中都没有连续的三个字是两两不同的.证明:对任意正整数 $n$ ,都有 $\left|B_{n+1}\right|=3\left|A_{n}\right|$ .

证明

我们采用递推的方法来处理.

用 $c_{n}$ 表示集合 $A_{n}$ 中以 $c$ 开头的词的个数, $d_{n}$ 表示以 $a$ 或 $b$ 开头的词的个数.

对于 $A_{n+1}$ 中的词,依第1个字分类,如果为 $c$ ,那么去掉它后所得的词仍属于 $A_{n}$ ;如果为 $a$ ,那么第2个字为 $c$ 或 $b$ ;如果为 $b$ ,那么第2个字为 $c$ 或 $a$ .所以,成立如下递推关系式

$\begin{cases} c_{n+1}=\left|A_{n}\right|=c_{n}+d_{n},\\ d_{n+1}=2c_{n}+d_{n}. \end{cases}\qquad(1)$

再用 $c_{n}^{\prime}$ 表示 $B_{n}$ 中最前面的两个字相同的词的个数, $d_{n}^{\prime}$ 表示 $B_{n}$ 中最前面的两个字不同的词的个数.

对于 $B_{n+1}$ 中的词,我们依最前面的两个字是否相同分类.如果相同,那么第3个字可以任取,此时,去掉第1个字后,所得词属于 $B_{n}$ ;如果不同,那么第3个字与前面两个字中的某一个相同,在与第1个字相同时,去掉第1个字后,共有 $d_{n}^{\prime}$ 个词.在与第2个字相同时,去掉第1个字后,共有 $2c_{n}^{\prime}$ 个词(这里系数为2是因为 $abb\cdots$ 与 $cbb\cdots$ 去掉第1个字后所得的词相同),所以,它们之间的递推关系式为

$\begin{cases} c_{n+1}^{\prime}=\left|B_{n}\right|=c_{n}^{\prime}+d_{n}^{\prime},\\ d_{n+1}^{\prime}=2c_{n}^{\prime}+d_{n}^{\prime}. \end{cases}\qquad(2)$

注意到,递推关系式(1)与(2)完全相同,不同的只是它们的初始条件.直接枚举可知 $c_{1}=1$ , $d_{1}=2$ ; $c_{2}^{\prime}=3$ , $d_{2}^{\prime}=6$ .因此 $c_{2}^{\prime}=3c_{1}$ , $d_{2}^{\prime}=3d_{1}$ ,从而由递推关系式,可知 $c_{n+1}^{\prime}=3c_{n}$ , $d_{n+1}^{\prime}=3d_{n}$ .结合 $\left|A_{n}\right|=c_{n+1}$ 及 $\left|B_{n}\right|=c^{\prime}_{n+1}$ ,可得 $\left|B_{n+1}\right|=3\left|A_{n}\right|$ .

命题获证.

说明利用递推思想处理组合计数问题是一个重要的方法.这里建立的递推式可化为常系数齐次线性递推关系,可求解出 $\left|A_{n}\right|$ 的具体数值.

2022-01-12-02

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

实数数列 $\left\{a_{n}\right\}$ 满足:对任意不同的正整数 $i$ 、 $j$ ,都有 $\left|a_{i}-a_{j}\right|\geqslant\dfrac{1}{i+j}$ ,且存在正实数 $c$ ,使得对任意 $n\in \mathbb{N}^{*}$ ,都有 $0\leqslant a_{n}\leqslant c$ .

求证: $c\leqslant 1$ .

证明

此题不是以等式形式给出的数列各项之间的关系,它只是用一个不等式刻画了项与项之间的差距.整个解决过程有一定的分析味道,基于裂项求和的思想.

对 $n\geqslant 2$ ,设 $\pi\left(1\right),\cdots ,\pi\left(n\right)$ 是 $1,2,\cdots ,n$ 的一个排列,使得

$0\leqslant a_{\pi\left(1\right)}<a_{\pi\left(2\right)}<\cdots <a_{\pi\left(n\right)}\leqslant c.$

注意,由条件可知 $\left\{a_{n}\right\}$ 中任意两项不同,而(1)只是将 $a_{1},\cdots ,a_{n}$ 从小到大作了一个排列.

利用(1)及条件,可知

$\begin{aligned} c&\geqslant a_{\pi\left(n\right)}-a_{\pi\left(1\right)}\\ &=\sum\limits_{k=1}^{n-1}a_{\pi\left(k+1\right)}-a_{\pi\left(k+1\right)}\\ &\geqslant \sum\limits_{k=1}^{n-1}\dfrac{1}{\pi\left(k+1\right)+\pi\left(k\right)}. \end{aligned}$

由Cauchy不等式,知

$\begin{aligned} & \sum\limits_{k=1}^{n-1} \dfrac{1}{\pi(k+1)+\pi(k)} \\ \geqslant& \dfrac{(n-1)^{2}}{\sum\limits_{k=1}^{n-1}(\pi(k+1)+\pi(k))} \\ =& \dfrac{(n-1)^{2}}{2 \sum\limits_{k=1}^{n} \pi(k)-\pi(1)-\pi(n)}\\ =&\dfrac{(n-1)^{2}}{n(n+1)-\pi(1)-\pi(n)} \\ \geqslant & \dfrac{(n-1)^{2}}{n(n+1)-1-2}\\ >&\dfrac{(n-1)^{2}}{n(n+1)-2}\\ =&\frac{n-1}{n+2}\\ =&1-\frac{3}{n+2} . \end{aligned}$

所以,我们有

$c\geqslant 1-\dfrac{3}{n+2}.$

令 $n\rightarrow\infty$ ,即可得 $c\geqslant 1$ .

命题获证.

2022-01-12-03

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

由实数组成的无穷数列 $\left\{a_{n}\right\}$ 定义如下: $a_{0}$ 、 $a_{1}$ 是两个不同的正实数,且 $a_{n}=\left|a_{n+1}-a_{n+2}\right|$ , $n=0,1,2,\cdots$ .问:该数列是否可能是一个有界数列?证明你的结论.

解

此数列一定是一个无界数列.证明的基本思想是从 $\left\{a_{n}\right\}$ 中取出一个递增的无界数列.

事实上,如果存在 $n\in \mathbb{N}^{*}$ ,使得 $a_{n}=a_{n+1}$ ,则由递推关系式,知a $_{n-1}=0$ ,进而 $a_{n-2}=a_{n-3}$ (注意,这里用到 $\left\{a_{n}\right\}$ 的每一项都是非负实数),这样依次倒推,可知 $a_{1}=a_{2}$ 或者 $a_{1}$ 、 $a_{2}$ 中有一个等于零,但这与 $a_{1}$ 、 $a_{2}$ 是两个不同的正实数矛盾.因此,对任意 $n\in \mathbb{N}^{*}$ ,都有 $a_{n}\ne a_{n+1}$ (即 $\left\{a_{n}\right\}$ 中没有相邻两项是相等的),从而结合递推式知,对任意 $n\in \mathbb{N}^{*}$ ,都有 $a_{n}>0$ .

现在我们来从 $\left\{a_{n}\right\}$ 中挑出一个递增的子数列 $\left\{b_{m}\right\}$ .

由条件,知 $a_{n+2}=a_{n}+a_{n+1}$ 或 $a_{n+2}=a_{n+1}-a_{n}$ 若为前者,则 $a_{n+2}>a_{n+1}$ ;若为后者,则 $a_{n+2}<a_{n+1}$ ,此时,由 $a_{n+2}=a_{n+1}-a_{n}$ 知,必有 $a_{n+3}=a_{n+2}+a_{n+1}$ (否则 $a_{n+3}=a_{n+2}-a_{n+1}<0$ ,矛盾),这表明 $a_{n+3}>a_{n+1}$ .这一段讨论表明:要么 $a_{n+2}>a_{n+1}$ ,要么 $a_{n+2}<a_{n+1}<a_{n+3}$ .

利用上述结论,我们从数列 $\left\{a_{n}\right\}$ 去掉所有满足 $a_{n+1}<a_{n}$ ,且 $a_{n+1}<a_{n+2}$ (注意,当 $n\geqslant 2$ 时,将有 $a_{n+2}>a_{n}$ )的项 $a_{n+1}$ ,当然,如果 $a_{1}>a_{2}$ ,那么去掉 $a_{1}$ 保留 $a_{2}$ 后再做去项操作.这样留下的项依次记为 $b_{1},b_{2},\cdots$ 所得数列 $\left\{b_{m}\right\}$ 是一个递增数列.

最后,我们证明: $\left\{b_{m}\right\}$ 为无界数列.

只需证明:对任意 $m\in \mathbb{N}^{*}$ , $b_{m+2}-b_{m+1}\geqslant b_{m+1}-b_{m}$ (因为这时,利用裂项求和可得 $b_{m+2}-b_{2}\geqslant m\left(b_{2}-b_{1}\right)$ ,让 $m\rightarrow +\infty$ ,即可知 $\left\{b_{m}\right\}$ 为无界数列).

由 $\left\{b_{m}\right\}$ 的定义,可设 $b_{m+2}=a_{n+2}$ (注意 $n$ 不一定为 $m$ ),则由于 $a_{n+2}$ 是未被去掉的项,故 $a_{n+2}>a_{n+1}$ ,如果 $a_{n+1}>a_{n}$ ,那么 $b_{m+1}=a_{n+1}$ ,而 $b_{m}=a_{n}$ 或者 $a_{n-1}$ (若为前者,则 $a_{n}>a_{n-1}$ ),于是,总有 $b_{m}\geqslant a_{n-1}$ ,得

$b_{m+2}-b_{m+1}=a_{n+2}-a_{n+1}=a_{n}=a_{n+1}-a_{n-1}\geqslant b_{m+1}-b_{m}.$

如果 $a_{n+1}<a_{n}$ ,那么 $b_{m+1}=a_{n}$ ,而 $b_{m}=a_{n-1}$ 或者 $a_{n-2}$ (若为后者,则 $a_{n-2}>a_{n-1}$ ,否则 $a_{n-1}$ 不是去掉的项),所以

$b_{m+2}-b_{m+1}=a_{n+2}-a_{n}=a_{n+1}=a_{n}-a_{n-1}\geqslant b_{m+1}-b_{m}.$

命题获证.

2022-01-12-04

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

数列 $\left\{a_{n}\right\}$ 满足递推式

$a_{n+1}=\dfrac{a_n^{2}-1}{n+1},n=0,1,2,\cdots$

问:是否存在正实数 $a$ ,使得下面的结论都成立?

(1)若 $a_{0}\geqslant a$ ,则极限 $\lim\limits_{n\rightarrow\infty}a_{n}$ 不存在;

(2)若 $0<a_{0}<a$ ,则 $\lim\limits_{n\rightarrow\infty}a_{n}=0$ .

解

存在满足条件的正实数 $a$ ,这个 $a=2$ .题目的解答过程中会不断用到数学归纳法,其中的详细推导请读者自己完成.

(1)当 $a_{0}\geqslant 2$ 时,利用数学归纳法可证:对 $n\geqslant 0$ ,都有 $a_{n}\geqslant n+2$ ,故此时 $\lim\limits_{n\rightarrow\infty}a_{n}$ 不存在.

(2)对 $0<a_{0}<a$ ,我们分两种情形处理:

情形一

$0<a_{0}\leqslant 1$ ,此时利用数学归纳法可证:对任意 $n\in \mathbb{N}^{*}$ ,都有 $\left|a_{n}\right|\leqslant \dfrac{1}{n}$ ;故 $\lim\limits_{n\rightarrow\infty}a_{n}=0$ .

情形二

$1<a_{0}<2$ ,如果存在 $m\in \mathbb{N}^{*}$ ,使得 $a_{m+1}\leqslant 0$ ,那么取最小的 $m$ ,则 $0<a_{m}\leqslant 1$ ,此时 $\left|a_{m+1}\right|=\dfrac{1-a_{m}^{2}}{m+1}\leqslant \dfrac{1}{m+1}$ ,依此结合数学归纳法可证:当 $n\geqslant m+1$ 时,都有 $\left|a_{n}\right|\leqslant \dfrac{1}{n}$ ,从而 $\lim\limits_{n\rightarrow\infty}a_{n}=0$ .

最后,若对任意 $m\in \mathbb{N}^{*}$ ,都有 $a_{m}>0$ ,结合 $1<a_{0}<2$ 可知,对 $n\geqslant 0$ 都有 $a_{n}>1$ .现在设 $a_{0}=2-\varepsilon\left(0<\alpha,-1\right)$ ,利用递推式及数学归纳法可证:对意 $n\in \mathbb{N}^{*}$ , $a_{n}<n+2-n\varepsilon$ .因此,取 $m=\left[\dfrac{1}{\varepsilon}\right]$ ,则有 $a_{m}<m+2-m\varepsilon\leqslant m+1$ ,然后,再用数学归纳法可证:对任意 $n>m$ ,都有 $a_{n}\leqslant\dfrac{\left(m+1\right)^{2}-1}{n-1}$ ,这在 $n$ 充分大时,导致 $a_{n}\leqslant 1$ ,矛盾.因此,必存在 $n\in \mathbb{N}^{*}$ ,使得 $a_{n}\leqslant 0$ ,归入前面的情形.