第53届国际数学奥林匹克中国国家集训队试卷训练题A解答.doc

训练题A、我们考虑如下变换：对于由三个正整数作成的有序组,法则将其变成三个新的正整数有序组：其中，请利用变换证明费尔马两平方和定理：若是一个质数，则存在正整数，使（注：这个变换属于近代数学家察基尔，据此，他从另一观点证明了费尔马两平方和定理，其想法如同天外来客，无中生有）证：容易验证，变换保持的值不变，例如我们按情况做这个变换：则有在其余的两种情况下，检验起来也是如此简单的这就是说，如果对于某个数，有等式，那么在变换后，这种等式的值保持不变我们再来检验，变换是对合的，即两次运用将使我们回到原来的数组 例如我们仍按照前一种情况做这个变换，即当时，有，这时，由于，这就是说，对的变换，需要按照情况来进行：，在其余的情况下，一切都是类似的 现在设，是一个素数；首先，方程，至少有两个显然解：与，前者满足，后者满足；马上想到的是，方程是否还有满足的解？如果有，那么方程立即变成等式：，结论已经获得；我们接下来的事情就是证明,满足这种条件的解确实存在 容易说明,方程的正整数解只有有限多组；因为不大于的正整数都只有有限多个据前面的察基尔变换可知，如果是方程的一组正整数解，那么也是方程的一组正整数解，反之亦然； 假若在它的全部解中，没有使成立的解，那么我们得出，变换可以将所有的解配对成，只要 现在我们需要考虑，是否存在这样的配对，或者如人们所说，变换是否具有不动点？观察变换中的三式，容易看出，的不动点（即满足时的不动点），就是使成立的不动点；但是方程显然没有使的解（否则将有，与为素数矛盾！），因此，满足的不动点只有一个，那就是，故由以上情况得出，方程的解的个数为奇数：其中，不动点为，而其余的解均可按对偶配对为了导出与假设的矛盾，我们需要从另一途径来说明，方程的解的个数又是偶数；设方程的全体解构成集合，任取，易知必有，而因，则与是一对不同的解，依据这一办法，可以将中的全体元素两两配对，因此，集有偶数个元素矛盾！故所设不真，即方程必有满足的解，这时由方程得到等式：定理证完 (注意：如果把以上做法看成是一个变换，使得，则变换也是对合的；因为它也满足，以及而在的假定下，解集中的元素对于不存在不动点,于是就可将解集的全体元素配对成,因此,解的个数是偶数)、若简单图有个顶点，至少条边，证明：中必有偶圈证：由于图的边数不小于顶点数，则中必有圈，今逐次这样地去掉图中的一些边：使得每去掉一条边，就破坏一个圈，这样的操作至少可以进行次，也就是至少可以去掉条边，破坏至少个圈，即是说，图中的圈至少有个这个圈中，必有两个圈有公共边，事实上如果任两个圈都无公共边，由于每个圈至少有条边，则图至少有条边，矛盾！今设是图中两个有公共边的圈，则至少有一条边不在中，至少有一条边不在中，若含有公共边的最长公共道路为，若设道路有条边，圈有条边（包括公共路），圈有条边（包括公共路），（即圈的长分别是）若去掉道路间的所有的边（即圈的上述公共边），则圈的剩下部分仍可合并为一个圈，记为，圈的长为；注意三个圈长的和等于，它是一个偶数，故三个加项和中必有一个是偶数，即中有偶圈、设为阶图，其边数，证明中存在两个无公共边的圈.证：对归纳，当时，这相当于从中至多去掉一条边，结论显然成立. 设时结论成立，当时，阶图的边数，由于的边数顶点数，其中必有圈.若中存在一个长为或的圈，则从图中删去圈上所有的边，剩下的阶子图中，依然满足：边数顶点数，其中又有圈，显然，与都是中的圈，且无公共边.以下假设，中的每个圈长至少为.若中有点，其度数，则删去点以及它所关联的边，剩下的阶子图中，有个顶点，至少条边，据归纳假设，中有不含公共边的两个圈，它们当然也是中的圈.若中有点，其度数，设与邻接的两个点是，显然不相邻（因中无三角形），此时，删去点及其所发出的两条边，同时添加边，所得的图中，有个顶点，至少条边，据归纳假设，中有不含公共边的两个圈与. 再将边去掉，恢复被删去的点及其所发出的两条边，回到图，则中也有不含公共边的两个圈（这是由于，若中的这两个圈与都不含边，则这两个圈与也是中的圈；若中的这两个圈中有一个，例如，含有边，从该圈中去掉，并代之以边，得到圈，则与是中不含公共边的两个圈）.若中所有的点，其度数，如果的边数，我们就从中删去一些边，使得边数恰好为，记此图为.在图中，若中有一顶点的度数，则据前面的讨论，结论已经得证；若中每个顶点的度数皆，则中各顶点的度数之和，故中的边数，即有，由此得，. 而在此时，只要能证得，在中必有三角形或四边形，这种三角形或四边形当然也在中，这将与原先的假设（中的每个圈长至少为）相矛盾.事实上，由于中的边数顶点数，故中必有圈，设为极小圈，则圈的点与点之间不能再有其它边相连，否则圈将被分成更小的圈，矛盾；设极小圈的长为，则.(由于每个顶点的度数皆，若，则圈的点与点之间将有其它边相连，于是圈被分成更小的圈，矛盾；若，圈上的每个点都要与圈外的一点相邻，于是得到三角形，矛盾)；于是，当或时，中的极小圈的长.当时，有，若极小圈为五边形，另两点为，五边形的五个顶点共向发出至少条边，则中必有一点，例如，要向五边形的顶点发出至少条边，其中必有两个相邻顶点，例如都与相邻，于是得到三角形（更小的圈），矛盾，因此；当时，有，若极小圈为六边形，六个顶点共向圈外的两点发出至少条边，则其中有一点，例如，要向六边形的顶点发出至少条边，于是点要向顶点组中的一组发出至少条边，设与相邻，则得到四边形，矛盾；若极小圈为五边形，另三点为，五边形的五个顶点共向发出至少条边，必有一点，例如，要向五边形的顶点发出至少条边，由于五边形的任两个顶点，要么相邻，要么中间只隔一个顶点，因此得到一个含有点的三角形或者四边形，矛盾,因此.综合以上讨论，可知本题结论成立.、设正整数，若正整数与互质，并且，就称是的“本原互质数”，例如的“本原互质数”为，其中为质数，而不是质数；的“本原互质数”为，它们都是质数一般地说，若为正整数，并且它的“本原互质数”所构成的集合是一个非空的质数集，就称数是单纯的，例如就是一个单纯数试求全体单纯数解：容易验证，这八个数都是单纯数；下面证明，除此而外，不再有其它的单纯数引理：用表示全体质数自小到大排成的数列：，则当时，成立不等式：引理证明：当时，显然有，下面考虑一般的情况，设是前个质数，作个数，其中 这个数中，每个数皆与中的所有数互质，且任两个数对模不同余，因此恰有一个是的倍数；继而可知，这个数中，任两个数对模不同余，因此其中至多一个是的倍数，对于给定的，如果数的个数少于集合中元素的个数，即，若 ，那么集中至少有一个数，设为，它与都互质；又因与中的所有数互质，于是，数与前个质数皆互质，此数要么本身是质数，要么存在质数因子，总之有质数，使得，此当然异于，但是前个质数已经被我们列出，所以即有 ；再证明，当时，对于前个质数，存在，使得 时，有 ，时，有 ；假若对于及，有 ，与 那么，由，约去，即有 ，利用中，以及切比雪夫定理（若实数，在区间中必有质数）则 ，由得，而由，仿照上面做法，得，故由归纳法得式成立由，引理得证回到本题，显然，是单纯数，当单纯数，则必为偶数，（否则，若为奇数，则合数将与互质，得不是单纯数）；当单纯数，则除了是偶数外，还应是的倍数，（否则，若与互质，则合数将与互质，得不是单纯数），因此大于的单纯数应是的倍数；当单纯数，则除了是的倍数外，还应是的倍数，（否则，若与互质，则合数将与互质，得不是单纯数），因此大于的单纯数应是的倍数；继而可知，大于的单纯数应是的倍数；大于的单纯数应是的倍数，大于的单纯数应是的倍数于是，在区间内，的倍数只有，它们都是单纯数，在区间内，的倍数只有这个数，它是单纯数； 在区间内，已经没有数是的倍数，因此没有单纯数，当时，由于内的单纯数必须是的倍数，而据引理，当时，成立不等式：，也就是说，的倍数不在该区间内，因此对任何，所有形如的区间内没有单纯数；又显然，当时，不是单纯数（因为合数与之互质），因此全部单纯数只有这八个数、将这十个原生数字分别填写于正五角星的十个交点处，使得五角星的每条线段上的四个数之和都是的倍数，并且经过外环五点、内环五点所得到的两个圆周上的五数之和也都是的倍数，称这样的填数图形为一个“五行轮”；例如左图便是一个“五行轮”我们将经过空中翻转或旋转移动后能够重合的“五行轮”认为是本质相同的，求本质不同的“五行轮”的个数（注：五行，指金木水火土，它们循环相生相尅，是自古以来释、道、儒、玄易、中医诸学穷研之精粹，如右图（源自古籍）而“五行轮”则是一种传说中的兵器，使用方法奥秘玄妙，对阵时按生尅关系，每招每式都需要用数学方法去推演的本问题借用其基本模型）解：若五条线上填写的数之和分别是，则，所以、如果诸全相等，则每线上的四数和皆为；注意到，五角星的每两线皆有一交点，而每一交点恰有两线经过；先说明，此时与必共线，否则，假若与不共线，设所在的一根线上的另三数为，另一根线上的另三数为，则，矛盾！现在设与所共的线为，则因，所以有；所在的另一线为，由于，则；所在的另一线为，由于，则；若，则，这时，矛盾！若，则，这时，矛盾！若，则皆与有两个公共点，矛盾！若，则，这时，矛盾！因此，使诸全相等的填法不存在于是这样的“五行轮”也不存在、今考虑诸不全相等的情况，由于，其中若有某个，即若有某根线上四数和，那么其余六点的填数和至多为，矛盾！又若有两个数皆为，则相应两线的填数和分别为，这两线的公共点的填数至多是，于是两线上七个不同的点填数和不小于，也得矛盾！因此，在诸不全相等时，五角星的五条线填数情况是：恰有一条线的填数和为，一条线的填数和为，其余三条线的填数和皆为为了找出所有的“五行轮”，首先指出，如果是一个“五行轮”，那么，将每个一律用替换，其中，得到的也是一个“五行轮”，称这样的两个“五行轮”是“对偶”的；由于内、外圈的五数之和皆大于，且两圈的十数之和为，故两圈的和数必定是，一个为，而另一个为由于上述“五行轮”一一对应，我们也可以这样来限定类“五行轮”，使得它的外圈五数之和恰为，（于是内圈五数和恰为）这样，全体“五行轮”的个数便等于类“五行轮”个数的倍注意到，四数和为的线段，只有三种情况：；四数和为的线段，也只有三种情况：；由于同一个五角星中的任两条线段和应当恰有一个交点，故其交点的填数，只有四种情况，按照“本质不同”的含义，我们可始终将这样两条线段和的交点置于点或处今按交点填数情况讨论：（一）、交点在处的情况：、当交点填数为时，按有个排列：它们只能与搭配，共生成六个图，其中前三个是类的，第四个是类的，后两个则不具轮特征（即：圈上五数和不是的倍数）；、当交点填数为时，按有个排列：它们也只能与搭配，共生成六个图，其中前三个是类的，第四个是类的，后两个则不具轮特征；、当交点填数为时，按有个排列：它们只能与搭配，共生成六个图，其中前两个是类的，中间两个是类的，后两个则不具有轮特征；、当交点填数为时，按有个排列：它们只能与搭配，共生成六个图，其中前两个是类的，中间两个是类的，后两个则不具轮特征；、当交点填数为时，按有个排列：若将它们与搭配，共生成六个图，其中第一个是类的，中间三个是类的，后两个则不具轮特征；当交点填数为时，按有个排列：若将它们与搭配，共生成六个图，其中第一个是类的，中间三个是类的，后两个则不具轮特征；在此情形下，我们总共得到个“五行轮“，其中个类五行轮，个类五行轮（二）、交点在处的情况：（如果采用对偶方法，也可共得到个“五行轮“，其中个类五行轮，个类五行轮，但为明确起见，且为了给出具体结果，我们仍旧实际操作一遍）、当交点填数为时，按有个排列：它们只能与搭配，共生成六个图，其中第一个是类的，中间三个是类的，后两个则不具轮特征；、当交点填数为时，按 也有个排列：它们也只能与搭配，共生成六个图，其中第一个是类的，中间三个是类的，后两个则不具轮特征；、当交点的填数为时，按有个排列：它们只能与搭配，共生成六个图，其中前两个是类的，中间两个是类的，后两个则不具轮特征；、当交点填数为时，按有个排列：它们只能与搭配，共生成六个图，其中前两个是类的，中间两个是类的，后两个则不具轮特征；、当交点填数为时，按有个排列：若将它们与搭配，共生成