奥数自学研究

高中奥数 2021-12-31

2021-12-31 本文已影响0人天目春辉

2021-12-31-01

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

设 $a_{1},a_{2},\cdots ,a_{n}$ 为一个倒三角形的第1行,其中 $a_{i}\in \left\{0,1\right\}$ , $i=1,2,\cdots ,n$ .数 $b_{1},b_{2},\cdots,b_{n-1}$ 为这个倒三角形的第2行,使得若 $a_{k}=a_{k+1}$ ,则 $b_{k}=0$ ;若 $a_{k}\ne a_{k-1}$ ,则 $b_{k}=1$ , $k=1,2,\cdots ,n-1$ .类似定义该倒三角形的其余各行,直到第 $n$ 行为止.求该三角形中1的个数的最大值.

解

我们设该三角形中1的个数的最大值为 $f_{n}$ .容易得到 $f_{1}=1,f_{2}=2,f_{3}=4$ .例子为

图1

得到上述值可以从表中第一行内0的个数出发,但是随着 $n$ 变大时,难以从第一行出发来处理.试着做 $n=5,6$ 时的情形,可以发现下面的表中1的个数比较多.

图2

上表中有一个特点,即每三行重复出现(只是"规模"小一些).于是,引导我们利用数学归纳法来求 $f_{n}$ 的值.

先证明一个引理.

引理

当 $n≥3$ 时,考虑该倒三角形最上面的3行

图3

则此3行中至少出现 $n-1$ 个0.

证明

对 $n$ 归纳予以证明.

初始情况的验证留给读者,我们来看如何实现归纳过渡.注意到,在 $\bmod 2$ 的意义下,前3行为

图4

如果 $a_{1},a_{1}+a_{2},a_{1}+a_{3}$ 不全为1,那么去掉这3个数,归为 $n-1$ 的情形,利用归纳假设可知,结论成立.

如果 $a_{1}=a_{1}+a_{2}=a_{1}+a_{3}=1$ ,那么 $a_{1}=1$ , $a_{2}=a_{3}=0$ ,此时,表格的前三行前面部分为

图5

其中被平行四边形框住的9个数(前面的3个斜行)中至少有3个0,于是,去掉这9个数后,利用归纳假设可知,引理成立由上述引理可知 $f_{n}\leqslant 2\left(n-1\right)+f_{n-3},n≥4$ .结合 $f_{1}=1,f_{2}=2,f_{3}=4$ ,可知 $f_{n}\leqslant \left[\dfrac{n\left(n+1\right)}{3}\right]$ ,这里 $\left[x\right]$ 表示不小于 $x$ 的最小整数.利用前面子,可知的例子,可知 $f_{n}=\left[\dfrac{n\left(n+1\right)}{3}\right]$ .

所以,该倒三角形中,1的个数的最大值为 $\left[\dfrac{n\left(n+1\right)}{3}\right]$ .

说明

此题找到取最大值的例子是一个关键,但经一定的尝试后不难得到解答难在对每三行作为一个整体来进行处理不易想到,它是从例子中得到启发后形成的思路.

上一篇下一篇

猜你喜欢

热点阅读