资源描述：
《数学竞赛中的组合数论问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数学竞赛中的组合数论问题 代数、几何、数论轮、组合是奥林匹克数学的主要内容，数学竞赛中常常遇到这样一些题目，这些题目把组合知识和数论知识交汇在一起，使得竞赛题目更有活力．我们姑且把这类题目叫做“组合数论”问题．组合数论问题大致有两类，一类是用组合数学的原理解决数论问题，另一类是用数论知识解决组合问题． ．从两道经典的数论问题谈起．1．狄利克雷（Dirichlet1805-1859）定理．设为无理数，则对任意的正整数，存在整数，其中，并且．证明 将区间分成等份，每份长为．考虑个数，．这里是的小数
2、部分，即 ．因而．由于把个数，放入个长为的区间，由抽屉原理，必有两个数在同一区间，设为和，，且．则有 ．从而 ，令，，则上式化为，因为为无理数，所以等号不可能成立．因而． 狄利克雷应用抽屉原理导出了他的有理数逼近定理，这是历史上第一次应用抽屉原理获得的不平凡结果，是一项很好的原创性工作，所以抽屉原理又称狄利克雷原理．2．证明不定方程没有正整数解．证明 假设不定方程有正整数解，在所有的解中一定有一组解，它的值比其余组解的值小．（这是极端原理的体现，极端原理的一种形式是在
3、一个有限正整数集合中，必有一个最小数．）因而，存在一个最小的正整数，使得 ，． ①有解．这时，不然的话，就有，且 ．但，与的假定矛盾．由的正整数解的结果可知，①中的和必定一为奇数，一为偶数，不妨假定为偶数，则有 ②其中，，且和一为奇数，一为偶数．因此，，且，．这时因为，若，，则，此时不可能为平方数．于是由 ，有 ，这里，且和一为奇数，一为偶数．由，有，因为两两互质，则它们都是某个整数的平方．即 ，
4、所以 ．于是是①的一组解．这时，．与的最小性矛盾．这个证明方法叫无穷递降法，是从极端原理出发的一种证法．这一命题是Fermat大定理的一个组成部分，1637年法国数学家费马（PierredeFermat，1601～1665）提出了下面的猜想：当时，方程没有正整数解．因为大于的整数必能被或奇质数整除，因此，如果对于或等于任意奇质数，方程都没有正整数解，那么费马问题就全部解决。本题如果能够证明正确的话，则没有正整数解就必然正确。这是因为若有正整数解，则也有正整数解．上面两个问题是数论中的经典问
5、题，而解决这两个问题，依赖于抽屉原理和极端原理这两个组合数学常用的原理．从而也给出了用组合知识解决数论问题的范例．二．用组合知识解决数论问题举例用抽屉原理解数论问题【例1】证明存在无穷多个正整数,这些数都是的倍数,而且这些数写成十进制数后,出现的个数相等(规定：首位前面的不算). （奥地利MO，2005年）【证】首先注意到令.设,即考虑集合,中的个元素,对若中存在一个,使,又由的个位数是,且,则此是的倍数,并且出现的个数相等;若中没有一个元素是的倍数,则这个元
6、素,对最多有个余数,由抽屉原理,必有两个元素对同余,设这两个元素为,则.而,因为,则.又因为的个位数是,则符合题目要求.【例2】求具有以下性质的最小正整数,使得对于任一选定的个整数,至少存在两个数,他们的和或差能被整除. （澳大利亚MO，1991年） 【解】若,即取个整数,例如取：.由于,,所以,任两个数的和与差都不是的倍数.设.并设是任意给定的个整数.若存在,使得,则差能被整除.若任意两个对均不同余,考虑的最小绝对剩余不妨设，此时由于，所以，至少有两个不同的数
7、，使得，此时有.【例3】若个正整数的乘积,恰好有个不同的质因数,证明这个正整数中,或者有一个是完全平方数,或者有某几个数的乘积是完全平方数.（莫斯科MO1986年）【证】设这个正整数的集合为,则有个非空子集.我们求出每个子集中的所有元素之积,并且将乘积表示成最大可能的完全平方数与一些质数的乘积的形式(例如,,).再将上述的乘积除以最大可能的完全平方数,就可以得到一些质数的乘积,这样一来,每一个子集中的所有元素之积对应一个质数的集合或空集(例如,上面的两个例子有).由以上,这个正整数的集合的每一个
8、子集都对应一个质数的集合或空集.由于个正整数的乘积,恰好有个不同的质因数,设这个不同的质因数的集合为,所以,上述这些质数的集合都是集合的子集,而这种子集共有个.由于,由抽屉原则,一定会有的两个不同的子集和对应着的同一个子集.因为,和中的数字之积分别具有和的形式.其中是正整数.于是是完全平方数.如果,则中的数都连乘了两次,即多乘了一个完全平方数,因此,划去和的公共元素之后,所剩下的数的乘积仍然是一个完全平方数.【例4】在三维欧氏空间中，任意给定个整点,其中任意三点不共线.证明:可以从中找到这样的三
