初中竞赛题选讲 第四百五十五题解答

本题目选自 2021北欧数学奥林匹克

黑板上写有若干个大于的整数. 诺迪对其进行如下操作: 在每一步中, 诺迪在黑板上写下满足如下条件的最小整数:
这个数比黑板上已有的每个数都大.
黑板上已有的每个数都不能整除这个数.
求证: 在某一步之后, 诺迪写下的全是素数.

证明: 设初始时黑板上最大的整数为.
诺迪写下的整数为:
我们首先证明, 任意一个大于的素数,必然会出现在黑板上.
反证: 假设素数未出现在黑板上, 由于数列为单增的无穷数列, 则必存在正整数, 使得
注意到我们写下之后,满足诺迪要求的两个条件, 且比小, 故不为满足条件的最小整数, 矛盾!

于是假设不成立, 即任意一个大于的素数,必然会出现在黑板上.
对任意合数, 若存在素数使得, 由于, 可能需要些时已经出现在了黑板上, 故必不可能出现在黑板上.
于是对任意黑板上出现的合数, 它的所有素因子一定小于.

下面我们证明一个引理:

引理: 给定自然数, 已知为素数.无穷数列中每个数都不含之外的素因子. 则必存在正整数,使得.

引理的证明: 对进行归纳.时,显然满足条件.

对数列, 若存在正整数, 使得对任意的自然数, 均有,则必存在正整数, 使得,的正整数有无穷多个. 此时转化为个素因子的情况, 由归纳原理知显然成立.

反之, 若满足的正整数有无穷多个.

则对这无穷多个数组成的新数列, 再考虑满足的正整数是否有无限个. 若为有限个, 则由归纳原理知结论成立.

若为无限个, 继续考虑这满足条件的数组成的无穷项的新数列....

若每一步均为无限个, 则我们必可以得到一个正整数, 使得对任意,均有, 此时为的倍数.

引理证毕.

回到原题目, 由于对任意黑板上出现的合数, 它的所有素因子一定小于, 故这些合数所组成的数列的素因子个数为有限个. 由引理知, 若这些合数为无穷个, 则必存在倍数关系. 于是这样的合数只有有限个. 当这有限个合数被列举完之后, 再列出的正整数必为素数.

证毕.

(0)

相关推荐

  • 韦东奕封神之题——2009IMO蚱蜢跳跃题详解,看完解析你也能做

    引言 本文给出 2009 年第五十届 IMO 压轴第六题的详细解答,据传当年韦东奕凭借此题甚至"击败"了陶哲轩.据悉,陶哲轩耗费 7 个小时才解决此题,而韦东奕仅花费 1 小时.本 ...

  • 质数:素数定理(1)

    素数的重要性在于这一事实:每一个整数都能表示为素数的乘积.如果一个数本身不是素数,那么可以不断对它进行因子分解,直到所有的因子都是素数为止.--R·柯朗 2021 03.14 作者序言 小贺 当我做素 ...

  • 初中竞赛题选讲 第四百七十七题解答

    本题目选自 第十八届中国东南地区数学奥林匹克 高一组 如图所示, 在圆内接四边形 中, 是边 内一点, 是线段 上一点, 是 外角平分线上一点, 满足 . 证明: . 证明:由,得 共圆. 于是 即, ...

  • 初中竞赛题选讲 第四百九十三题解答

    本题目选自 2021中欧数学奥林匹克

  • 初中竞赛题选讲 第三百五十七题解答

    本题目选自 2020土耳其数学奥林匹克 第二轮 已知正整数 ,集合 .若正整数 满足, 对 的任一 元子集, 其中必存在元素 ,使得 ,求 的最小值. 解:考虑问题的反面, 即求 的最大值, 使得存在 ...

  • 初中竞赛题选讲 第三百二十一题解答

    已知有若干个硬币堆,每个堆中有至少一个硬币.对他 们进行如下操作: 任选两个硬币个数之和为偶数的硬币堆, 将它们合成一堆,再均分为个数相同的两堆. 若按某种方案将若干个硬币分成若干堆之后,可以经过若 ...

  • 初中竞赛题选讲 第一百六十九题解答

    银行发行了一种硬币,一面是 H,另一面是 T.培神 有 枚这样的硬币,并把它们从左到右排成一行. 他重复进行以下操作: 如果存在有硬币 H 面朝上, 培神可以挑选连续的若干枚硬币(至少一枚)将它们] ...

  • 初中竞赛选讲 第三百九十四题的解答

    三角形 内接于圆 , 为三角形 内心.设 为劣弧 的中点, 为弧 的中点,圆 交圆 于 ,设 关于 的对称点为 ,延长 交圆 于 ,求证: . . . 四点共圆. 证明: 设 的内切圆 分别与 切于点 ...

  • 十万个冷知识(四百二十五)

    中国人的脸,在菲律宾是土豪的象征,菲律宾70%的经济,都掌握在华裔手中.菲国内10大富豪有8位是祖籍福建的华人. 小编:菲律宾人对待金钱的态度很随意,没钱有没钱的快乐,你不懂--"寅吃卯粮& ...

  • 认知世事(四百八十五)

    时间一天天的过,人生不过几十年, 匆忙人生路,有酸有甜,有苦有乐, 要少些抱怨,多些宽容,把握幸福, 要珍惜光阴,坚持奋斗,放飞梦想.

  • 认知世事(四百七十五)

    想开一点,很多事不值得总放在心间: 看淡一点,不要太在乎别人的那张脸: 简单一点,不要用他的尺子衡量长短.