高中奥数 2022-02-22

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

2022-02-22-01

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

函数 $f$ 、 $g:\mathbb{N}^{*}\rightarrow \mathbb{N}^{*}$ ,其中 $f$ 是满射,而 $g$ 是单射,并且对任意正整数 $n$ ,都有 $f\left(n\right)\geqslant g\left(n\right)$ .证明:对任意正整数 $n$ ,都有 $f\left(n\right)=g\left(n\right)$ .

证明

对任意 $k\in \mathbb{N}^{*}$ ,由 $f$ 是满射,知集合 $f^{-1}\left(k\right)=\left\{x\vert x\in \mathbb{N}^{*},f\left(x\right)=k\right\}$ 是一个非空集,于是,由最小数原理知,存在 $m_{k}\in \mathbb{N}^{*}$ ,使得 $m_{k}=\min f^{-1}\left(k\right)$ .

下面先证明: $g\left(m_{k}\right)=k$ . $(*)$

对 $k$ 归纳,当 $k=1$ 时,由 $g\left(m_{1}\right)\leqslant f\left(m_{1}\right)=1$ 结合 $g^{-1}\left(m_{1}\right)\in \mathbb{N}^{*}$ ,知 $g\left(m_{1}\right)=1$ .即 $(*)$ 对 $k=1$ 成立.

现设 $(*)$ 对所有小于 $k$ 的正整数都成立,即 $g\left(m_{1}\right)=1$ , $\cdots$ , $g\left(m_{k-1}\right)=k-1$ ,讨论 $g\left(m_{k}\right)$ 的值.

首先, $g\left(m_{k}\right)\leqslant f\left(m_{k}\right)=k$ ,其次 $\left\{g\left(m_{1}\right),\cdots ,g\left(m_{k-1}\right)\right\}=\left\{1,2,\cdots k-1\right\}$ , $g$ 是单射,而由 $m_{i}$ 的定义知 $m_{1},\cdots ,m_{k}$ 两两不同,故 $g\left(m_{k}\right)\geqslant k$ .从而 $g\left(m_{k}\right)=k$ .所以, $(*)$ 对 $k\in \mathbb{N}^{*}$ 都成立.

利用 $(*)$ 和 $g$ 为单射,可知 $g$ 为 $\mathbb{N}^{*}$ 到 $\mathbb{N}^{*}$ 上的一一对应.现在对任意 $n\in \mathbb{N}^{*}$ ,记 $g\left(n\right)=k$ .,由 $g$ 为一一对应及 $(*)$ 知 $n=m_{k}$ ,从而 $f\left(n\right)=f\left(m_{k}\right)=k$ ,所以 $f\left(n\right)=g\left(n\right)$ 命题获证.

2022-02-22-01

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

是否存在一个由整数组成的数列 $\left\{a_{n}\right\}$ ?使得 $0=a_{0}<a_{1}a_{1}<<a_{2}<\cdots$ ,并且符合下面的两个条件:

(1)每一个正整数都可以表示为a $_{j}+a_{j}$ ( $i,j\geqslant 0$ ,可以相同)的形式;

(2)对任意正整数 $n$ ,都有 $a_{n}>\dfrac{n^{2}}{16}$ .

解

对 $n\in \mathbb{N}^{*}$ ,设 $a_{n}$ 是二进制表示中仅在偶数位上出现数码1或仅在奇数位上出现数码1的正整数从小到大的排列中的第 $n$ 项.我们证明:此数列 $\left\{a_{n}\right\}$ 符合条件.

利用正整数的二进制表示可知(1)成立,只需证明(2)亦成立.考虑所有小于 $2^{2r}$ 的非负整数,它们在二进制表示下都为 $2r$ 位数(不足位的前面补上0),其中偶数位都为零的数有 $2^{r}$ 个,奇数位都为零的数有 $2^{r}$ 个,只有0在两类数中同时出现,因此,数列 $\left\{a_{n}\right\}$ 中恰有 $2^{r+1}-1$ 个数小于 $2^{2r}$ ,故 $a_{2^{r+1}-1}=2^{2r}$ .

对 $n\in \mathbb{N}^{*}$ ,设 $2^{r+1}-1\leqslant n<2^{r+2}-1$ , $r\in \mathbb{N}$ ,则由 $\left\{a_{n}\right\}$ 的定义知 $a_{n}\geqslant a_2^{r+1}-1=2^{2r}=\dfrac{1}{16}\times 2^{2\left(r+2\right)}>\dfrac{n^{2}}{16}$ .

所以,存在满足的数列 $\left\{a_{n}\right\}$ .

高中奥数 2022-02-22

猜你喜欢

热点阅读