训练题A1、我们考虑如下变换T ：对于由三个正整数作成的有序组(,,)X x y z =,法则T 将其变成三个新的正整数有序组：1111()(,,)T X X x y z ==．其中，()()()111(2,,)1(,,)(2,,)22(2,,)x z z y x z x y z x y z y x y x y z y z x yx y x y z y +--<-⎧⎪=--+-≤≤⎨⎪--+⎩当当在其它情况下3请利用变换T 证明费尔马两平方和定理：若41p n =+是一个质数，则存在正整数,a b ， 使22a b p +=．（注：这个变换属于近代数学家察基尔()Zagier ，据此，他从另一观点证明了费尔马两平方和定理，其想法如同天外来客，无中生有．）证：容易验证，变换T 保持24x yz +的值不变，例如我们按情况()1做这个变换：则有2222221114(2)4()(44)(444)4x y z x z z y x z x xz z yz xz z x yz +=++--=+++--=+．在其余的两种情况下，检验起来也是如此简单的．这就是说，如果对于某个数p ，有等式24x yz p +=，那么在变换T 后，这种等式的值保持不变．我们再来检验，变换T 是对合的，即两次运用T 将使我们回到原来的数组． 例如我们仍按照前一种情况()1做这个变换，即当x y z <-时，有1112,,x x z y z z y x z =+==--，这时，由于11122x x z y z z x y =+>-=+-， 这就是说，对1X 的变换12222()(,,)T X X x y z ==，需要按照情况()3来进行：2112(2)2x x y x z z x =-=+-=，2111(2)()y x y z x z z y x z y =--=+-+--=， 21z y z ==．在其余的情况下，一切都是类似的．现在设，41p n =+是一个素数；首先，方程24(4)x yz p+=，至少有两个显然解：(,,)(1,1,)x y z n =与(1,,1)n ，前者满足x y =，后者满足x z =；马上想到的是，方程(4)是否还有满足y z =的解？如果有，那么方程(4)立即变成等式：22(2)x y p +=，结论已经获得；我们接下来的事情就是证明,满足这种条件的解确实存在．容易说明,方程(4)的正整数解(,,)x y z 只有有限多组；因为不大于p 的正整数,,x y z 都只有有限多个．据前面的察基尔变换可知，如果(,,)x y z 是方程(4)的一组正整数解， 那么111(,,)(,,)x y z T x y z =也是方程(4)的一组正整数解，反之亦然；假若在它的全部解中，没有使y z =成立的解，那么我们得出，变换T 可以将所有的解 配对成()(,,),(,,)x y z T x y z ，只要(,,)(,,)x y z T x y z ≠．现在我们需要考虑，是否存在这样的配对，或者如人们所说，变换T 是否具有不动点？ 观察变换T 中的三式，容易看出，T 的不动点（即满足111(,,)(,,)(,,)x y z T x y z x y z ==时的不动点），就是使x y =成立的不动点；但是方程(4)显然没有使1x y =>的解（否则将有2244(4)p x yz x xz x x z =+=+=+，与p 为素数矛盾！），因此，满足x y =的不动点只有一个，那就是(,,)(1,1,)x y z n =，故由以上情况得出，方程(4)的解的个数为奇数：其中，不动点为(1,1,)n ，而其余的解均可按对偶配对．为了导出与假设的矛盾，我们需要从另一途径来说明，方程(4)的解的个数又是偶数； 设方程(4)的全体解构成集合{}2(,,)4,S x y z x yz p y z =+=≠，任取000(,,)x y z S ∈，易知必有000(,,)x z y S ∈，而因00y z ≠，则000(,,)x y z 与000(,,)x z y 是一对不同的解，依据这一办法，可以将S 中的全体元素两两配对，因此，集S 有偶数个元素．矛盾！ 故所设不真，即方程(4)必有满足y z =的解(,,)a b b ，这时由方程(4)得到等式：22(2)a b p +=．定理证完．(注意：如果把以上做法看成是一个变换H ，使得111(,,)(,,)(,,)x y z H x y z x z y ==，则变换H 也是对合的；因为它也满足111(,,)(,,)H x y z x y z =，以及2211144x y z x yz +=+．而在y z ≠的假定下，解集中的元素对于H 不存在不动点,于是就可将解集的全体元素配对成()(,,),(,,)x y z H x y z ,因此,解的个数是偶数)．2、若简单图G 有21n +个顶点，至少31n +条边(2)n ≥，证明：G 中必有偶圈．证：由于图G 的边数不小于顶点数，则G 中必有圈，今逐次这样地去掉图中的一些边： 使得每去掉一条边，就破坏一个圈，这样的操作至少可以进行1n +次，也就是至少可以去掉1n +条边，破坏至少1n +个圈，即是说，图G 中的圈至少有1n +个．这1n +个圈中，必有两个圈有公共边，事实上如果任两个圈都无公共边，由于每个圈至少有3条边，则图G 至少有3(1)33n n +=+条边，矛盾！今设12,C C 是图G 中两个有公共边的圈，则1C 至少有一条边不在2C 中，2C 至少有一条边不在1C 中，若12,C C 含有公共边e 的最长公共道路为0()C AB =，若设道路0C 有r 条边，圈1C 有1r 条边（包括公共路），圈2C 有2r 条边（包括公共路），（即圈12,C C 的长分别是12,r r ）． 若去掉道路0()C AB =间的所有的边（即圈12,C C 的上述公共边），则圈12,C C 的剩下部分仍可合并为一个圈，记为*C ，圈*C 的长为122r r r +-；注意三个圈*12,,C C C 长的和等于122()r r r +-，它是一个偶数，故三个加项12,r r 和122r r r +-中必有一个是偶数，即G 中有偶圈．3、设G 为n 阶图()5n ≥，其边数4e n ≥+，证明G 中存在两个无公共边的圈.证：对n 归纳，当5n =时，9e ≥，这相当于从5k 中至多去掉一条边，结论显然成立. 设()6n k k <≥时结论成立，当n k =时，k 阶图G 的边数4e k ≥+，由于G 的边数≥顶点数，其中必有圈.若G 中存在一个长为3或4的圈1C ，则从图G 中删去圈1C 上所有的边，剩下的k 阶子图1G 中，依然满足：边数≥顶点数，其中又有圈2C ，显然，1C 与2C 都是G 中的圈，且无公共边.以下假设，G 中的每个圈长至少为5.若G 中有点0v ，其度数()01d v ≤，则删去点0v 以及它所关联的边，剩下的1k -阶子图2G 中，有1k -个顶点，至少()14k -+条边，据归纳假设，2G 中有不含公共边的两个圈，它们当然也是G 中的圈.若G 中有点0v ，其度数()02d v =，设与0v 邻接的两个点是12, v v ，显然12, v v 不相邻（因G 中无三角形），此时，删去点0v 及其所发出的两条边，同时添加边12v v ，所得的图3G 中，有1k -个顶点，至少()14k -+条边，据归纳假设，3G 中有不含公共边的两个圈1C 与2C . 再将边12v v 去掉，恢复被删去的点0v 及其所发出的两条边0102, v v v v ，回到图G ，则G中也有不含公共边的两个圈（这是由于，若3G 中的这两个圈1C 与2C 都不含边12v v ，则这两个圈1C 与2C 也是G 中的圈；若3G 中的这两个圈中有一个，例如2C ，含有边12v v ，从该圈中去掉12v v ，并代之以边0102, v v v v ，得到圈0C ，则0C 与1C 是G 中不含公共边的两个圈）.若G 中所有的点i v ，其度数()3i d v ≥，1,2,,i k =，如果G 的边数4k >+，我们就从G 中删去一些边，使得边数恰好为4k +，记此图为4G .在图4G 中，若4G 中有一顶点的度数3<，则据前面的讨论，结论已经得证； 若4G 中每个顶点的度数皆3≥，则4G 中各顶点的度数之和3k ≥，故4G 中的边数32k≥，即有342kk +≥，由此得，8k ≤. 而在此时，只要能证得，在4G 中必有三角形或四边形，这种三角形或四边形当然也在G 中，这将与原先的假设（G 中的每个圈长至少为5）相矛盾.事实上，由于4G 中的边数4k +≥顶点数k ，故4G 中必有圈，设C 为极小圈，则圈C 的点与点之间不能再有其它边相连，否则圈C 将被分成更小的圈，矛盾；设极小圈C 的长为r ，则2r k ≤-.(由于每个顶点的度数皆3≥，若r k =，则圈C 的点与点之间将有其它边相连，于是圈C 被分成更小的圈，矛盾；若1r k =-，圈121r C vv v v =上的每个点都要与圈外的一点0v 相邻，于是得到三角形012v v v ，矛盾)；于是，当5k =或6k =时，4G 中的极小圈C 的长4r ≤.当7k =时，有5r ≤，若极小圈C 为五边形12345v v v v v ，另两点为,u v ，五边形的五个顶点共向,u v 发出至少5条边，则,u v 中必有一点，例如u ，要向五边形的顶点发出至少3条边，其中必有两个相邻顶点，例如12v v 都与u 相邻，于是得到三角形12uv v （更小的圈），矛盾，因此4r ≤；当8k =时，有6r ≤，若极小圈为六边形123456v v v v v v ，六个顶点共向圈外的两点,u v 发出至少6条边，则其中有一点，例如u ，要向六边形的顶点发出至少3条边，于是点u 要向顶点组{}{}135246,,, ,,v v v v v v 中的一组发出至少2条边，设u 与13,v v 相邻，则得到四边形123v v v u ，矛盾；若极小圈C 为五边形12345v v v v v ，另三点为,,u v w ，五边形的五个顶点共向,,u v w 发出至少5条边，必有一点，例如u ，要向五边形的顶点发出至少2条边，由于五边形的任两个顶点，要么相邻，要么中间只隔一个顶点，因此得到一个含有点u 的三角形或者四边形，矛盾,因此4r ≤.综合以上讨论，可知本题结论成立.4、设正整数2m >，若正整数a 与m 互质，并且1a m <<，就称a 是m 的“本原互质数”，例如10的“本原互质数”为3,7,9，其中3,7为质数，而9不是质数；12的“本原互质数”为5,7,11，它们都是质数．一般地说，若m 为正整数，并且它的“本原互质数”所构成的集合是一个非空的质数集，就称数m 是单纯的，例如12就是一个单纯数．试求全体单纯数． 解：容易验证，3,4,6,8,12,18,24,30这八个数都是单纯数； 下面证明，除此而外，不再有其它的单纯数． 引理：用123,,,p p p 表示全体质数自小到大排成的数列：2,3,5,7,11,，则当4n ≥时，成立不等式：2112n n p p p p +<⋅⋅⋅．引理证明：当4n =时，显然有2251234112357210p p p p p =<=⋅⋅⋅=，下面考虑一般4n >的情况，设123,,,,k p p p p 是前k 个质数，作k p 个数123,,,,k p a a a a ，其中1121212131211211121311k k k k p k k a p p p a p p p a p p p a p p p p ----=⋅-=⋅-=⋅-=⋅- …… ① 这k p 个数123,,,,k p a a a a 中，每个数皆与1231,,,,k p p p p -中的所有数互质，且任两个数对模k p 不同余，因此恰有一个是k p 的倍数；继而可知，这k p 个数123,,,,k p a a a a 中，任两个数对模k r p +不同余，1r ≥，因此其中至多一个是k r p +的倍数，1,2,r =．对于给定的n k ≥，如果数1,,,k k n p p p +的个数少于集合{}12,,,k p A a a a =中元素的个数，即，若1k n k p -+< … ②，那么集A 中至少有一个数，设为j a ，它与1,,,k k np p p +都互质；又因j a 与1231,,,,k p p p p -中的所有数互质，于是，数j a 与前n 个质数123,,,,n p p p p 皆互质，此数j a 要么本身是质数，要么存在质数因子，总之有质数p ，使得j p a ，此p 当然异于123,,,,n p p p p ，但是前n 个质数已经被我们列出，所以1n p p +≥．即有112121n j k k p p a p p p p p p +≤≤≤-< … ③ ；再证明，当5n ≥时，对于前n 个质数123,,,,n p p p p ，存在k ，1k n <<，使得11212n k k k n p p p p p p p +++<< … ④5n =时，有61234513235711p p p p p p =<=⋅⋅<⋅= … ⑤， 6n =时，有71234561723571113p p p p p p p =<=⋅⋅<⋅⋅= … ⑥；假若对于n m =及1m +，有11212m i i i m p p p p p p p +++<<… ⑦，与21212+1m j j j m p p p p p p p +++<<… ⑧那么，由⑦，221112+11212m i i i i i m m m p p p p p p p p p p p ++++++⋅<⋅<⋅，约去1i p +，即有111212312m i i i i i m m m p p p p p p p p p p p +++++++⋅<⋅<⋅ … ⑨，利用⑤⑥中135i p p +>=，以及切比雪夫定理（若实数1a >，在区间(,2)a a 中必有质数）则23211122m m m i m p p p p p +++++<<≤ … ⑩，由⑨⑩得，3121232m i i i m p p p p p p p +++++<<，而由⑧，222112112123m j j j j j m m m p p p p p p p p p p p ++++++++⋅<⋅<⋅，仿照上面做法，得4121233m j j j m p p p p p p p +++++<<，故由归纳法得④式成立．由④，221121212()n k k k k n p p p p p p p p p p +++<<⋅，引理得证．回到本题，显然，3,4,6,8是单纯数，当单纯数4m >，则m 必为偶数，（否则，若m 为奇数，则合数4将与m 互质，得m 不是单纯数）；当单纯数9m >，则m 除了是偶数外，还应是3的倍数，（否则，若m 与3互质，则合数9将与m 互质，得m 不是单纯数），因此大于9的单纯数应是236⨯=的倍数； 当单纯数25m >，则m 除了是6的倍数外，还应是5的倍数，（否则，若m 与5互质，则合数25将与m 互质，得m 不是单纯数），因此大于25的单纯数应是23530⨯⨯=的倍数； 继而可知，大于27的单纯数应是2357210⨯⨯⨯=的倍数；大于211的单纯数应是2357112310⨯⨯⨯⨯=的倍数，…，大于2np 的单纯数应是12n p p p 的倍数．于是，在区间22(3,5)内，6的倍数只有12,18,24，它们都是单纯数，在区间22(5,7)内， 30的倍数只有30这个数，它是单纯数；在区间22(7,11)(49,121)=内，已经没有数是2357210⨯⨯⨯=的倍数，因此没有单纯数，当4n ≥时，由于221(,)n n p p +内的单纯数必须是12n p p p 的倍数，而据引理，当4n ≥时，成立不等式：2112n n p p p p +<⋅⋅⋅，也就是说，12n p p p 的倍数不在该区间内，因此对任何4n ≥，所有形如221(,)n n p p +的区间内没有单纯数；又显然，当2n ≥时，2n p 不是单纯数（因为合数21n p -与之互质），因此全部单纯数只有3,4,6,8,12,18,24,30这八个数．5、将0,1,2,3,4,5,6,7,8,9这十个原生数字分别填写于正五角星的十个交点处，使得五角星的每条线段上的四个数之和都是9的倍数，并且经过外环五点、内环五点所得到的两个圆周上的五数之和也都是9的倍数，称这样的填数图形为一个“五行轮”； 例如左图便是一个“五行轮”．我们将经过空中翻转或旋转移动后能够重合的“五行轮”认为是本质相同的，求本质不同的“五行轮”的个数．（注：五行，指金木水火土，它们循环相生相尅，是自古以来释、道、儒、玄易、中医诸学穷研之精粹，如右图（源自古籍）．而“五行轮”则是一种传说中的兵器，使用方法奥秘玄妙，对阵时按生尅关系，每招每式都需要用数学方法去推演的．本问题借用其基本模型．）解：若五条线上填写的数之和分别是9,1,2,3,4,5k S k =，则5919290k k i S i ====∑∑，所以5110k k S ==∑．0(1)、如果诸k S 全相等，则每线上的四数和皆为18；注意到，五角星的每两线皆有一交点，而每一交点恰有两线经过；先说明，此时9与0必共线，否则，假若9与0不共线，设9所在的一根线上的另三数为123,,x x x ，另一根线上的另三数为123,,y y y ，则12312312312336(9)(9)18()x x x y y y x x x y y y =+++++++=++++++18(123456)39≥++++++=，矛盾！9876543210外环相生，内环相尅现在设9与0所共的线为12(9,0,,)l a a =，则因129a a +=，所以有12(,)(1,8),(2,7),(3,6),(4,5)a a =；0所在的另一线为0123(0,,,)l b b b =，由于12318b b b ++=，则123(,,)(3,7,8),(4,6,8),(5,6,7)b b b =；9所在的另一线为9123(9,,,)l c c c =，由于1239c c c ++=，则123(,,)(1,2,6),(1,3,5),(2,3,4)c c c =；若(9,0,1,8)l =，则0(0,5,6,7)l =，9(9,2,3,4)l =，这时09l l =∅，矛盾！ 若(9,0,2,7)l =，则0(0,4,6,8)l =，9(9,1,3,5)l =，这时09l l =∅，矛盾！若(9,0,3,6)l =，则09,l l 皆与l 有两个公共点，矛盾！ 若(9,0,4,5)l =，则0(0,3,7,8)l =，9(9,1,2,6)l =，这时09l l =∅，矛盾！因此，使诸k S 全相等的填法不存在．于是这样的“五行轮”也不存在．(2)、今考虑诸k S 不全相等的情况，由于5110k k S ==∑，其中若有某个4k S ≥，即若有某根线上四数和936k S ≥，那么其余六点的填数和至多为9，矛盾！又若有两个数,i j S S 皆为3，则相应两线的填数和分别为27，这两线的公共点的填数至多是9，于是两线上七个不同的点填数和不小于2727945+-=，也得矛盾！因此，在诸k S 不全相等时，五角星的五条线填数情况是：恰有一条线的填数和为27，一条线的填数和为9，其余三条线的填数和皆为18．为了找出所有的“五行轮”，首先指出，如果019(,,,)A a a a =是一个“五行轮”，那么，将每个k a 一律用k b 替换，其中9,0,1,,9k k b a k =-=，得到的019(,,,)B b b b =也是一个“五行轮”，称这样的两个“五行轮”是“对偶”的；由于内、外圈的五数之和皆大于10(01234)=++++，且两圈的十数之和为45，故两圈的和数必定是，一个为18，而另一个为27．由于上述“五行轮”,A B 一一对应，我们也可以这样来限定A 类“五行轮”，使得它的外圈五数之和恰为18，（于是内圈五数和恰为27）．这样，全体“五行轮”的个数便等于A 类“五行轮”个数的2倍． QP注意到，四数和为9的线段，只有三种情况：123(0,1,2,6),(0,1,3,5),(0,2,3,4)ααα===；四数和为27的线段，也只有三种情况：123(3,7,8,9),(4,6,8,9),(5,6,7,9)βββ===；由于同一个五角星中的任两条线段i α和j β应当恰有一个交点，故其交点的填数， 只有3,4,5,6四种情况，按照“本质不同”的含义，我们可始终将这样两条线段i α和j β的交点置于点P 或Q 处． 今按交点填数情况讨论： （一）、交点在P 处的情况：0(1)、当交点填数为3时，按2α有6个排列：它们只能与1β搭配，共生成六个图，其中前三个是A 类的，第四个是B 类的，后两个则不具轮特征 （即：圈上五数和不是9的倍数）；0(2)、当交点填数为3时，按3α有6个排列：它们也只能与1β搭配，共生成六个图，其中前三个是A 类的，第四个是B 类的，后两个则不具轮特征；0(3)、当交点填数为4时，按3α有6个排列：它们只能与2β搭配，共生成六个图，其中前两个是A 类的，中间两个是B 类987654321987654321098765432198765432109876421539876521043987654321098765432198765432109876543219876420153987652104398765432198765432198765432109876543210987642153987652143的，后两个则不具有轮特征；(4)、当交点填数为5时，按2α有6个排列：它们只能与3β搭配，共生成六个图，其中前两个是A 类的，中间两个是B 类的，后两个则不具轮特征；(5)、当交点填数为6时，按1α有6个排列：若将它们与2β搭配，共生成六个图，其中第一个是A 类的，中间三个是B 类的，后两个则不具轮特征；(6)当交点填数为6时，按1α有6个排列：若将它们与3β搭配，共生成六个图，其中第一个是A 类的，中间三个是B 类的，后两个则不具轮特征；在此情形下，我们总共得到24个“五行轮“，其中12个A 类五行轮，12个B 类五行轮．9876543210987654321098765432198765432109876421539876521439876543210987654321987654321987654321098764215398765214398765432109876543210987654321098765432109876420153987652143（二）、交点在Q处的情况：（如果采用对偶方法，也可共得到24个“五行轮“，其中12个A类五行轮，12个B类五行轮，但为明确起见，且为了给出具体结果，我们仍旧实际操作一遍．）(1)、当交点填数为3时，按2α有6个排列：它们只能与1β搭配，共生成六个图，其中第一个是A类的，中间三个是B类的，后两个则不具轮特征；(2)、当交点填数为3时，按3α也有6个排列：它们也只能与1β搭配，共生成六个图，其中第一个是A 类的，中间三个是B类的，后两个则不具轮特征；(3)、当交点的填数为4时，按3α有6个排列：它们只能与2β搭配，共生成六个图，其中前两个是A类的，中间两个是B类的，后两个则不具轮特征；987654321987654321987654321987654321987642153987652143987654321987654321987654321987654321987642015398765214398765432198765432198765432198765432198764201539876521430(4)、当交点填数为5时，按2α有6个排列：它们只能与3β搭配，共生成六个图，其中前两个是A 类的，中间两个是B 类的，后两个则不具轮特征；0(5)、当交点填数为6时，按1α有6个排列：若将它们与2β搭配，共生成六个图，其中前三个是A 类的，第四个是B 类的，后两个则不具轮特征；(6)当交点填数为6时，按1α有6个排列：若将它们与3β搭配，共生成六个图，其中前三个是A 类的，第四个是B 类的，后两个则不具轮特征；在此情形下，我们也得到24个“五行轮”，其中12个A 类五行轮，12个B 类五行轮； 因此全部“五行轮”共有48个（其中24个A 类五行轮，24个B 类五行轮）．（又注，如果不考虑“轮”特征，只关注五角星填数，那么图形将有72般变化，也就是已经列出来的全部图形，这是一个有趣的结果；本题融九五太极，八九玄功于一体，所生成的十二组图形，梯次而出，有如布阵排兵，体现了数学结构的美与和谐，很值得细细玩味．）9876543219876543210987654321098765432109876421539876521043987654321098765432109876543219876543210987642015398765214398765432109876543210987654321098765432109876420153987652143。
