高中奥数 2022-01-26

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

2022-01-26-01

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

在坐标平面上任给一条起点为 $\left(0,0\right)$ ,终点为 $\left(1,0\right)$ 的折线.证明:对任意 $n\in \mathbb{N}^{*}$ ,在该折线上存在两点,它们的纵坐标相同,而横坐标相差 $\dfrac{1}{n}$ .

证明

先建立一个引理:对任意 $\alpha\in \left(0,1\right)$ ,折线上存在两点,它们的纵坐标相同,横坐标相差 $\alpha$ 或 $1-\alpha$ .

事实上,设 $\Gamma$ 为题中所给的折线, $\Gamma_{1}$ 为 $\Gamma$ 向左平移 $\alpha$ 个单位得到的折线, $\Gamma_{2}$ 为向右平移 $1-\alpha$ 个单位得到的折线,容易得到 $\Gamma$ 与 $\Gamma_{1}\Cup\Gamma_{2}$ 至少有一个交点,而这就是引理要求的结果(如图所示,从 $\Gamma$ 的最高点与最低点出发讨论即可知 $\Gamma$ 与 $\Gamma_{1}\Cup\Gamma_{2}$ 有交点).

下面利用引理来证明需要的结论.

取 $\alpha= \dfrac{1}{2}$ ,可知 $n=2$ 时,结论成立;取 $\alpha=\dfrac{1}{3}$ ,则折线上有两点 $A$ 、 $B$ ,使得 $AB//x$ 轴,且 $\left|AB\right|=\dfrac{1}{3}$ 或 $\left|AB\right|=\dfrac{2}{3}$ ,若 $\left|AB\right|=\dfrac{1}{3}$ ,则 $n=3$ 已成立,若 $\left|AB\right|=\dfrac{2}{3}$ ,则考虑连结 $A$ 、 $B$ 的 $\Gamma$ 的子折线,利用引理及 $n=2$ 的结论,可知该子折线上存在点 $C$ 、 $D$ ,使 $CD//AB$ ,且 $\left|CD\right|=\dfrac{1}{2}\left|AB\right|=\dfrac{1}{3}$ ,故 $n=3$ 时,结论也成立.

依此类推,结合数学归纳法,可知结论对任意 $n\geqslant 2$ 均成立.

2022-01-26-02

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

有一个黑盒和标号为 $1,2,\cdots ,n$ 的 $n$ 个白盒,在 $n$ 个白盒中共放了 $n$ 个白球,允许进行如下操作:若标号为 $k$ 的白盒中恰有 $k$ 个白球,则从中取出这 $k$ 个球,分别在黑盒和标号为 $1,2,\cdots ,k-1$ 的白盒中各放入一个球.

证明:对任意 $n\in \mathbb{N}^{*}$ ,存在唯一的一种放置方式,使得 $n$ 个球最初全在白盒中,但经有限次操作后, $n$ 个球全部在黑盒中.

证明

先用数学归纳法证明存在性.

当 $n=1$ 时,显然存在;设 $n$ 时,存在满足条件的放法 $T$ ,考虑 $n+1$ 的情形,这时先将 $n$ 个球依放法 $T$ 放入标号为 $1,2,\cdots ,n$ 的白盒中,并设放好后,最小的空盒号码为 $i\left(1\leqslant i\leqslant n\right)$ ,则依下法放入第 $n+1$ 个球:从 $1,2,\cdots ,i-1$ 号白盒中各取一个球放入第 $i$ 号盒中,并将第 $n+1$ 个球也放入 $i$ 号盒中,易知这样的放置方法满足条件.

再用数学归纳法(仍对 $n$ 归纳)证明:放法是唯一的.

当 $n=1$ 、 $2$ 时,唯一性显然成立;设对 $n\left(\geqslant 2\right)$ 时,满足条件的放置方法只有一种,记为 $T$ .

易知 $n+1\geqslant 3$ 时,满足条件的放法中,第 $n+1$ 个白盒子必为空盒,于是,若 $n+1$ 时存在两种满足条件的放法 $T_{1}$ 和 $T_{2}$ .注意到,第 $n+1$ 号白盒(为空盒)可以拆走,并且 $T_{1}$ 与 $T_{2}$ 经一步操作后,白盒中有 $n$ 个球,白盒个数也为 $n$ 个,故它们都变为 $T$ .

设 $T_{1}$ 、 $T_{2}$ 的第一次操作的白盒号分别为 $i_{1}$ 、 $i_{2}$ .若 $i_{1}>i_{2}$ ,则 $T_{1}$ 经第一次操作后第 $i_{2}$ 号白盒中有至少1个球,而 $T_{2}$ 经第一次操作后第2号白盒中没有球,不能都变为 $T$ ,所以 $i_{1}\leqslant i_{2}$ ,同理 $i_{2}\leqslant i_{1}$ ,即有 $i_{1}=i_{2}$ .这时 $T_{1}$ 、 $T_{2}$ 中盒号大于 $i_{1}$ 的白盒子中的球数相同,小于 $i_{1}$ 的白盒子中的球数也相同(否则, $T_{1}$ 与 $T_{2}$ 经一次操作后,不能都变为 $T$ ),因此 $i_{1}$ 号盒中的球数也相同,从而 $T_{1}=T_{2}$ .

这表明,存在唯一的满足条件的放置方法.

2022-01-26-03

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

设 $R_{0}$ 是一个 $n$ 元数组,其中每个数都属于 $\left\{A,B,C\right\}$ .定义序列 $R_{0},R_{1},R_{2},\cdots$ 如下:如果 $R_{j}=\left(x_{1},\cdots,x_{n}\right)$ ,那么 $R_{j+1}=\left(y_{1},y_{2},\cdots,y_{n}\right)$ ,这里

$y_{i}=\begin{cases} x_{i},&\text{若}x_{i}=x_{i+1},\\ \left\{A,B,C\right\}\backslash \left\{x_{i},x_{i+1}\right\},&\text{若}x_{i}\neq x_{i+1}. \end{cases}$

其中 $x_{n+1}=x_{1}$ .例如:若 $R_{0}=\left(A,A,B,C\right)$ ,则 $R_{1}=\left(A,C,A,B\right)$ , $R_{2}=\left(B,B,C,C\right)$ , $\cdots$ .

(i)求所有的 $n\in \mathbb{N}^{*}$ ,使得存在 $m\in \mathbb{N}^{*}$ ,满足:对任意 $R_{0}$ 都有 $R_{m}=R_{0}$ .

(ii)对 $n=3^{k}\left(k\in \mathbb{N}^{*}\right)$ ,求满足(i)的最小正整数 $m$ .

解

(i)分别用 $0$ 、 $1$ 、 $2$ 表示 $A$ 、 $B$ 、 $C$ ,在模3的意义来把握序列 $R_{0},R_{1},\cdots$ 的变化情况.

设 $R_{j}=\left(x_{1},\cdots,x_{n}\right)$ , $R_{j+1}=\left(y_{1},y_{2},\cdots,y_{n}\right)$ ,则对 $1\leqslant i\leqslant n$ ,均有 $y_{i}\equiv -\left(x_{i}+x_{i+1}\right)\left(\bmod 3\right)$ .

如果 $n$ 为偶数,取 $R_{0}=\left(1,2,1,2,\cdots,1,2\right)$ ,那么对任意 $m\geqslant 1$ ,均有 $R_{m}=\left(0,0,\cdots,0,0\right)$ ,所以此时不存在符合要求的正整数 $m$ .

如果 $n$ 为奇数,由于不同的 $n$ 元数组 $\left(x_{1},\cdots ,x_{n}\right)$ 至多 $3^{n}$ 组,故对任意 $R_{0}$ ,存在 $m_{R_{0}}\in \mathbb{N}^{*}$ ,及 $k\in \mathbb{N}$ ,使得 $R_{k}=R_{m_{R_{0}}+k}$ .

我们证明:若 $k\geqslant 1$ ,则 $R_{k-1}=R_{m_{R_{0}}+k-1}$ (从而依此类推可知 $R_{0}=R_{m_{R_{0}}}$ ).

事实上,设 $R_{k-1}=\left(x_{1},\cdots,x_{n}\right)$ , $R_{m_{R_{0}}+k-1}=\left(y_{1},\cdots,y_{n}\right)$ ,则由 $R_{k}=R_{m_{R_{0}}+k}$ ,可知 $-\left(x_{i}+x_{i+1}\right)\equiv -\left(y_{i}+y_{i+1}\right)\left(\bmod 3\right)$ ,所以 $\sum\limits_{j=1}^{n}\left(-1\right)^{j}\left(x_{j}+x_{j+1}\right)\equiv \sum\limits_{j=1}^{n} \left(-1\right)^{j}\left(y_{j}+y_{j+1}\right)\left(\bmod 3\right)$ ,结合 $n$ 为奇数,可知 $-x_{1}+\left(-1\right)^{n}x_{n+1}\equiv -y_{1}+\left(-1\right)^{n}y_{n+1}\left(\bmod 3\right))$ ,即 $-2x_{1}\equiv -2y_{1}\left(\bmod 3\right)$ , $x_{1}\equiv y_{1}\left(\bmod 3\right)$ ,所以 $x_{1}=y_{1}$ ,同理可证对 $i\in \left\{2,\cdots,n\right\}$ ,均有 $x_{i}=y_{i}$ ,所以 $R_{k-1}=R_{m_{R_{0}}+k-1}$ .

依上可知,对任意 $R_{0}$ ,存在 $m_{R_{0}}$ ,使得 $R_{0}=R_{m_{R_{0}}}$ ,于是,在 $R_{0}$ 变化时,取所有 $m_{R_{0}}$ 的最小公倍数 $m$ ,则对任意 $R_{0}$ ,均有 $R_{0}=R_{m}$ .

综上可知,当且仅当 $n$ 为奇数时,存在满足条件的 $m$ .

(ii)对 $n=3^{k}$ , $k\in \mathbb{N}^{*}$ ,满足条件((i)中的条件)的 $m$ 的最小值 $m=3^{k}$ .

事实上,对任意 $R_{0}=\left(x_{1},\cdots,x_{n}\right)$ ,设 $R_{3^{k}}=\left(y_{1},\cdots,y_{n}\right)$ ,则由前推出的模3意义下的关系式,易知

$y_{p}\equiv -\sum\limits_{i=0}^{3^{k}}\mathrm{C}_{3^{k}}^{i}x_{i+p}\left(\bmod 3\right),$

这里 $x_{i+p}$ 的下标在模 $n$ 的意义下取值, $p=1,2,\cdots ,n$ .注意到对 $1\leqslant i\leqslant 3^{k}-1$ , $\mathrm{C}_{3^{k}}^{i}\equiv 0\left(\bmod 3\right)$ ,所以 $y_{p}\equiv -x_{p}-x_{3^{k}+p}\equiv -2x_{p}\equiv x_{p}\left(\bmod 3\right)$ ,从而 $R_{3^{k}}=R_{0}$ .

另一方面,设 $R_{0}=\left(0,0,\cdots,0,1\right)$ ,则对 $0<m<3^{k}$ , $R_{m}$ 的第 $3^{k}-m$ 个分量不等于0,所以满足(i)的 $m$ 的最小值为 $3^{k}$ .

高中奥数 2022-01-26

猜你喜欢

热点阅读