• 同余理论在数学竞赛中的应用

     

       【摘要】 具有悠久历史的数学竞赛已逐渐形成一门特殊的数学学科――竞赛数学. 本文从数学竞赛这个大范围入手,着眼于数论在数学竞赛中的地位和作用,选择中国剩余定理作为切入点,介绍了同余理论的系统知识及同余性质的一些简单应用,并对数学竞赛中有关同余理论的应用作了系统的划分. 每一部分都有2 ― 4个例题加以举例说明.
    中国论文网 /9/view-9299365.htm
       【关键词】 同余 同余理论 数学竞赛
      
       一、数学竞赛数论同余
      
       数学竞赛是一种有组织的,在规定时间之内进行的解数学题的竞赛,是人类智慧的灵活、力量与完美的较量.
       数学竞赛历史悠久,而且在最近10年有很大的发展和变化. 并且随着数学竞赛的发展,已逐渐形成一门特殊的数学学科――竞赛数学,也可称为奥林匹克数学. 将高等数学下放到初等数学中去,用初等数学的语言来表述高等数学的问题,并用初等数学方法来解决这些问题,这就是竞赛数学的任务. 数论这门学科最初是从研究整数开始的,所以叫做整数论. 后来整数论又进一步发展,就叫做数论了.
       近几十年来,初等数论在计算机科学、组合数学、代数编码、信号的数字处理等领域内得到了广泛的应用. 而且初等数论在各类数学竞赛中占有重要的地位. 国际数学奥林匹克(IMO)从1959年到2005年中,已经举行了46届竞赛,在总共的278道题目中,约有四分之一的题目是主要用初等数论知识来解的,如果加上涉及用初等数论知识来解的题目,那所占的比例可达到一半左右.
       初等数论的主要内容大致可分为四部分:①整除理论,②不定方程,③同余,④原根与指标.
      
       二、同余理论在数学竞赛中的应用
      
       (一) 同余的性质以及几个重要的定理
       1. 同余的定义、性质
       定义 给定正整数m,如果整数a与b 之差能被m整除,则称a与b 对于模m同余,或称a与b同余,模 为m,记为a ≡ b(mod m),
       此时也称b是a 对模m的同余.
       性质
      
       2. 剩余类和完全剩余系
       全体整数集合可按模m来分类:当且仅当a≡b(mod m)时,a和b属于同一类.于是全体整数按模m被分为m类,每一个这样的类被称为模m的剩余类.在 m个剩余类中各取一个数作为代表,这样的m个数被称为模m的完全剩余系.例如0,1,2,…,m - 1是模m的一个完全剩余系,称为最小非负完全剩余系.
       完全剩余系有下列性质:
      
       定理3、定理4也是同余理论中重要的定理,在求解同余方程的问题中有非常重要的作用,这里虽不做详细的应用介绍,但对于广大参加数学竞赛的学生还是希望能对其加以重视.
       (二) 同余理论用于处理有关整除的问题
       整除与同余是密切相关的,有些整除问题在解答过程中常常是同余理论的灵活运用.
       例1 (第六届奥赛试题)(1)证明:求出所有正数n 使2n-1能被7整除; (2)没有正整数n能让2n + 1 被7整除.
      
       (三) 同余理论用于求解不定方程
       对于一次不定方程的存在性的解法已有一套完整的理论来解决,但若将这些方程转化成线性同余式则解题更简捷.
       例2 (第23届IMO试题) 试证:(1)如果正整数n及方程x3 - 3xy2 + y2 = n有一组整数解(x,y),那么这个方程至少有三组整数解.
      
       综上所述,方程x3 - 3xy2 + y3 = 2891无整数解.
       (四)同余理论用于分配问题
       例3 一位魔方制造商把他的产品装在大方盒子(正方体)里运给批发商. 一位批发商从大方盒中取出一行魔方,试验看是否有毛病,但在试验中,这些魔方毁坏了,其余的魔方用小盒包装,每盒装6个,那么装到最后会剩下几个魔方?
       分析 此题看似复杂,其实用同余的观点处理却非常简单.设一行有n个魔方,则大方盒中总共装有n3个,做完试验后,大方盒中还有n3 - n个魔方,于是问题转化为求n3 - n ≡ ?(mod 6).
       解 因为n3 - n = n(n - 1)(n + 1)为三个连续自然数之积,所以n3 ≡ 0(mod 6).
       故不论大方盒的大小如何,试验后按6个一小盒装总可以全部装完.
       (五)构造剩余系解题
       利用完全剩余系常常可以帮助我们巧妙地解答某些试题.
       例4 设自然数n ≤ 2006,试求其中使3n除7的余数为1的所有n的和.
       解 由题意,即求满足3n ≡ 1(mod 7)(8)
      的所有n的和. 而
      
       例5 (第23届全俄中学奥林匹克竞赛试题,11年级)巫士委员会以如下方式接受考核:国王把所有巫士排成一队,然后给每个巫士戴上从白色、蓝色、红色帽子中任意选取的一顶帽子,每个巫士都能够看到站在其前面所有人的帽子颜色,但看不见自己所戴帽子的颜色,也看不到站在他后面的人的帽子颜色.要求每分钟都有巫士报出三种颜色中的一种(允许同时报).报完之后国王就处死那些将自己所戴帽子颜色判断错了的巫士.在议事举行前,这100个巫士达成一致:尽量将叛死刑的人数降到最低.问:有多少个巫士一定可以免受惩罚?
       解 第一个猜的巫士因为没有任何信息帮助他确定其所戴帽子的颜色,所以不管猜什么颜色,都只是一个随机的猜测,那么就不能担保100个巫士全部免受惩罚.
       但采用如下的办法,可保证99个巫士免受惩罚.
       首先由站在队伍末尾的巫士报出一种颜色,接着由站在他前面的人报,如此继续,最后直到站在首位的巫士报出一种颜色.
       分别用三个数字来代表三中颜色:白色为0,蓝色为1,红色为2.最后一个巫士将站在前面的所有巫士的帽子颜色数目相加,再去3去除这个和,并报出余数相应的帽子颜色,记该余数为S1.倒数第二个巫士也将其前方的所有帽子颜色数目相加,用3去除和得一余数,该余数记为r2,那么倒数第二个巫士所戴帽子的颜色数目为 S2 = S1 - r2(mod 3),从而也能都准确报出自己所戴帽子的颜色,使自己免受惩罚.
       令Sn为倒数第n个巫士所报的帽子的颜色数目, rn为倒数第n个巫士将他前方所有的帽子颜色数目相加所得的和用3除之后所得的余数.因而,只要有了递归数列{Sn},即Sn ≡ S1- Sk - rn(mod 3),0 ≤ Sn ≤ 2,倒数第n(n > 1 )个巫士就能准确地报出自己所戴帽子的颜色.
       以上是同余理论在一些数学竞赛中的有关应用,而鉴于同余理论在数论中的特殊地位,若要灵活地掌握和应用它,还需加强对数论知识的系统、有效的学习. 同余理论在数学竞赛中的应用是相当广泛的,而且不论是《初中数学竞赛大纲》还是《高中数学竞赛大纲》都规定有相应的同余理论的内容,所以广大竞赛学生应该对同余理论加以足够的重视.
      
      注:“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”

    转载请注明来源。原文地址:https://www.xzbu.com/9/view-9299365.htm

    上一篇:以结对竞赛构建学生主体互动关系

    下一篇:走出观摩课、竞赛课的误区


    相关文章: