高中奥数 2021-12-31

高中奥数 2021-12-31

作者: 天目春辉 | 来源:发表于2021-12-31 11:22 被阅读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]$ .

说明

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

相关文章

网友评论

奥数自学研究

本文标题：高中奥数 2021-12-31

本文链接：https://www.haomeiwen.com/subject/wuegqrtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

奥数自学研究

热点阅读

奥数自学研究

关于我们|服务条款|联系我们|高中奥数 2021-12-31|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！