高中奥数 2022-02-15

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

2022-02-15-01

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

求最小的正整数 $k$ ,使得至少存在两个由正整数组成的数列 $\left\{a_{n}\right\}$ 满足下述条件:

(1)对任意正整数 $n$ ,都有 $a_{n}\leqslant a_{n+1}$ ;

(2)对任意正整数 $n$ ,都有 $a_{n+2}=a_{n+1}+a_{n}$ ;

(3) $a_{9}=k$ .

解

利用 $a_{n+2}=a_{n+1}+a_{n}$ 可知 $a_{9}=a_{8}+a_{7}=2a_{7}+a_{6}=\cdots=21a_{2}+13a_{1}$ ,依题中条件,可知不定方程
$13.x+21y=k\qquad(*)$
有至少两组正整数解 $\left(x,y\right)$ ,使得 $x\leqslant y$ .

注意到,若 $(*)$ 有两组正整数解 $\left(x_{1},y_{1}\right)$ 和 $\left(x_{2},y_{2}\right)$ ,使得 $x_{1}\leqslant y_{1}$ , $x_{2}\leqslant y_{2}$ ,则 $13x_{1}+21y_{1}=13x_{2}+21y_{2}=k$ ,由对称性,不妨设 $x_{1}\leqslant x_{2}$ ,那么 $13\left(x_{2}-x_{1}\right)=21\left(y_{1}-y_{2}\right)$ ,此时,由 $x_{1}=x_{2}$ 可得 $y_{1}=y_{2}$ ,导致 $\left(x_{1},y_{1}\right)=\left(x_{2},y_{2}\right)$ 矛盾,故 $x_{1}<x_{2}$ ,从而有 $21\mid x_{2}-x_{1}$ , $13\mid y_{1}-y_{2}$ (用到 $\left(13,21\right)=1$ ),所以 $x_{2}-x_{1}\geqslant 21$ ,得 $x_{2}\geqslant 21+x_{1}\geqslant 22$ ,结合 $y_{2}\geqslant x_{2}$ 可知 $k\geqslant 13\times 22+21\times 22=748$ .

另一方面,当 $k=748$ 时, $(*)$ 有两组不同的正整数解,它们是 $\left(22,22\right)$ 和 $\left(1,35\right)$ ,分别对应的 $\left(a_{1},a_{2}\right)$ 形成两个符合要求的数列综上可知,所求最小正整数为748.

2022-02-15-02

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

Fibonacci数列 $\left\{F_{n}\right\}$ 定义如下: $F_{1}=F_{2}=1$ , $F_{n+2}=F_{n+1}+F_{n}$ , $n=1,2,\cdots$ .求所有的正整数数对 $\left(k,m\right)$ , $m>k$ .使得如下定义的数列 $\left\{x_{n}\right\}$ :
$x_{1}=\dfrac{F_{k}}{F_{m}},x_{n+1}=\begin{cases} \dfrac{2x_{n}-1}{1-x_{n}},&\text{若}x_{n}\neq 1,\\ 1,&\text{若}x_{n}= 1 \end{cases}\left(n=1,2,\cdots\right)$
包含等于1的项.

解

若 $m\geqslant k+2$ ,则 $F_{m}\geqslant F_{k+2}=F_{k+1}+F_{k}\geqslant 2F_{k}$ (因为数列 $\left\{F_{n}\right\}$ 是不减数列),于是 $x_{1}\leqslant \dfrac{1}{2}$ ,结合 $\left\{x_{n}\right\}$ 的定义可知 $x_{2}\leqslant 0$ ,进而利用数学归纳法易证:对 $n\geqslant 2$ ,都有 $x_{n}\leqslant 0$ .此时, $\left\{x_{n}\right\}$ 中不包含等于1的项.所以 $m<k+2$ ,而 $m>k$ ,故只能是 $m=k+1$ .

另一方面,对任意 $k\in \mathbb{N}^{*}$ ,若 $m=k+1$ ,则由 $\left\{x_{n}\right\}$ 的定义可知 $x_{2}=\dfrac{2F_{k}-F_{k+1}}{F_{k+1}-F_{k}}$ (除非 $k=1$ , $m=2$ ,此时 $x_{1}=1$ ,数列中已包含1),得 $x_{2}=\dfrac{F_{k}-F_{k-1}}{F_{k-1}}=\dfrac{F_{k-2}}{F_{k-1}}$ ,依此递推,当 $k$ 为奇数时,设 $k=2n+1$ ,则有 $x_{3}=\dfrac{F_{2n-3}}{F_{2n-2}}$ , $\cdots$ , $x_{n+1}=\dfrac{F_{1}}{F_{2}}=1$ ,符合题意;当 $k$ 为偶数时,设 $k=2n$ ,则有 $x_{3}=\dfrac{F_{2n-4}}{F_{2n-3}}$ , $\cdots$ , $x_{n}=\dfrac{F_{2}}{F_{3}}=\dfrac{1}{2}$ ,此后数列的每一项都不大于零,不符合题意.

综上可知,所求正整数对 $\left(k,m\right)=\left(2n-1,2n\right)$ , $n\in \mathbb{N}^{*}$ .

2022-02-15-03

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

小张从 $\left\{1,2,\cdots ,144\right\}$ 中任取一个数,小王希望有偿地知道小张所取的数.小王每次可从 $\left\{1,2,\cdots ,144\right\}$ 中取一个子集 $M$ ,然后问小张:“你取的数是否属于 $M$ ?”如果答案是Yes,则小王付给小张2元钱,答案是No,则付1元问:小王至少需要支付多少元钱,才能保证可以知道小张所取的数?

解

答案是11元钱.

设 $f\left(n\right)$ 是从 $\left\{1,2,\cdots ,n\right\}$ 中确定小张所取的数所需支付的最少钱数,则 $f\left(n\right)$ 是一个不减数列.并且如果小王第一次所取的子集是一个 $m$ 元集,那么 $f\left(n\right)\leqslant \max\left\{f\left(m\right)+2,f\left(n-m\right)+1\right\}$ .

下面我们利用Fibonacci数列 $\left\{F_{n}\right\}$ ,证明下述结论:设 $x$ 为正整数,并且 $F_{n}<x\leqslant F_{n+1}\left(n\geqslant 2\right)$ ,则
$f\left(x\right)=n-1.\qquad(*)$

先证明:对任意 $n\in \mathbb{N}^{*}\left(n\geqslant 2\right)$ ,均有
$f\left(F_{n+1}\right)\leqslant n-1.\qquad(**)$

事实上,当 $n=2$ 时, $F_{3}=2$ ,易知 $f\left(F_{3}\right)\leqslant 2$ .设对小于 $n$ 的正整数, $(**)$ 都成立.考虑 $n$ 的情形,小王第一次取一个子集,使其元素个数为 $F_{n-1}$ ,就有 $f\left(F_{n+1}\right)\leqslant \max\left\{f\left(F_{n-1}\right)+2,f\left(F_{n+1}-F_{n-1}\right)+1\right\}=\max\left\{f\left(F_{n-1}\right)+2,f\left(F_{n}\right)+1\right\}\leqslant \max\left\{n-1.n-1\right\}=n-1$ (这里认为 $f\left(F_{2}\right)=f\left(1\right)=0$ ).所以 $(**)$ 对一切正整数 $n$ 成立.

再证明:对任意 $n\in \mathbb{N}^{*}$ , $F_{n}<x\leqslant F_{n+1}$ , $x\in \mathbb{N}^{*}$ ,均有 $f\left(x\right)\geqslant n-1$ .

当 $n=2$ 时, $x=F_{3}=2$ ,此时易知 $f\left(2\right)\geqslant 2$ ,故对 $n=1$ 成立.设命题对小于 $n$ 的正整数成立,考虑 $n$ 的情形.对任意 $n\in \mathbb{N}^{*}$ , $F_{n}<x\leqslant F_{n-1}$ (注意,这里 $n\geqslant 3$ ,故 $x\geqslant 3$ ).

如果小王第一次取的子集的元素个数 $\leqslant F_{n-2}$ ,那么小王至少应付的钱数 $\geqslant f\left(x-F_{n-2}\right)+1\geqslant f\left(F_{n-1}+1\right)+1\geqslant n-1$ ;如果小王第一次取的子集的元素个数 $\geqslant F_{n-2}+1$ ,那么他至少应付的钱款数 $\geqslant f\left(F_{n-2}+1\right)+2\geqslant n-3+2=n-1$ .所以, $f\left(x\right)\geqslant n-1$ .