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

数学竞赛中的组合数论问题 　　　　数学竞赛中的组合数论问题 　代数、几何、数论轮、组合是奥林匹克数学的主要 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 ，数学竞赛中常常遇到这样一些题目，这些题目把组合知识和数论知识交汇在一起，使得竞赛题目更有活力．我们姑且把这类题目叫做“组合数论”问题．组合数论问题大致有两类，一类是用组合数学的原理解决数论问题，另一类是用数论知识解决组合问题． 　　．从两道经典的数论问题谈起． 1．狄利克雷（Dirichlet 1805-1859）定理． 设 为无理数，则对任意的正整数 ，存在整数 ，其中 ，并且 ． 证明　将区间 分成 等份，每份长为 ． 考虑 个数 ， ．这里 是 的小数部分，即 　　　　 ． 因而 ． 由于把 个数 ，放入 个长为 的区间，由抽屉原理，必有两个数在同一区间， 设为 和 ， ，且 ． 则有　　　　　　 ． 从而　　　　　　 ， 令 ， ，则上式化为 ， 因为 为无理数，所以等号不可能成立． 因而 ． 　　狄利克雷应用抽屉原理导出了他的有理数逼近定理，这是历史上第一次应用抽屉原理获得的不平凡结果，是一项很好的原创性工作，所以抽屉原理又称狄利克雷原理． 2．证明不定方程 没有正整数解． 证明　假设不定方程 有正整数解 ，在所有的解中一定有一组解，它的 值比其余组解的 值小．（这是极端原理的体现，极端原理的一种形式是在一个有限正整数集合中，必有一个最小数．）因而，存在一个最小的正整数 ，使得 　　　　 ， ．　　　　　　　　　　　　① 有解．这时 ，不然的话，就有 ，且 　　　　　　 ． 但 ，与 的假定矛盾．由 的正整数解的结果可知，①中的 和 必定一为奇数，一为偶数，不妨假定 为偶数，则有 　　　　 　　　　　　　　　　　　　② 其中 ， ，且 和 一为奇数，一为偶数． 因此 ， ，且 ， ． 这时因为，若 ， ，则 ，此时不可能为平方数． 于是由　　　　　　 ， 有　　　　　 ， 这里 ，且 和 一为奇数，一为偶数． 由 ，有 ， 因为 两两互质，则它们都是某个整数的平方．即 　　　　　　　 ， 所以　　　　 ． 于是 是①的一组解． 这时， ．与 的最小性矛盾． 这个证明 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 叫无穷递降法，是从极端原理出发的一种证法． 这一命题是Fermat大定理的一个组成部分，1637年法国数学家费马（Pierre de Fermat，1601～1665）提出了下面的猜想：当 时，方程 没有正整数解．因为大于 的整数必能被 或奇质数整除，因此，如果对于 或 等于任意奇质数，方程都没有正整数解，那么费马问题就全部解决。本题如果能够证明正确的话，则 没有正整数解就必然正确。这是因为若 有正整数解，则 也有正整数解． 上面两个问题是数论中的经典问题，而解决这两个问题，依赖于抽屉原理和极端原理这两个组合数学常用的原理．从而也给出了用组合知识解决数论问题的范例． 二．用组合知识解决数论问题举例 用抽屉原理解数论问题 【例1】证明存在无穷多个正整数,这些数都是 的倍数,而且这些数写成十进制数后, 出现的个数相等( 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 ：首位前面的 不算). 　　　　　　　　　　　　　　　　　　　（奥地利MO， 2005年） 【证】首先注意到 令 . 设 ,即 考虑集合 , 中的 个元素,对 若 中存在一个 ,使 ,又由 的个位数是 ,且 ,则此 是 的倍数,并且 出现的个数相等; 若 中没有一个元素是 的倍数,则这 个元素,对 最多有 个余数,由抽屉原理,必有两个元素对 同余,设这两个元素为 ,则 . 而 ,因为 ,则 . 又因为 的个位数是 ,则 符合题目要求. 【例2】求具有以下性质的最小正整数 ,使得对于任一选定的 个整数,至少存在两个数,他们的和或差能被 整除. 　　　　　　　　　　　　　　　　　　 （澳大利亚MO， 1991年）　 【解】若 ,即取 个整数,例如取： . 由于 , , 所以,任两个数的和与差都不是 的倍数. 设 .并设 是任意给定的 个整数. 若存在 ,使得 ,则差 能被 整除. 若任意两个 对 均不同余,考虑 的最小绝对剩余 不妨设 ，此时由于 ， 所以，至少有两个不同的数 ，使得 ，此时有 . 【例3】若 个正整数的乘积,恰好有 个不同的质因数,证明这 个正整数中,或者有一个是完全平方数,或者有某几个数的乘积是完全平方数. （莫斯科MO 1986年） 【证】设这 个正整数的集合为 ,则 有 个非空子集. 我们求出每个子集中的所有元素之积,并且将乘积 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示成最大可能的完全平方数与一些质数的乘积的形式(例如, , ).再将上述的乘积除以最大可能的完全平方数,就可以得到一些质数的乘积,这样一来,每一个子集中的所有元素之积对应一个质数的集合或空集(例如,上面的两个例子有 ). 由以上,这 个正整数的集合 的每一个子集都对应一个质数的集合或空集. 由于 个正整数的乘积,恰好有 个不同的质因数,设这 个不同的质因数的集合为 ,所以,上述这些质数的集合都是集合 的子集,而这种子集共有 个. 由于 ,由抽屉原则,一定会有 的两个不同的子集 和 对应着 的同一个子集 . 因为, 和 中的数字之积分别具有 和 的形式.其中 是正整数. 于是 是完全平方数. 如果 ,则 中的数都连乘了两次,即多乘了一个完全平方数,因此,划去 和 的公共元素之后,所剩下的数的乘积仍然是一个完全平方数. 【例4】在三维欧氏空间中，任意给定 个整点,其中任意三点不共线.证明:可以从中找到这样的三个点,使得以它们为顶点的三角形的重心也是整点. （ IMO预选题， 1977年）　 【证】设 是空间中三个不共线的整点. 以它们为顶点的三角形的重心坐标 是 为了使 是整点,必须 即 考虑整数对于 的同余类. 个整点的第一坐标分属于 的同余类: 中的某一类,因而,必有 个整点属于同一类. 个第一坐标属于同一类的整点的第二坐标也分属于 的同余类中的某一类,因而,必有 个整点属于同一类. 对这 个第一坐标属于同一类,且第二坐标也属于同一类的整点的第三坐标分两种情形讨论: 1. 这 点中有 个点的第三坐标各属于 的同余类中的不同类,则这 个整点的第一坐标, 第二坐标对 同类, 第三坐标对 不同类,这 点的相应坐标的和均为 的倍数,因而, 以它们为顶点的三角形的重心也是整点. 2. 这 点中的第三坐标至多属于 的同余类中的两类,因而,必有 个整点属于同一类.此时,这 点的相应坐标分别属于 的同一类, 因而, 以它们为顶点的三角形的重心也是整点. 综上,问题得证. 【例5】设 是任意一个具有性质 的正整数的无穷数列，求证可以把这个数列的无穷多个 用适当的正整数 表示为 　　　　　　　 【证】将数列 按 分成若干个子数列． 因为数列 为无穷数列,而子数列只有有限个(不多于 个),由抽屉原理，至少有一个子数列有无穷多项． 　　现在考虑这个无穷子数列，因为数列是递增的，所以，一定有一个最小项 ，同时还有无穷多个 属于这个子数列，且 ． 　　因为这个无穷子数列对 是同余的，所以 ，即 　　　　　　　　　　 　　在上式中，令 ，则上式化为 ． 　　　因此，数 符合要求，而 又无穷多个。 【例6】求证：在40个不同的正整数所组成的等差数列中，至少有一项不能表示成 的形式． 　（IMO中国国家队选拔考试，2009年）　 【解】假设存在一个各项不同且均能表示成 的形式的 项等差数列． 设这个等差数列为 ，其中 ． 设 ， ，其中 表示不超过实数 的最大整数． 则 ． 我们研究这个数列中最大的 项 ． 首先证明： 中至多有一个不能表示成 或 的形式． 若 中的某一个 能表示成 或 的形式． 由假设，一定存在非负整数 ，使得 ． 由 的定义，可知 ． 又因为 不能表示成 或 的形式，则 ， 若 ，则 　 　　　　 　　　　 　　　　 　　　　 ． 与 矛盾； 若 ，则 　 　　　　 　　　　 　　　　 ． 与 矛盾； 因此，只有 ． 即 中至多有一个不能表示成 或 的形式． 所以 中至少有 个能表示成 或 的形式． 由抽屉原理，至少有 个能表示成 或 中的同一种形式． (1) 若有 个能表示成 的形式．设为 , 　　则 是某个公差为 的 项等差数列中的 项． 然而 ．显然 ， ， 所以 ，矛盾． (2) 若有 个能表示成 的形式．设为 , 则 是某个公差为 的 项等差数列中的 项． 然而 ,矛盾． 综上，假设不成立，故原题得证 用极端原理解数论问题 【例1】设 满足:对任何整数 及 中中任意数 可以相同), 均不是相邻整数之积,试定出所有元素个数最多的 . 　　　　　　　　　　　　　　（中国国家队选拔考试，2003年） 【证】由极端原理设 满足题目的条件,且 最大. 因为 , ① 由于 均不是相邻整数之积,则对任一 ,有 所以 . 因此, .② 把上述集合进行分拆,使每个子集中元素之和,恰满足①,可分拆为 个子集: 这 个子集的每一个子集至多有一个元素包含在 中,故 . 若 ,则每个子集恰好有一个元素包含在 中,因此, . 根据 ①,若 ,则 ,故 ,若 ,则 , ,则 , .若 ,则 ,从而可以有 . 若 ,则 , ,故 , ,则 , 故 . . 综合以上,满足要求的集合 【例2】证明存在无限多个正整数 ，使得对 有 　　　　　　　 其中 表示 的所有约数之和. 　（IMO预选题，1983年) 【证】假设结论不成立, 即只有有限个正整数 ,使得对 有 ,其中 . 设 是这些 中的最大者. 则数列 以 为上界(因为 ),并且对 ,有 , 这是因为 ,使得 . 因为 所以数列 也以 为上界. 因为当 时, ,则 , 由于 的约数是形如 的数与数 ,其中 ,因此 与数列 以 为上界矛盾. 结论得证. 【例3】证明：不存在整数 ，满足 ① (韩国数学奥林匹克，2003年) 【解】设 是方程①的整数解，显然由 可得 ．不妨设 ．进一步假设 是满足上述条件的最小解． 由 可知 是偶数， 是奇数． ①可化为　　　　 ．　　　　　　　　② 显然 ． 于是 ， 和 是一组勾股数，故存在一个奇数 和一个偶数 ，使得 　　　　 ，且 由此，存在一个整数 和一个奇数 ，使得 　　　　 ，　　 ． 于是　　 ． 由于 ，及 ， 所以存在整数 ，其中 ，使得 　　　　 或 由此得 ， 由于 ， ，故存在正整数 ， ，使得 　　　　 ，　 ． 因此，　 ． 这就回到②式．设 ， 则 ， 于是 是方程①的解，但是， ，与 的最小性矛盾． 所以方程没有整数解． 【例4】设 是一个正整数, 为 的各位数字之和,对于正整数 存在一个含有 个正整数的集合 ,对于任意的非空子集 , 的最小值设为 .证明:存在常数 ,使得 (34届美国MO. 2005年) 【证】设 是满足 的最小的正整数. 令 . 显然, 的任意一个非空子集的元素之和有 的形式,其中 . 由于 ,则第一项的末尾至少有 个 ,而第二项至多有 位数字, 的每位数字都是 ,且 .因此, 的各位数字之和就是 的各位数字之和加上 的各位数字之和,再减去 的各位数字之和,所以 的各位数字之和即为 的各位数字之和 . 因为 ,所以, . 因为,当 时, ,所以, 因此,取 ,可知右边的不等式成立. 设 是由 个正整数组成的集合, 使得对于任意的非空子集 ,均有 ,因为 总是与 关于 同余,所以, 对于所有的非空子集 ,均有 . 对 中的任意一个数 ,当 取一个不同于 的数 时,有 ,当 取两个数 时,有 . 于是, ,即 中的每个元素都是 的整数倍,且 设 是满足 的最大整数,使得 .由下面的引理1可知,有一个 的非空子集 ,使得 是 的倍数.再由引理2可得 .于是,由 的最大性,知 ,从而 ,因此,有 . 因此,取 ,可知左边的不等式成立. 引理1. 含有 个正整数的集合包含一个非空子集,其元素之和是 的倍数. 证.对任意 个正整数的集合 ,如果 中任意两个数对 同余,那么, . 否则,不妨设 ,考察下面的 数: 其中必有两个数对 同余,则其差是 的倍数.引理1得证. 引理2. 对 的任意一个整数倍数 ,都有 证.如果命题不成立,设 是符合条件但使得 成立的最小正整数,则由 ,知 ,因此, ,即 是一个至少为 位的正整数. 设 是一个 位数,则 .令 ,则 记 则 ,其中 . 现在有 即 .这与 的最小性矛盾.引理2得证. 于是本题得证. 三用数论知识解决组合问题 【例1】将集合 分拆为 个互不相交的非空子集 的并。若对于每一个 ，其中任意两个不同的元素的和都不是完全平方数，求 的最小值. 　　　　　　　　　　　　　　　　　　　　（福建高一数学竞赛，　2006年） 【证】首先考虑数 . 因为 所以,这三个数必须属于三个不同的子集. 于是, . 另外, 集合 分拆为 个互不相交的非空子集 的并,使得它们满足题设条件.令 容易验证 满足题设条件. 所以, 的最小值为 . 　　【例2】平面上有 个不同的点,任意两点之间的距离为整数,这些点两两之间用线段连接.求证：至少存在 条线段,使得这些线段长度之和是 的倍数. 【证】首先证明:当 时,对于 个点之间的 条线段中一定有一条线段的长度是 的倍数. 设 是平面上的不同的四点,如图, 设 . 由余弦定理得 用反证法.假设 都不是 的倍数,则有 , 所以有 , ① 于是, 因为 是整数, 由余弦定理可得 是有理数. 设 由①得 所以, ,(否则,若 则 ,这时可以设 ,用 替代 .) 因此, , 此时, . ② 由 ,得 , ③ 由②, ③有 此式与①式矛盾. 所以, 至少有一个是 的倍数. 下面证明本题的结论：因为对 个点有 个 点集,每一个点集都至少有一对点的距离是 的倍数,所以有 个点对的距离是 的倍数. 由于每对点均和 个点构成 点集,因而重复了 次. 所以至少存在 条线段的长度都是 的倍数,其和也是 的倍数. 【例3】是否可以将正整数 分别填入 的 个方格内，使得凡具备 形的四个方格（方向可以任意转置）内的数字之和都能被 （中国北方数学奥林匹克，2006年） 【解】假设能够满足题设要求. 将 的 个方格染成如图的黑白两色． 　由题设， 和 都能被 整除，则它们的差 也能被 整除，于是 与 被 除有相同的余数，设为 ． 　由于 和 都能被 整除，则它们的差 也能被 整除，于是 与 被 除有相同的余数为 ， 与 被 除也有相同的余数为 ． 　同理， 和 都能被 整除则它们的差 也能被 整除，于是 与 被 除有相同的余数为 ， 　由于 和 都能被 整除，则它们的差 也能被 整除，因为 与 被 除也有相同的余数为 ，则 与 被 除有相同的余数为 ． 由以上可类推，图中白格内的数被 除有相同的余数为 ，黑格内的数被 除有相同的余数为 ． 　这样， 个方格内的数被 除有相同的余数只能有 和 两种，然而， 被 除的余数有 共五种，出现矛盾． 　因此题设的要求不能实现． 【例4】将 这 个正整数任意地写在一个 的方格表中，每个方格写一个数。每一次操作可以交换任何两个数的位置。证明：只需经过 次操作，就能使得写在任何两个有公共边的方格中的两个数的和都是合数． （第33届俄罗斯数学奥林匹克，2007年） 【解】用一条竖直的直线 将方格表分成两半．由于共有 个偶数，所以在其中一半中有不多于 个偶数，不妨设右半部表中有不多于 个偶数，则在左半部表中有同样数目的奇数． 第一步操作是逐一将右半部表中的偶数与左半部表中的奇数交换位置，经过不多于 次操作，就可以使右半部表中全是奇数，左半部表中全是偶数．此时，位于同一半表中的任何两个有公共边的方格中的两个数的和都是偶数，因而是合数． 问题还剩下在分界线 两侧相邻两数的和，这样的数有 对，如果这 对数每一对的和是合数，问题已经解决，如果有质数，则最多有 对的和是质数． 第二步操作是对在分界线 两侧相邻数的操作．我们的操作只需在右半部表中进行． 右半部表中的数 全是奇数，即 共 个奇数，分别有不少于 个对 余 ，这时观察直线 左半部的 个数 ， 若 ，则在右半部用一个 交换到与 相邻的位置，这时这两个数的和是 的倍数，因而是合数．这样的交换最多有 次． 　　于是，最多经过 次操作，就能使得写在任何两个有公共边的方格中的两个数的和都是合数．