数学竞赛中的组合数论问题..doc

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