高中奥数 2022-02-21

作者: 不为竞赛学奥数 | 来源:发表于2022-02-21 14:05 被阅读0次

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

2022-02-21-01

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

设 $m$ 为给定的正整数,数列 $\left\{a_{n}\right\}$ 的每一项都是正整数,且对任意正整数 $n$ ,都有 $0<a_{n+1}-a_{n}\leqslant m$ .

证明:存在无穷多对正整数 $\left(p,q\right)$ ,使得 $p<q$ ,且 $a_{p}\mid a_{q}$ .

证明

先证:存在一对正整数 $\left(p,q\right)$ ,使得 $p<q$ ,且 $a_{p}\mid a_{q}$ .考察下列数表
$\begin{gathered} x_{0,1}, x_{0,2}, \cdots, x_{0, m} \\ x_{1,1}, x_{1,2}, \cdots, x_{1, m} \\ \cdots \\ x_{m, 1}, x_{m, 2}, \cdots, x_{m, m} \end{gathered}$
这里 $x_{0,1}=a_{1}$ , $x_{0,j}=x_{0,j-1}+1$ , $j=2,\cdots ,m$ .而 $x_{i,j}=\left(\prod\limits_{k=1}^{m}x_{i-1,k}\right)+x_{i-1,j}$ , $1\leqslant i,j\leqslant m$ .

上述数表中,每一行都是连续 $m$ 个正整数,每一列中任意两个数 $a$ 、 $b$ ,若 $a<b$ ,则 $a\mid b$ .

依条件,每一行中都有 $\left\{a_{n}\right\}$ 中至少两个数,因此,表格中有至少 $2\left(m+1\right)$ 个数为数列 $\left\{a_{n}\right\}$ 中的项,从而表格中有一列中有两个数在 $\left\{a_{n}\right\}$ 中,记为 $a_{p}$ , $a_{q}$ , $p<q$ ,则 $a_{p}\mid a_{q}$ .

现在将 $x_{0,1}$ 取为 $a_{q}+1$ ,同上构造同样性质的表格,即可找到下一对 $\left(p^{\prime},q^{\prime}\right)$ , $p^{\prime}<q^{\prime}$ ,使 $a_{p^\prime}\mid a_{q^\prime}$ .依次递推,即可找到无穷多对 $\left(p,q\right)$ ,使 $p<q$ ,且 $a_{p}\mid a_{q}$ .

命题获证.

2022-02-21-02

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

设 $S$ 是一个由非负整数组成的集合,用 $r_{s}\left(n\right)$ 表示满足下述条件的有序数对 $\left(s_{1},s_{2}\right)$ 的对数 $s_{1}$ 、 $s_{2}\in S$ , $s_{1}\ne s_{2}$ ,且 $s_{1}+s_{2}=n$ .

问:能否将非负整数集分划为两个集合 $A$ 、 $B$ ,使得对任意非负整数 $n$ ,都有 $r_{A}\left(n\right)=r_{B}\left(n\right)$ ?

解

存在这样的分划.令 $A=\left\{n\in \mathbb{N}\vert n\text{的二进制表示中数码1出现的次数为偶数}\right\}=\left\{0,3,5,6,\cdots \right\}$ ; $B=\left\{n\in \mathbb{N}\vert n\text{的二进制表示中数码1出现的次数为奇数}\right\}=\left\{1,2,4,7,\cdots\right\}$ .我们说 $A$ 、 $B$ 是符合条件的分划.

下面证明:对任意 $n\in \mathbb{N}$ ,都有 $r_{A}\left(n\right)=r_{B}\left(n\right)$ . $(*)$

对 $n$ 的二进制表示中的位数 $m$ 归纳来证明.

当 $m=0,1$ 时,注意到 $r_{A}\left(0\right)=r_{B}\left(0\right)=r_{A}\left(1\right)=r_{B}\left(1\right)=0$ 可知 $(*)$ 成立.

现设对位数不超过 $m$ 的 $n\in \mathbb{N}$ , $(*)$ 都成立.考察 $m+1$ 位的正整数 $n$ ,对可能的等式 $n=s_{1}+s_{2}$ , $s_{1}>s_{2}$ , $s_{1},s_{2}\in A$ (当 $s_{1},s_{2}\in B$ 时类似讨论),分三种情形讨论.

情形一:若 $s_{1}$ 右起第 $m+1$ 位为1,则 $s_{2}$ 右起第 $m+1$ 位必为0.考察这两个数右起的第1至第 $m$ 位,其中 $s_{1}$ 有奇数个1,而 $s_{2}$ 有偶数个1,令 $s_{1}^{\prime}=s_{2}+2^{m}$ , $s_{2}^{\prime}=s_{1}-2^{m}$ ,那么 $s_{1}^{\prime}$ 与 $s_{2}^{\prime}$ 都有奇数个1,并且 $s_{1}^{\prime}>s_{2}^{\prime}$ , $s_{1}^{\prime}+s_{2}^{\prime}=n$ , $s_{1}^{\prime},s_{2}^{\prime}\in B$ .反过来,当 $s_{1}$ 、 $s_{2}\in B$ 时,亦有 $s_{1}^{\prime}$ 、 $s_{2}^{\prime}\in A$ .故这部分两个集合中的表示方法数相同.

情形二:若 $s_{1}$ 、 $s_{2}$ 右起第 $m+1$ 位都为0,而右起第 $m$ 位都为1,同上讨论,可知 $s_{1}^{\prime}=s_{1}-2^{m-1}\in B$ , $s_{2}^{\prime}=s_{2}-2^{m-1}\in B$ .故 $\left(s_{1}^{\prime},s_{2}^{\prime}\right)$ 构成 $B$ 中对 $n-2^{m}$ 的一个表示.反过来,当 $s_{1}$ 、 $s_{2}\in B$ 时, $\left(s_{1}^{\prime},s_2^{\prime}\right)$ 构成 $A$ 中对 $n-2^{m}$ 的一个表示利用 $r_{A}\left(n-2^{m}\right)=r_{B}\left(n-2^{m}\right)$ (归纳假设),可知这部分两个集合中的表示方法数亦相同.

情形三若 $s_{1}$ , $s_{2}$ 右起第 $m+1$ 位都为0,右起第 $m$ 位不全为1,这时 $s_{1}$ 右起第 $m$ 位为1,而 $s_{2}$ 右起第 $m$ 位为0.此时考察两数右起第1位至 $m-1$ 位中1的个数, $s_{1}$ 中有奇数个, $s_{2}$ 中有偶数个.令 $s_{1}^{\prime}=s_{2}+2^{m-1}$ , $s_{2}^{\prime}=s_{1}-2^{m-1}$ .同情形一可知,这部分两个集合中的表示方法数相同.

综上可知,对 $m+1$ 位数 $n$ ,亦有 $r_{A}\left(n\right)=r_{B}\left(n\right)$ .所以, $A$ 、 $B$ 符合.

2022-02-21-03

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

证明:任何一个大于1的整数都可以表示为符合下述条件的有限个正整数的和的形式:

(1)每个加项的素因数都是2或3;

(2)任意两个加项中没有一个是另一个的倍数.

证明

设能表示的数构成的集合为 $S$ ,令 $T=S\cup\left\{1\right\}$ ,并记 $S$ 中3的幂次不超过 $h$ 的元素构成的集合为 $S_{h}$ , $T_{h}=S_{h}\cup\left\{1\right\}$ ,则下面的结论显然成立.

(1) $2T\subseteq T$ , $3T\subseteq T$ .这里 $xT=\left\{xt\vert t\in T\right\}$ .

(2)若 $h<k$ ,则 $2T_{h}+3^{k}\subseteq T$ .这里 $2T_{h}+3^{k}=\left\{2t+3^{k}\vert t\in T_{h}\right\}$ .

下面用数学归纳法证明:对任意 $n\in \mathbb{N}^{*}$ ,都有 $n\in T$ .

“ $1\in T$ ”由 $T$ 的定义可知是成立的.若对任意 $m\in \mathbb{N}^{*}$ , $m<n$ ,均有 $m\in T$ ,考虑 $n$ 的情形.

情形一:若 $2\mid n$ ,则 $\dfrac{n}{2}\in T$ ,于是 $n\in 2T\subseteq T$ ;

情形二:若 $3\mid n$ ,则 $\dfrac{n}{3}\in T$ ,于是 $n\in 3T\subseteq T$ ;

情形三:若 $2\nmid n$ ,且 $3\nmid n$ ,则存在 $k\in \mathbb{N}^{*}$ ,使 $3^{k}<n<3^{k+1}$ .这时, $0< \dfrac{n-3^{k}}{2}<\dfrac{3^{k+1}-3^{k}}{2}=3^{k}<n$ , $\dfrac{n-3^{k}}{2}\in T_{k-1}$ .