高中奥数 2022-02-08

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

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

先猜后证是数学发现的基本途径,如果所猜结论证不出来就变为了数学猜想.借助较小的数考察一个关于正整数n的命题,利用类比不完全归纳等手段猜出一般性结果,然后借助数学归纳法予以证明.这样的过程在解决问题时经常会出现.

2022-02-08-01

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

函数 $f:\mathbb{N}^{*}\rightarrow\mathbb{N}$ 定义如下 $f\left(1\right)=0$ ,且对任意 $n\in \mathbb{N}^{*}$ , $n\geqslant 2$ ,都有
$f\left(n\right)=\max\left\{f\left(j\right)+f\left(n-j\right)+j\vert j=1,2,\cdots,\left[\dfrac{n}{2}\right]\right\}.$
求出(并予以证明) $f\left(2044\right)$ 的值.

解

试算 $n$ 较小时 $f\left(n\right)$ 的值,分别有 $f\left(2\right)=1$ , $f\left(3\right)=2$ , $f\left(4\right)=4$ , $f\left(5\right)=5$ , $\cdots$ .在计算这些值的过程中,可发现当 $1\leqslant j\leqslant \left[\dfrac{n}{2}\right]$ 时, $f\left(j\right)+f\left(n-j\right)+j$ 的最大值在 $j=\left[\dfrac{n}{2}\right]$ 时取到,因此,猜想
$f\left(2n\right)=2f\left(n\right)+n,f\left(2n+1\right)=f\left(n\right)+f\left(n+1\right)+n.\qquad(*)$
下面用数学归纳法来证明 $(*)$ 成立.

当 $n=1$ 时,由上面的讨论知 $(*)$ 成立.

现设 $(*)$ 对 $1,2,\cdots ,n-1$ 都成立,考虑 $n$ 的情形.

先求 $f\left(2n\right)$ 的值.
$\begin{aligned} f\left(2n\right) & =\max\left\{f\left(j\right)+f\left(n-j\right)+j\vert 1\leqslant j\leqslant n\right\}\\ &\geqslant f\left(n\right)+f\left(2n-n\right)+n\\ &=2f\left(n\right)+n. \end{aligned}$
因此,只需证明: $f\left(2n\right)\leqslant 2f\left(n\right)+n$ .

对 $1\leqslant j\leqslant n$ 中 $j$ 的奇偶性分别讨论.

当 $j=2k$ , $1\leqslant k\leqslant \left[\dfrac{n}{2}\right]$ 时,由归纳假设有
$\begin{aligned} f(j)+f(2 n-j)+j &=f(2 k)+f(2(n-k))+2 k \\ &=(2 f(k)+k)+(2 f(n-k)+n-k)+2 k \\ &=2(f(k)+f(n-k)+k)+n \leqslant 2 f(n)+n . \end{aligned}$
最后一个不等式由 $f\left(n\right)$ 的定义得到.

当 $j=2k-1$ , $1\leqslant k\leqslant \left[\dfrac{n+1}{2}\right]$ 时,由归纳假设知
$\begin{aligned} & f(j)+f(2 n-j)+j \\ =& f(2 k-1)+f(2(n-k)+1)+2 k-1 \\ =&(f(k)+f(k-1)+k-1)+(f(n-k)+f(n-k+1)+n-k)+2 k-1 \\ =&(f(k-1)+f(n-(k-1))+k-1)+(f(k)+f(n-k)+k)+n-1 \\ \leqslant & f(n)+f(n)+n\\ =&2 f(n)+n . \end{aligned}$
这里认定 $f\left(0\right)=0$ ,又当 $n$ 为偶数时 $\left[\dfrac{n+1}{2}\right]=\left[\dfrac{n}{2}\right]$ ;当 $n$ 为奇数时,设 $n=2m+1$ ,则 $k=\left[\dfrac{n+1}{2}\right]$ 时, $f\left(k\right)+f\left(n-k\right)+k=f\left(m+1\right)+f\left(m\right)+m+1\leqslant f\left(n\right)+1$ ,所以上述不等式的推导是正确的.从而 $f\left(2n\right)\div2f\left(n\right)+n$ .

再求 $f\left(2n+1\right)$ 的值时,同上类似讨论,可知只需证明:
$f\left(2n+1\right)\leqslant f\left(n\right)+f\left(n+1\right)+n$
仍对 $1\leqslant j\leqslant n$ 中 $j$ 的奇偶性分别予以分析.

当 $j=2k$ , $1\leqslant j\leqslant\left[\dfrac{n}{2}\right]$ 时,由归纳假设有
$\begin{aligned} & f(j)+f(2 n+1-j)+j \\ =& f(2 k)+f(2 n+1-2 k)+2 k \\ =&(2 f(k)+k)+(f(n-k)+f(n-k+1)+n-k)+2 k \\ =&(f(k)+f(n-k)+k)+(f(k)+f(n+1-k)+k)+n \\ \leqslant & f(n)+f(n+1)+n . \end{aligned}$
当 $j=2k-1$ , $1\leqslant j\leqslant \left[\dfrac{n+1}{2}\right]$ 时,有
$\begin{aligned} & f(j)+f(2 n+1-j)+j \\ =& f(2 k-1)+f(2 n-2 k+2)+2 k-1 \\ =&(f(k-1)+f(k)+k-1)+(2 f(n-k-1)+n-k+1)+2 k-1 \\ =&(f(k-1)+f(n-(k-1))+k-1)+(f(k)+f(n+1-k)+k)+n \\ \leqslant & f(n)+f(n+1)+n . \end{aligned}$
从而 $f\left(2n+1\right)\leqslant f\left(n\right)+f\left(n+1\right)+n$ .

综上可知,对任意 $n\in \mathbb{N}^{*}$ , $(*)$ 都成立.

现在利用 $(*)$ 依次递推计算得 $f\left(2\right)=1$ , $f\left(3\right)=2$ , $f\left(4\right)=4$ , $f\left(7\right)=9$ , $f\left(8\right)=12$ , $f\left(15\right)=28$ , $f\left(16\right)=32$ , $f\left(31\right)=75$ , $f\left(32\right)=80$ , $f\left(62\right)=181$ , $f\left(63\right)=186$ , $f\left(125\right)=429$ , $f\left(126\right)=435$ , $f\left(250\right)=983$ ,f $\left(251\right)=989$ , $f\left(501\right)=2222$ , $f\left(1002\right)=4945$ , $f\left(2004\right)=10892$ .

所求的值 $f\left(2004\right)=10892$ .

说明

猜测的时候可以粗糙一些,但推导证明时一定要认真仔细,否则很容易得出错误的结论,难以形成科学的态度和习惯.

2022-02-08-02

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

对正整数 $k\leqslant 1$ ,设 $p\left(k\right)$ 为不能整除 $k$ 的最小素数.若 $p\left(k\right)>2$ ,记 $q\left(k\right)$ 为所有小于 $p\left(k\right)$ 的素数的乘积.若 $p\left(k\right)=2$ ,则令 $q\left(k\right)=1$ .

定义数列 $\left\{x_{n}\right\}$ 如下 $x_{0}=1$ ,而
$x_{n+1}=\dfrac{x_{n}p\left(x_{n}\right)}{q\left(x_{n}\right)},n=0,1,2,\cdots .$
求所有的 $n\in \mathbb{N}^{*}$ ,使 $x_{n}=111111$ .

解

试算最初的一些 $x_{n}$ 的值,列表如下:

表1

如果将 $n$ 写为二进制数,那么由上面的数据,可知 $n$ 在二进制表示中有几个1,那么 $x_{n}$ 就是几个素数的乘积.进一步,将素数从小到大排列,设依次为 $p_{0}<p_{1}<p_{2}<\cdots.$ 对照表中的数据不难得到下面的猜想:

对任意 $n\in \mathbb{N}^{*}$ ,设二进制表示下:
$n=2^{r_{1}}+2^{r_{2}}+\cdots+2^{r_{k}},r_{1}>r_{2}>\cdots >r_{k}\geqslant 0.$
即 $n$ 所对应的二进制数共 $\left(r_{1}+1\right)$ 位,其中第 $r_{k}+1,r_{k-1}+1,\cdots ,r_{1}+1$ 位上数归纳的元素为1,其余位上的元素全为0.则 $x_{n}=p_{r_{1}}p_{r_{2}}\cdots p_{r_{k}}$ ,其中 $p_{r_{i}}$ 表示所有素数中第 $r_{i}+1$ 大的素数. $(*)$

我们通过对 $n$ 归纳来证明上述结论.

当 $n=1$ 时,由 $x_{1}=2=p_{0}$ ,可知 $①$ 成立.

现设命题对 $n$ 成立,即 $x_{n}=p_{r_{1}}p_{r_{2}}\cdots p_{r_{k}}$ ,考虑 $n+1$ 的情形.

如果 $r_{k}\geqslant 1$ ,即 $n$ 对应的二进制数末位为0,那么 $n+1=2^{r_{1}}+2^{r_{2}}+\cdots+2^{r_{k}}+2^{0}$ ,此时 $x_{n}$ 为奇数,故 $p\left(x_{n}\right)=2$ ,进而 $q\left(x_{n}\right)=1$ ,由归纳假设,可知
$x_{n+1}= \dfrac{x_{n}p\left(x_{n}\right)}{q\left(x_{n}\right)}= \dfrac{x_{n}\cdot p_{0}}{1}=p_{r_{1}}\cdots p_{r_{k}}p_{0}$
如果 $r_{k}=0$ ,设 $i$ 是使得 $r_{i-1}\geqslant r_{i}+2$ 的最大的正整数,即 $n$ 对应的二进制数从右端第二位起往左数,所有的二进制位中,只有第 $\left(r_{i}+1\right)$ 位是第一个,其左边的二进制数位至少含有一个0.即
$n=\mathop {1}_{\atop{{\text{第}\atop {r_{1}+1 \atop \text{位}}}}}0\cdots0\mathop {1}_{\atop{{\text{第}\atop {r_{2}+1 \atop \text{位}}}}}0\cdots0\mathop {1}_{\atop{{\text{第}\atop {r_{i-1}+1 \atop \text{位}}}}}0\cdots0\mathop {1}_{\atop{{\text{第}\atop {r_{i}+1 \atop \text{位}}}}}\underbrace{11\cdots11}_{r_{i}\text{个}}.$
此时 $r_{k-j}=j$ ,其中 $0\leqslant j\leqslant k-i$ .那么
$n+1=2^{r_{1}}+2^{r_{2}}+\cdots+2^{r_{i-1}}+2^{r_{i+1}}\left(\text{若}i\text{不存在},\text{则}n+1=2^{r_{1}+1}\right).$
这时由归纳假设知 $p\left(x_{n}\right)=p_{r_{i}+1}$ ,从而 $q\left(x_{n}\right)=p_{0}p_{1}\cdots p_{i}=p_{0}p_{1}\cdots p_{k-i}=p_{r_{k}}p_{r_{k-1}}\cdots p_{r_{i}}$ .所以
$x_{n+1}=\dfrac{x_{n}\cdot p\left(x_{n}\right)}{q\left(x_{n}\right)}=\dfrac{p_{r_{1}}\cdots p_{r_{i-1}}p_{r_{i}+1}p_{r_{i}}\cdots p_{r_{k}}}{p_{r_{i}}\cdots p_{r_{k}}}=p_{r_{1}}\cdots p_{r_{i-1}}p_{r_{i}+1}.$
所以, $(*)$ 对 $n+1$ 成立,即对任意 $n\in \mathbb{N}^{*}$ , $(*)$ 都成立.