美文网首页奥数自学研究
高中奥数 2022-02-11

高中奥数 2022-02-11

作者: 天目春辉 | 来源:发表于2022-02-11 07:35 被阅读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.证明:不存在正整数km,使得对任意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(**)
    如果存在km\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

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