高中奥数 2022-02-11

2022-02-11 本文已影响0人不为竞赛学奥数

2022-02-11-01

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

是否存在一个由正整数组成的数列 $\left\{a_{n}\right\}$ ,使得每一个正整数都在该数列中恰好出现一次,并且对任意 $k\in \mathbb{N}^{*}$ ,都有 $k\mid\left(a_{1}+\cdots+a_{k}\right)$ ?

解

存在这样的数列.

我们采用递归方法来构造:取 $a_{1}=1$ ,现设 $a_{1},a_{2},\cdots ,a_{m}$ (两两不同)已取定,令 $t$ 为不在 $a_{1},\cdots ,a_{m}$ 中出现的最小正整数.由于 $\left(m+1,m+2\right)=1$ ,故利用中国剩余定理可知:存在无穷多个正整数 $r$ ,使得(记 $s=a_{1}+\cdots+a_{m}$ )
$\begin{cases} s+r\equiv 0\left(\bmod m+1\right),\\ s+r+t\equiv0 \left(\bmod m+2\right). \end{cases}$
取这样的一个 $r$ ,使得 $r>\max\left\{a_{1},\cdots,a_{m},t\right\}$ ,令 $a_{m+1}=r$ , $a_{m+2}=t$ .依此定义的数列即符合要求.

说明利用递推方法来处理存在性问题本质上还是一种直接构造的技巧.本题中定义的数列依次写出可以是1,3,2,10,4, $\cdots$ ,每次增加两项的做法可确保不重复地遍经所有正整数.

2022-02-11-02

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

一个由整数组成的数列 $\left\{a_{n}\right\}$ 满足:对任意下标 $k\geqslant 2$ ,都有 $0\leqslant a_{k}\leqslant k-1$ ,并且 $a_{1}+\cdots+a_{k}\equiv 0\left(\bmod k\right)$ .证明:无论初始值 $a_{1}$ 如何选取,都存在正整数 $m$ ,使得该数列从第 $m$ 项起变为常数.

证明

出发点是去证:对任意 $a_{1}\in \mathbb{Z}$ ,存在下标 $k$ ,使得 $a_{1}+\cdots+a_{k}=-dk$ ,其中 $0\leqslant d<k.\qquad(*)$

如果上述结论获证,那么 $a_{1}+\cdots+a_{k}+d=d\cdot\left(k+1\right)$ ,而 $a_{k+1}$ 是 $\left\{0,12,\cdots ,k\right\}$ 中满足 $a_{1}+\cdots+a_{k+1}\equiv 0\left(\bmod k+1\right)$ 的唯一整数,于是 $a_{k+1}=d$ .依此递推,就可证出:当 $n\geqslant k+1$ 时,都有 $a_{n}=d$ .

现在来证 $(*)$ 成立.若否,设存在 $a_{1}$ ,使得满足 $(*)$ 的下标 $k$ 不存在.由于当 $a_{1}<0$ 时,如果数列 $\left\{a_{n}\right\}$ 不是从某一项开始变为0,那么 $\left\{a_{n}\right\}$ 中有无穷多项为正整数,因此,存在 $m\in \mathbb{N}^{*}$ ,使得 $a_{1}+\cdots+a_{m}\geqslant 0$ ,从而,可不妨设 $a_{1}>0$ (注意,若 $a_{1}=0$ ,则可知对任意 $n\in \mathbb{N}^{*}$ ,都有 $a_{n}=0$ ),此时,对任意 $m\in \mathbb{N}^{*}$ ,都有 $a_{1}+a_{2}+\cdots+a_{m}>0$ .

由条件 $a_{1}+\cdots+a_{m}\equiv 0\left(\bmod m\right)$ ,可设 $a_{1}+\cdots+a_{m}=d_{m}\cdot m$ ,结合反设中没有下标 $k$ 符合 $(*)$ ,可知对任意 $m\in \mathbb{N}^{*}$ ,都有 $d_{m}\geqslant m$ ,故 $a_{1}+\cdots+a_{m}\geqslant m^{2}$ .利用 $m\geqslant 2$ 时,有 $a_{m}\leqslant m-1$ ,得
$m^{2}\leqslant a_{1}+\cdots+a_{m}\leqslant a_{1}+1+2+\cdots+\left(m-1\right)=a_{1}+\dfrac{m\left(m-1\right)}{2}.$
导致 $a_{1}\geqslant \dfrac{m\left(m+1\right)}{2}$ ,此式不能对所有 $m\in \mathbb{N}^{*}$ 都成立,所得矛盾表明 $(*)$ 成立.
综上可知,命题成立.

说明

利用反证法(或抽屉原则等)是间接得到存在性的基本方法,在处理不存在问题时就更常用了.

2022-02-11-03

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

数列 $\left\{a_{n}\right\}$ 定义如下:若正整数 $n$ 在二进制表示下,数码1出现偶数次,则 $a_{n}=0$ ;否则 $a_{n}=1$ .证明:不存在正整数 $k$ 、 $m$ ,使得对任意 $j\in \left\{0,1,2,\cdots ,m-1\right\}$ ,都有
$a_{k+j}=a_{k+m+j}=a_{k+2m+j}.\qquad(*)$

证明

利用 $\left\{a_{n}\right\}$ 的定义可知
$\begin{cases} a_{2n}\equiv a_{n}\left(\bmod 2\right),\\ a_{2n+1}\equiv a_{2n}+1\equiv a_{n}+1\left(\bmod 2\right). \end{cases}\qquad(**)$
如果存在 $k$ 、 $m\in \mathbb{N}^{*}$ ,使得对 $j\in \left\{0,1,\cdots,m-1\right\}$ 都有 $(*)$ 成立那么由最小数原理,我们可设 $\left(k,m\right)$ 是这样的正整数对中使 $k+m$ 最小的数对.

情形一 $m$ 为偶数,设 $m=2t$ , $t\in \mathbb{N}^{*}$ .

若 $k$ 为偶数,在 $(*)$ 中取 $j=0,2,\cdots ,2\left(t-1\right)$ ,则 $0\leqslant \dfrac{j}{2}\leqslant t-1$ ,且
$a_{k+j}=a_{k+m+i}=a_{k+2m+j},$
由 $(**)$ 得 $a_{\frac{k}{2}+\frac{j}{2}}=a_{\frac{k}{2}+t+\frac{j}{2}}=a_{\frac{k}{2}+2t+\frac{j}{2}}$ ,这表明 $\left(\dfrac{k}{2},\dfrac{m}{2}\right)$ 也是使 $(*)$ 对 $0\leqslant j\leqslant \dfrac{m}{2}-1$ 都成立的正整数对,与 $k+m$ 的最小性矛盾.

若 $k$ 为奇数,在 $(*)$ 中取 $j=1,3,\cdots ,2t-1$ ,同上讨论可知
$a_{\frac{k+1}{2}+\frac{j-1}{2}}=a_{\frac{k+1}{2}+t+\frac{j-1}{2}}=a_{\frac{k+1}{2}+2t+\frac{j-1}{2}},$
表明 $\left(\dfrac{k+1}{2},\dfrac{m}{2}\right)$ 也使 $(*)$ 对 $0\leqslant j\leqslant \dfrac{m}{2}-1$ 都成立,与 $k+m$ 的最小性矛盾.

情形二 $m$ 为奇数.

当 $m=1$ 时,要求 $a_{k}=a_{k+1}=a_{k+2}$ ,这时如果 $k$ 为偶数,那么 $a_{2n}=a_{2m+1}\equiv a_{2n}+1\left(\bmod 2\right)$ ,矛盾;如果 $k$ 为奇数,设 $k=2n+1$ ,那么 $a_{2n+2}=a_{2n+3}\equiv a_{2n+2}+1\left(\bmod 2\right)$ ,亦矛盾.

当 $m\geqslant 3$ 时,在 $(*)$ 中令 $j=0,1,2$ ,可得
$\begin{cases} a_{k}=a_{k+m}=a_{k+2m},&\qquad(***)\\ a_{k+1}=a_{k+m+1}=a_{k+2m+1},&\qquad(****)\\ a_{k+2}=a_{k+m+2}=a_{k+2m+2}.&\qquad(*****) \end{cases}$
如果 $k$ 为偶数,设 $k=2n$ , $m=2t+1$ ,那么由 $(**)$ 知 $a_{k+1}\ne a_{k}$ , $a_{k+m+1}\ne a_{k+m+2}$ ,这样结合 $(***)$ 、 $(****)$ 、 $(*****)$ 可知
$a_{k}=a_{k+m+2}=a_{k+2}.\qquad(******)$
(注意,这里用到数列之中的每一项都为0或1.)

现在,若 $n$ 为偶数,设 $n=2t$ ,则 $a_{k+2}=a_{4t+2}=a_{2t+1}\equiv a_{2t}+1\equiv a_{4t}+1\equiv a_{k}+1\left(\bmod 2\right)$ ,与 $(******)$ 矛盾;若 $n$ 为奇数,则由 $m$ 为奇数可知 $k+2m\equiv 0\left(\bmod 4\right)$ ,类似讨论可得 $a_{k+2m}\ne a_{k+2m+2}$ ,结合 $(***)$ 、 $(*****)$ 、 $(******)$ 亦得矛盾.

如果 $k$ 为奇数,结合 $m$ 为奇数,由 $(**)$ 可知 $a_{k+m}\ne a_{k+m+1}$ , $a_{k+1}\ne a_{k+2}$ ,利用 $(***)$ 、 $(****)$ 、 $(*****)$ 得
$a_{k}=a_{k+m}=a_{k+2}.\qquad(*******)$
现在,若 $k\equiv 1\left(\bmod 4\right)$ ,则由 $(*******)$ 的 $a_{k}=a_{k+2}$ 可推出矛盾;若 $k\equiv 3\left(\bmod 4\right)$ ,则由 $m$ 为奇数可知 $k+2m\equiv 1\left(\bmod 4\right)$ ,故 $a_{k+2m}\ne a_{k+2n+2}$ ,即 $a_{k}\ne a_{k+2}$ 与 $(*******)$ 矛盾.

综上可知,命题成立.

高中奥数 2022-02-11

猜你喜欢

热点阅读