高中奥数 2022-02-10

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

存在性问题出现在数学的每一个分支中,前面的各节中都出现过.这里专门用一节来讨论数列中的存在性问题是希望起到强调的作用,引起重视,并以例题的形式讨论一些处理此类问题的方法.

2022-02-10-01

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚先猜后证 P089 例01）

设 $a$ 、 $b$ 是两个大于2的整数.证明:存在正整数 $k$ 及由正整数组成的有穷数列 $n_{1},n_{2},\cdots ,n_{k}$ ,使得 $n_{1}=a$ , $n_{k}=b$ ,而对 $1\leqslant i\leqslant k-1$ ,都有
$\left(n_{i}+n_{i+1}\right)\mid n_{i}n_{i+1}.$

证明我们用“ $a\sim b$ ”表示正整数 $a$ 、 $b$ 可以用上述数列连接,那么“若 $a\sim b$ 成立,则 $b\sim a$ 亦成立”.

一个自然的想法是证明:任意两个相邻正整数(都大于2)之间是“可达”的.利用下面的两个结论可达此目的.

结论1对任意 $n\in \mathbb{N}^{*}$ , $n\geqslant 3$ ,都有 $n\sim 2n$ .

下面的数列表明结论1成立.

$n,n\left(n-1\right),n\left(n-1\right)\left(n-2\right),n\left(n-2\right),2n.$

结论2对任意 $n\in \mathbb{N}^{*}$ , $n\geqslant 4$ ,都有 $n\sim n-1$ .

利用数列
$n,n\left(n-1\right),n\left(n-1\right)\left(n-2\right),n\left(n-1\right)\left(n-2\right)\left(n-3\right),2\left(n-1\right)\left(n-2\right).$
结合结论1知 $2\left(n-1\right)\left(n-2\right)\sim \left(n-1\right)\left(n-2\right)$ ,而 $\left(n-1\right)\left(n-2\right)+\left(n-1\right)=\left(n-1\right)^{2}$ 是 $\left(n-1\right)\left(n-2\right)\cdot\left(n-1\right)$ 的约数.故结论2成立.

对大于2的整数 $a$ 、 $b$ ,不妨设 $a\leqslant b$ ,如果 $a=b$ ,那么利用 $a\sim a+1\sim b\left(=a\right)$ 可知命题成立;如果 $a<b$ ,那么利用 $a\sim a+1\sim a+2\sim\cdots\sim b$ 可知命题亦成立.

说明解决的关键是对结论1和结论2的直接构造,这是处理存在性问题的最自然的思路.

2022-02-10-02

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚先猜后证 P090 例02）

设 $m\in \mathbb{N}^{*}$ .问:是否存在一个 $m$ 次的整系数多项式 $f\left(x\right)$ ,使得对任意 $n\in \mathbb{Z}$ ,由下述方式定义的数列 $\left\{a_{k}\right\}$ 中任意两项互素: $a_{1}=f\left(n\right)$ , $a_{k+1}=f\left(a_{k}\right)$ , $k=1,2,\cdots$ ?

解

当 $m=1$ 时,不存在这样的多项式.

事实上,如果存在 $f\left(x\right)=ax+b$ 符合要求,不妨设 $a>0$ .那么对 $n\in \mathbb{Z}$ 有
$a_{k}=a^{k}\cdot n+\left(a^{k-1}+\cdots+1\right)b.\qquad(*)$
此结论可通过对 $k$ 归纳得到.

若 $b=0$ ,则对任意大于1的正整数 $n$ ,由 $(*)$ 可知数列 $\left\{a_{k}\right\}$ 中每一项都是 $n$ 的倍数,从而没有两项是互素的.

若 $b\ne 0$ ,由于 $a$ 为正整数,知存在 $k\in \mathbb{N}^{*}$ ,使得 $\left|\left(a^{k-1}+\cdots+1\right)b\right|>1$ ,记 $c=\left(a^{k-1}+\cdots+1\right)b$ ,我们取 $n$ 为 $\left|c\right|$ 的素因子,则对应于这个 $n$ 的 $a_{k}$ 是 $n$ 的倍数,由 $(*)$ 知 $a_{2k}=a^{2k}\cdot n+\left(a^{2k-1}+\cdots+1\right)b=a^{2k}\cdot n+\left(a^{k}+1\right)\cdot\left(a^{k-1}+\cdots+1\right)b=a^{2k}\cdot n+\left(a^{k}+1\right)c$ ,故 $n$ 也是 $a_{2k}$ 的约数,导致 $a_{k}$ 与 $a_{2k}$ 不互素.

所以,在 $m=1$ 时,不存在符合要求的整系数多项式.

下证:当 $m\geqslant 2$ 时,都存在这样的多项式.

我们证明:当 $f\left(x\right)=x^{m-1}\left(x-1\right)+1$ 时,对任意 $n\in \mathbb{Z}$ ,相应的数列 $\left\{a_{k}\right\}$ 中任意两项都互素.

注意到,对任意 $k\in \mathbb{N}^{*}$ ,有
$a_{k+1}=a_{k}^{m-1}\left(a_{k}-1\right)+1\equiv 1\left(\bmod a_{k}\right),$
而且
$a_{k+2}=a_{k+1}^{m-1}\left(a_{k+1}-1\right)+1\equiv 1^{m-1}\cdot 0+1=1\left(\bmod a_{k}\right).$
依此结合数学归纳法可知,对任意正整数 $t>k$ ,都有 $a_{t}\equiv 1\left(\bmod a_{k}\right)$ .所以,数列 $\left\{a_{k}\right\}$ 中任意两项都互素.

综上可知,当 $m=1$ 时,不存在;而 $m\geqslant 2$ 时,都存在.

说明对 $m\geqslant 2$ 的情形,任取一个 $m-2$ 次的整系数多项式 $g\left(x\right)$ ,令 $f\left(x\right)=x\left(x-1\right)g\left(x\right)+1$ ,仿上可证:对 $n\in \mathbb{Z}$ ,相应的数列 $\left\{a_{k}\right\}$ 中任意两项互素.

2022-02-10-03

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚先猜后证 P091 例03）

设 $q$ 为一个给定的实数,满足 $\dfrac{1+\sqrt{5}}{2}<q<2$ .数列 $\left\{p_{n}\right\}$ 定义如下:若正整数 $n$ 的二进制表示是 $n=2^{m}+a_{m-1}\cdot 2^{m-1}+\cdots+a_{1}\cdot 2+a_{0}$ ,这里 $a_{i}\in \left\{0,1\right\}$ .则 $p_{n}=q^{m}+a_{m-1}\cdot q^{m-1}+\cdots+a_{1}\cdot q+a_{0}$ .证明:存在无穷多个正整数 $k$ ,使得不存在正整数 $l$ ,满足 $p_{2k}<p_{l}<p_{2k+1}$ .

证明

对 $m\in \mathbb{N}^{*}$ ,设二进制表示 $2k=(\underbrace{10\cdots 10}_{m\text{个}10})_{2}$ ,我们证明不存在 $l\in \mathbb{N}^{*}$ ,使得 $p_{2k}<p_{l}<p_{2k+1}$ .

事实上,对这样的 $k\in \mathbb{N}^{*}$ ,有
$p_{2k}=q^{2m-1}+q^{2m-3}+\cdots+q,p_{2k+1}=p_{2k}+1.$
如果存在 $l\in \mathbb{N}^{*}$ ,使得 $p_{2k}<p_{l}<p_{2k+1}$ ,设 $l$ 的二进制表示为 $l=\sum\limits_{i=0}^{t}a_{i}\cdot2^{i}$ , $a_{i}\in \left\{0,1\right\}$ , $a_{t}=1$ ,则 $p_{l}=\sum\limits_{i=0}^{t}a_{i}\cdot q^{i}$ .

(1)若 $m=1$ ,则 $q<p_{l}<q+1$ ,这时,如果 $t\geqslant 2$ ,那么 $p_{l}\geqslant q^{2}>q+1$ (因为 $\dfrac{+\sqrt{5}}{2}<q<2$ ,有 $q+1<q^{2}$ ),矛盾.如果 $t=1$ ,那么 $p_{l}=q$ 或 $q+1$ ,亦矛盾.

(2)设 $m-1\left(m\geqslant 2\right)$ 时,可以推出矛盾,考虑 $m$ 的情形.

若 $t\geqslant 2m$ ,则 $p_{l}\geqslant q^{2m}\geqslant q^{2m-1}+q^{2m-2}\geqslant q^{2m-1}+q^{2m-3}+q^{2m-4}\geqslant \cdots\geqslant q^{2m-1}+\cdots+q+1=p_{2k+1}$ ,矛盾.

若 $t\leqslant 2m-2$ ,则 $p_{l}\leqslant q^{2m-2}+q^{2m-3}+\cdots+1=\left(q^{2m-2}+q^{2m-3}\right)+\left(q^{2m-4}+q^{2m-5}\right)+\cdots+\left(q^{2}+q\right)+1\leqslant q^{2m-1}+q^{2m-3}+\cdots+q^{3}+1<q^{2m-1}+\cdots +q^{3}+q=p_{2k}$ ,矛盾.

上述推导中,都用到 $q^{i+2}\geqslant q^{t+i}+q^{i},i=0,1,2,\cdots$ .

所以 $t=2m-1$ ,这时,记 $l^{\prime}=l-2^{2m-1}=\sum\limits_{i=0}^{t-1}a_{i}\cdot 2^{i}$ ,进而,有 $p_{l^{\prime}}=p_{l}-q^{2m-1}$ ,于是,由 $p_{2k}<p_{l}<p_{2k+1}$ 知
$p_{2\left(k-1\right)}=q^{2m-3}+\cdots+q^{3}+q<p_{l^{\prime}}<p_{2\left(k-1\right)+1}.$

与归纳假设不符.

综上可知,命题成立.

高中奥数 2022-02-10

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

奥数自学研究