高中奥数 2022-02-17

2022-02-17 本文已影响0人不为竞赛学奥数

2022-02-17-01

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

设 $a_{0}<a_{1}<\cdots<a_{n}$ , $a_{0},\cdots ,a_{n}$ 都是正整数.证明:

$\dfrac{1}{\left[a_{0},a_{1}\right]}+\dfrac{1}{\left[a_{1},a_{2}\right]}+\cdots+\dfrac{1}{\left[a_{n-1},a_{n}\right]}\leqslant 1-\dfrac{1}{2^{n}}.$

证明

用数学归纳法(对 $n$ 归纳)证明下述加强的命题:
$\dfrac{1}{\left[a_{0},a_{1}\right]}+\dfrac{1}{\left[a_{1},a_{2}\right]}+\cdots+\dfrac{1}{\left[a_{n-1},a_{n}\right]}\leqslant \dfrac{1}{a_{0}}\left(1-\dfrac{1}{2^{n}}\right).\qquad(*)$
当 $n=1$ 时,由条件 $a_{0}<a_{1}$ ,故 $\left[a_{0},a_{1}\right]\geqslant 2a_{0}$ ,于是 $\dfrac{1}{\left[a_{0},a_{1}\right]}\leqslant \dfrac{1}{2a_{0}}=\dfrac{1}{a}\left(1-\dfrac{1}{2}\right)$ ,故 $n=1$ 时,不等式 $(*)$ 成立.

设不等式 $(*)$ 在 $n$ 时成立,则对 $n+1$ 的情形,有
$\begin{aligned} &\dfrac{1}{\left[a_{0},a_{1}\right]}+\dfrac{1}{\left[a_{1},a_{2}\right]}+\cdots+\dfrac{1}{\left[a_{n},a_{n+1}\right]}\\ \leqslant &\dfrac{1}{\left[a_{0},a_{1}\right]}+\dfrac{1}{a_{1}}\left(1-\dfrac{1}{2^{n}}\right).\qquad(**) \end{aligned}$
如果 $a_{1}\geqslant 2a_{0}$ ,则 $(**)$ 式右边 $\leqslant \dfrac{1}{\left[a_{0},a_{1}\right]}+\dfrac{1}{a_{0}}\left(1-\dfrac{1}{2^{n}}\right)\leqslant \dfrac{1}{2a_{0}}\left(2-\dfrac{1}{2^{n}}\right)=\dfrac{1}{a_{0}}\left(1-\dfrac{1}{1-2^{n+1}}\right)$ ;如果 $a_{0}<a_{1}<2a_{0}$ ,则由 $\left(a_{0},a_{1}\right)\leqslant a_{1}-a_{0}$ ,可知 $(**)$ 式右边 $\leqslant \dfrac{a_{1}-a_{0}}{a_{0}a_{1}}+\dfrac{1}{a_{1}}\left(1-\dfrac{1}{2^{n}}\right)=\dfrac{1}{a_{0}}-\dfrac{1}{a_{1}\cdot 2^{n}}<\dfrac{1}{a_{0}}-\dfrac{1}{2a_{0}\cdot 2^{n}}=\dfrac{1}{a_{0}}\left(1-\dfrac{1}{2^{n+1}}\right)$ 所以,不等式 $(*)$ 对 $n+1$ 也成立.

2022-02-17-02

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

定义数列 $\left\{u_{n}\right\}_{n=0}^{+\infty}$ 如下: $u_{0}=0$ , $u_{1}=1$ ,且对任意 $n\in \mathbb{N}^{*}$ ,数 $u_{n+1}$ 是满足下述条件的最小正整数:

(1)对任意 $n\in \mathbb{N}^{*}$ , $u_{n+1}>u_{n}$ ;

(2)数 $u_{0},u_{1},\cdots ,u_{n+1}$ 中没有3个数成等差数列.

求 $u_{100}$ 的值.

解

设二进制表示下, $n=\left(a_{k}a_{k-1}\cdots a_{0}\right)_{2}$ ,这里 $a_{i}\in \left\{0,1\right\}$ , $a_{k}=1$ ,令 $t_{n}=\left(a_{k}a_{k-1}\cdots a_{0}\right)_{3}$ (为一个3进制表示下的正整数), $t_{0}=0$ .

我们用数学归纳法证明:对任意的 $n\in \mathbb{N}^{*}$ ,均有 $u_{n}=t_{n}$ .

当 $n=1$ 时,命题显然成立.设对任意的 $m<n$ ,均有 $u_{m}=t_{m}$ .下面证明 $u_{n}=t_{n}$ .

一方面,集合 $\left\{t_{0},t_{1},\cdots ,t_{n}\right\}$ 中无任意3个数成等差数列,这是因为对任意 $0\leqslant \alpha<\beta<\gamma\leqslant n$ ,若 $t_{\alpha}+t_{\gamma}=2t_{\beta}$ ,由于 $2t_{\beta}$ 在3进制表示下只出现数码0和2,所以 $t_{\alpha}$ 、 $t_{\gamma}$ 在3进制表示下相应的每个数码都需相同.从而 $t_{\alpha}=t_{\gamma}$ ,要求 $\alpha=\gamma$ ,矛盾.

上述讨论表明 $u_{n}\leqslant t_{n}$ .

另一方面,若 $u_{n}<t_{n}$ ,则由归纳假设知 $u_{n}\in \left\{t_{n-1}+1,\cdots ,t_{n}-1\right\}$ ,此时,在 $u_{n}$ 的三进制表示中,必出现数码2(因为仅出现数码0,1的3进制正整数 $\in \left\{t_{0},t_{1},\cdots \right\}$ ).所以,存在 $a$ 、 $b\in \mathbb{N}$ ,使得 $0\leqslant t_{a}<t_{b}<u_{n}$ 满足:

(1)如果在 $u_{n}$ 的3进制表示中,某一位为0(或者1),则在 $t_{a}$ , $t_{b}$ 的3进制表示中,同样位置上的数码也为0(或者1);

(2)如果在 $u_{n}$ 的3进制表示中,某一位为2,则t在该位上为0,而 $t_{a}$ 在该位上为1.

于是 $t_{a}+u_{n}=2t_{b}$ ,矛盾.所以 $u_{n}\geqslant t_{n}$ .

综上所述,可知 $u_{n}=t_{n}$ .鉴于 $100=\left(1100100\right)_{2}$ ,所以
$u_{100}=\left(1100100\right)_{3}=981.$

2022-02-17-03

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

正整数 $a$ 、 $b$ 、 $n\left(b>1\right)$ 满足 $\left(b^{n}-1\right)\mid a$ .

证明:在 $b$ 进制表示下,数 $a$ 的表示中至少出现 $n$ 个非零数码.

证明

在 $b$ 进制表示下予以讨论.

设能被 $b^{n}-1$ 整除的所有数中,其 $b$ 进制表示下出现的非零数字个数的最小值为 $s$ ,并在所有这些非零数字个数为 $s$ 的数中,取数码和最小的数 $A$ .

设 $A=a_{1}b^{n_{1}}+a_{2}b^{n_{2}}+\cdots+a_{s}b^{n_{s}}$ 为 $A$ 的 $b$ 进制表示,这里
$n_{1}>n_{2}>\cdot>n_{s}\geqslant 0,1\leqslant a_{i}<b,i=1,2,\cdots ,s$
下面证明 $n_{1},n_{2},\cdots ,n_{s}$ 构成模 $n$ 的完系,从而 $s\geqslant n$ .

一方面,设 $1\leqslant i<j\leqslant s$ ,若 $n_{i}\equiv n_{j}\equiv r\left(\bmod n\right)$ ,这里 $0\leqslant r\leqslant n-1$ .我们考察数
$B=A-a_{i}b^{n_{i}}-a_{j}b^{n_{j}}+\left(a_{i}+a_{j}\right)b_n^{n_{1}+r}.$
显然 $b^{n}-1\mid B$ .若 $a_{i}+a_{j}<b$ ,则 $B$ 的非零数字的个数为 $s-1$ ,与 $A$ 的选择矛盾.故必有 $b\leqslant a_{i}+a_{j}<2b$ ,设 $a_{i}+a_{j}=b+q$ , $0\leqslant q<b$ ,这时 $B$ 的 $b$ 进制表示为
$\begin{aligned} B=& b^{n n_{1}+r+1}+q b^{m_{1}+r}+a b_{1}^{n_{1}}+\cdots+a_{i-1} b^{n_{i-1}}+a_{i+1} b^{n_{i+1}} \\ &+\cdots+a_{j-1} b^{n_{j}-1}+a_{j+1} b^{n_{j+1}}+\cdots+a_{s} b^{n_{s}}. \end{aligned}$
这样, $B$ 的数字和 $=\sum\limits_{k=1}^{s} a_{k}-\left(a_{i}+a_{j}\right)+1+q=\sum\limits_{k=1}^{s} a_{k}+1-b<\sum\limits_{k=1}^{s} a_{k}$ ,与 $A$ 的选择亦矛盾.故 $n_{1},\cdots ,n_{s}$ 模 $n$ 两两不同余.

另一方面,若 $s<n$ ,设 $n_{i}\equiv r_{i}\left(\bmod n\right)$ , $0\leqslant r_{i}<n$ .考察数 $C$ ,
$C=a_{1}b^{r_{1}}+a_{2}b^{r_{2}}+\cdots+a_{s}b^{r_{s}}$
由于 $b^{n_{i}}\equiv b^{r_{i}}\left(\bmod b^{n}-1\right)$ ,故 $b^{n}-1\mid C$ ,但 $s<n$ 意味着 $0<C\leqslant \left(b-1\right)b+\left(b-1\right)b^{2}+\cdots+\left(b-1\right)b^{n-1}=b^{n}-b<b^{n}-1$ .矛盾.

所以,命题成立.

高中奥数 2022-02-17

猜你喜欢

热点阅读