第四节 变换和操作.doc

第五章 组合数学第四节 变换和操作E4001 给定四个数a、b、c、d，按下列法则进行变换：前一个乘后一个，第四个乘第一个，得到一组新数ab、bc、cd、da从这组新数出发，再按上述法则又得到一组新数，如此下去证明：除a=b=c=d=1或0的特殊情况外，不会再出现原来的四个数【题说】1961年全俄数学奥林匹克八年级题5【证】设在变换n次后又出现原来4个数a、b、c、d因为一次变换后4数之积为（abcd）2，第n次变换后4数之积为（abcd）2n，所以abcd=1或0若a、b、c、d中有一个为0，则易知两次变换后，所得数均为0设abcd=1，则三次变换后所得的数A=a2b2，B=b2c2，C=c2d2，D=d2a2都是正数，且满足AC=BD=1不妨设A最大，经2n次变换后，最大数为A2n由于经若干次变换后，A、B、C、D又重新出现，所以必有A=1，从而B=C=D=1由此易知a=b=c=d=1E4002 在mn的方格表中的每一个方格里任填上一个实数，允许同时改变表里某一行或某一列所有数的符号证明：经过若干次这样的变换后，总能使表中任一行的和与任一列的和非负【题说】 1961年全俄数学奥林匹克九年级题2、十年级题3【证】设表格中所有数之和为无论怎样改变行、列符号，最多可取2m+n1个不同的值设与其最大值所对应的表为T，则T的每行、每列的和一定非负如若不然，T的某行（列）的和为负，则将此行（列）变号后，的值应变大，矛盾E4003 给定一个由2k个由+1或1组成的数组，将每个与其后一个相乘，最后一个与第一个相乘，得到一组新数，依次类推证明：最后一定能得到全由+1组成的数组【题说】 1961年全俄数学奥林匹克十年级题5【证】k=1时，命题显然成立假设命题对k成立设2k+1个数x1，x2，x2k+1，都是+1或1因为xi2=1，于是第二次、第三次变换后所得的数为x1x2，x2x3，x3x4，x2k+1x1与x1x2，x2x4，x3x5，x2k+1x2可见，每两次变换后，奇数项恰是x1，x3，x2k+11一次变换的结果，偶数项恰是x2，x4，x2k+1变换的结果如此变换下去，依归纳假定，奇数项与偶数项最后都变成+1故长度为2k+1的数列也是如此E4004 一群小孩围坐一圈分糖果，老师让他们每人先取偶数块，然后按下列规则调整：所有的小孩同时把自己的糖分一半给右边的小孩糖的块数变成奇数的人，向老师补要一块证明：经过有限次调整之后，大家的糖就变得一样多了【题说】1962年北京市赛高三二试题4【证】设在某次调整前糖最多的人有2m块，最少的有2n块，mn，那末可以看出：（1）调整后每人的糖的块数仍然在2n与2m之间因为若某孩子原有2k块，在他左边的有2h块，nkm，nhm那么调整后这孩子所得的块数k+h满足2nk+h2m只有当k+h是奇数时（这时k+h2m），可补要一块，仍不超过2m块（2）原来拿糖超过2n块的，调整后仍超过2n块，因为由kn，hn，得k+h2n（3）至少有一个原来糖为2n块的孩子调整后糖至少增加一块因为至少有一个拿2n块的孩子左邻拿着2k2n块，调整后这个孩子至少要拿n+k2n块由于每调整一次，拿2n块的孩子至少少了一个，所以若干次后，每个孩子的糖的块数都大于2n，又由于每人的糖的块数始终2m，所以若干次调整后，糖块最多与最少的差至少减少1因此，有限次调整后，各人的糖的块数就会变成相同了E4005 剧院的坐位排成p排和q列整个剧院可容纳pq个观众（p1，q1）在每一个坐位上坐着一个小学生，他们都不一样高老师在每一排中挑选个子最矮的学生在这些最矮的学生中，个子最高的等于a然后，老师在每一列中挑选最高的学生，他们之中最矮的等于b试说明：三个关系式ab， a=b，ab之中的哪一个可以表示a与b的关系并弄清：当剧院里的小学生调换坐位时，这个关系是否会改变？【题说】1963年匈牙利数学奥林匹克题1【解】个子为a的学生，他所在行的任一个学生个子a因而每一列最高的学生个子a于是恒有ba如果个子为a的学生，他所在列l的其他学生个子a，那么b=a否则ba因此只要注意保持列l上的学生，个子全a（或不全a），则关系b=a（ba）不会发生变化E4006 1在44的方格表里填上一些“+”号或“”号，如图所示，可以同时改变一行，一列或平行于某一条对角线的直线上的所有方格里的符号（特别地，也包括任何一个角上的方格）证明：无论进行多少次这样的变换，我们都不能得到全部都是“+”号的表2在88大小的象棋盘上的所有方格里，除了一个不在角上的方格以外（在这个方格里放置“”号），都放置“+”号可以同时改变水平或铅直方向或对角线（特别地，可以是任何一个角上的方格，对角线是指“象”所走的路线）上的方格里的符号证明：无论进行多少次这样的变换，我们都不能得到完全是“+”号的棋盘【题说】第二届（1968年）全苏数学奥林匹克八年级题6、九年级题8、十年级题6【证】1由图b容易看出，每一条平行于正方形的边或对角线的直线，穿过图中画有斜线的方格偶数次而这些方格中有奇数个“”号，并且在进行指定运算时不变2在88的棋盘上可以画一个44的方形，其中“”号的放置如图a从而归结为1E4007 在圆周上写有一些数，如果某四个相邻的数a、b、c、d满足：（ad）（bc）0，那么，b和c可以交换位置证明：这样的交换只可以进行有限次【题说】第五届（1971年）全苏数学奥林匹克十年级题5【证】由于ab+cdac+bd，所以，每交换一次，相邻的数的乘积的和S严格增大，而和S只可以取有限个不同的值，故这样的交换只可以进行有限次E4008 两个人玩下面的游戏一个人报一个数字，另外一个人则按自己的意愿用这个数字替换以下差式中的一个星号，这样进行8次，将星号换成8个数字报数的人要使差尽量大，而第二个人要使差尽量小证明：1无论第一个人怎样说，第二个人总能使所得的差不大于40002无论第二个人怎样替换，第一个人总能使差不小于4000【题说】第六届（1972年）全苏数学奥林匹克八年级题6本题可推广至n（1）位数，这时对双方都最有利的“值”等于410n1【证】 1第一个人说的数字为0至3（或6至9）时，第二个人将它放在被减数（或减数）的首位易知这样便可使差4000第一个人说的数字为4（或5）时，第二个人将它放在被减数（减数）的首位，然后只要有非0（非9）的数字，便放在减数（被减数）的首位，最后的差必40002第一个人先报4或5若第二个人将它放在被减数（或减数）首位，第一个人以后只报0（或9）若第二个人将4或5放在其他数位上，根据从左到右，第一个数字出现在被减数或减数上，第一个人报4或5这样继续下去（如果在同一数位上，被减数与减数均有数字，则根据其余的数位决定报4或5）、直至被减数（或减数）首位出现4或5，第一个以后只报0（或9）即可E4009 已知若干个红色的和若干个蓝色的点，将它们的某些点联成线段如果和某点相联的点中与它的颜色不同的点多于一半，则称它为“奇点”如果我们每一次将一个奇点改成另外的颜色证明：经过若干次操作以后，一个奇点也没有了【题说】第八届（1974年）全苏奥林匹克题十年级题3【证】事实上，每改变一次“奇点”的颜色，“奇点”数目就减少一个，而“奇点”总数是有限的所以经若干次操作后，一个奇点也没有了E4010 在木板上写有若干个0，1和2现在可以擦掉两个不同的数字，并用另一个数字来代替（代替0和1的是2，代替1和2的是0，代替0和2的是1）证明：如果由于这种做法，最后在木板上只留下一个数字，那么与它们操作的次序无关【题说】第九届（1975年）全苏数学奥林匹克八年级题6，十年级题5【证】 假设0的个数是p，1的个数是q，2的个数是r在每次操作后，p、q和r分别增加或减少1，即p、q、r改变一次奇偶性当木板上只留下一个数字时，p、q、r三个数中，一个为1，另两个为0由此可见，p、q、r三数中，必有一个的奇偶性与另外两个奇偶性不同；与它对应的数字最后留在木板上E4011 圆周上有若干黑色和白色的棋子，两人按下面的规则作游戏：甲取走所有与白子相邻（只需有一侧相邻）的黑子，然后，乙取走所有与黑子相邻的白子这样进行下去，直至剩下的棋子全部同色1如果开始有40枚棋子，是否有可能在每人取两次之后，只剩下一枚棋子？2如果开始有1000枚棋子，问最少经过多少步才能只剩下一枚棋子？【题说】第十一届（1977年）全苏数学奥林匹克八年级题4【解】 1能如图，棋子0表示最后留下的一枚黑子，在它两旁各放1枚白子并标以1，表示在倒数第1步（即第4步）被取去的白子在每个1的两旁各放1枚黑子并标以2，表示在倒数第2步（即第3步）被取去的黑子在每个2与0的两旁各放1枚白子并标以3，表示在倒数第3步（即第2步）被取去的白子最后放上标有4的黑子这样，共41枚棋子第一次取去标有4的黑子，第二、三、四次依次取去标有3、2、1的棋子，最后剩下一枚黑子0在图中删去一个标有4的棋子，对剩下的40枚棋子，结论依然成立2用上面的方法可得下表：这里棋子总数St是能够经过n步后剩下1枚棋子的情况中棋子数的最大值由于S7=5571000，S8=13931000所以至少8步才能使原有的1000枚棋子只剩下1枚棋子用上面的作法不难得出有1393枚棋子而经过8步最后只剩1枚黑子的图，将其中标有8的棋子（共4082=816枚）删去393枚，便得到1000枚棋子，经过8步最后只剩下1枚黑子E4012 有两个同心圆盘，各分成n个相等的小格外盘固定，内盘可以转动（如图所示）内外两盘小格上分别填有实数： a1，a2，an；b1，b2，bn，且满足条件：a1+a2+a3+an0，b1+b2+b3+bn0证明：可将内盘转动到一个适当位置，使两个盘的小格对齐，这时，两个盘n个对应小格内数字乘积的和为一正数【题说】 1978年安徽省赛二试题4【证】如图所示，对应小格上两数乘积的和为a1b1+a2b2+anbn记为A1将内盘按顺时针方向转动一格，对应小格上两数乘积的和为a1b2+a2b3+anb1记为A2转动i格，对应小格上两数乘积之和为a1bi+1+a2bi+2+anbi 记为 Ai+1（i=1，2，n1）A1+A2+An=（a1+a2+an）（b1+b2+bn）0所以A1，A2，An中至少有一个正数，即结论成立E4013 设有N个人，排成一行，从第一名开始，1至3报数，凡报到3的就退出队伍，余下的向前靠拢再按此规律重复进行，直到第p次报数后，只剩下三个人为止试问：1这剩下的三个人，他们最初应分别在原队伍的什么位置？2当N=1000时，求这三个人的最初位置【题说】1979年浙江省赛二试题5【解】1显然，最后剩下的三个人中，前二人最初的位置分别是第一和第二设第三个人的最初位置是第ap+1个第一次报数后，他排在第ap个，第p次报数后，他在第a1个，显然a1=3由于ap+1，ap，都没有被淘汰，因此，ap+1，ap等都不是3的倍数设 ap+1=3q+rp（rp=1或2）则 ap+1ap=q2当N=1000时，用递推公式算得a1=3，a2=4，a3=5，a4=7，a16=712，a17=10671000所以当N=1000时，共报数15次，最后剩下的三个人，最初位置分别是第1、2、712E4014 设A和E为正八边形的相对顶点，顶点A处有一只袋鼠，除顶点E外，袋鼠可以从八边形的任一顶点跳到两相邻顶点中任一顶点，落到顶点E时袋鼠就在此停止设en为袋鼠从顶点A恰好跳n次后落到顶点E的各种方法的个数证明：1e2n1=0；跳n次后从顶点A落到顶点E的方法称为顶点的一个序列（P0，P1，Pn），满足下列条件：（1）P0=A；（2）Pn=E；（3）对任一i，0in1，PiE；（4）对任一i，0in1，Pi和Pi+1为相邻的顶点【题说】第二十一届（1979年）国际数学奥林匹克题6本题由原联邦德国提供【证】如图，设正八边形为ABCDEFGH，从A出发经过n步到达B的个数记为bn；从A出发经过n步到达C、D、A的路的个数分别记为cn、dn、an由于对称性，由A出发经过n步到达H、G、F的路的个数也分别是bn、cn、dn因此有 en=2dn1 （1）同理有 cn=bn1+dn1 （2）bn=cn1+an1 （3）an=2bn1 （4）由于袋鼠跳到E点后就停止不动了，所以dn=cn1 （5）由以上（1）（5）得en=2dn1=2cn2=2（bn3+dn3）=2（cn4+an4+dn3）=2（dn3+2bn5+dn3）=2dn3+2（cn4dn5）+dn3=2dn3+2（dn3dn5）+dn3=8dn34dn5于是en=4en22en4 （6）由e1=e3=0及递推关系（6）立即得出1又由（6），e2n=4e2n2en4e2n是线性递推数列，由它的特征方程k2=4k2e2n=c1xn1+c2yn1由于e2=0，e4=2所以c1+c2=0因此2成立E4015 一张台球桌形状是正六边形ABCDEF一个球从AB的中点P击出，击中BC边上的某点Q，并且依次碰击CD、DE、EF、FA各边，最后击中AB边上的某一点设BPQ=，求的取值范围【题说】1981年全国联赛题5本题可用图形的对称变换、正弦定理或线性函数迭代法来证明本题还可推广到正n边形的情形【解】 如图，设AB=2BQP=CQR=DSR=EST=FUF=AUV=60，CRQ=DRS=STE=FTU=AVU=在BQP中，即 BQsin（60）=sin（1）同理（2BQ）sin（60）=RCsin （2）（2RC）sin=DSsin（60） （3）（2DS）sin（60）=TEsin （4）（2TE）sin=FUsin（60） （5）（2FU）sin（60）=AVsin （6）（6）（5）+（4）（3）+（2）+（1），得6sin（60）5sin=AVsin由0AV2，得E4016 黑板上写出三个整数，然后抹去其中一个，而用留下的两数之和减1所得的数来替代被抹去的数，这样的变换重复若干次后，结果得到的数是17、1967、1983试问在黑板上最初所写的数能否是：（a）2、2、2；（b）3、3、3？【题说】第十七届（1983年）全苏数学奥林匹克八年级题2【解】（a）2，2，22，2，3（表示变换），然后始终为两个偶数一个奇数，不论多少次变换都不能到3个奇数17，1967，1983（b）（3，3，3）（5，3，3）（5，7，3）（13，15，3）（17，15，3）（17，15，31）（17，1939，1951）（17，1967，1951）（17，1967，1983）E4017 正五边形的每个顶点对应一个整数使得这五个整数的和为正若其中三个相连顶点相应的整数依次为x、y、z，而中间的y0，则要进行如下的操作：整数x、y、z分别换为x+y、y、z+y只要所得的五个整数中至少还有一个为负时，这种操作就继续进行问：是否这样的操作进行有限次后必定终止？【题说】第二十七届（1986年）国际数学奥林匹克题3本题由原民主德国提供【解】为方便计，把五个数写成一列：v、w、x、y、z，并注意v与z是相邻的不妨设y0操作后，便得v、w、x+y、y、y+z它们的和未变考虑操作前后各项平方及每相邻两项和的平方之和（称为双平方和）的差v2+w2+（x+y）2+（y）2+（y+z）2+（v+w）2+（w+x+y）2+x2+z2+（y+z+v）2v2+w2+x2+y2+z2+（v+w）2+（w+x）2+（x+y）2+（y+z）2+（z+v）2=2y（v+w+x+y+z）因为y0，v+w+x+y+z0，故上述差为负数这就是说，每操作一次后，各数双平方和变小但原来5个数的双平方和为一定值，因此这种操作进行有限次后即行停止，即5个数最后都变为正数E4018 如图a，ABC的顶点B在单位圆的圆心上，A、C针方向依次作旋转，具体方法如下：第一次，以A为中心，使B落到圆周上；第二次，以B为中心，使C落到圆周上；第三次，以C为中心，使A落到圆周上如此旋转直到第100次求A点所走路程的总长度【题说】1987年全国联赛一试题1（4）原题为选择题【解】在这100次运动中，A点在第1、4、7、11、100次运动中都未动，而第2、5、8、98次运动中A点走过的路程相等；第3、6、9、99次运动中A点走过的路程相等在图中，A2表示A点第2次运动后的位置，其余下标类似因为由于B3必在C2A3的中垂线上，且C2B3=1，所以B3即是B点，这综上所述，得A点在100次运动中走过的路程为E4019 有1987片玻璃片，每片上涂有红、黄、蓝三色之一，进行下列操作：将不同颜色的两块玻璃片擦净，然后涂上第三种颜色（例如将一块蓝玻璃片和一块红玻璃片上的红色与蓝色擦掉，然后在两片上涂上黄色）证明：1无论开始时红、黄、蓝色玻璃片各有多少片，总可以经过有限次操作而使所有的玻璃片涂有同一种颜色；2最后变成哪一种颜色，与操作顺序无关【题说】第二届（1987年）东北三省数学邀请赛题4【证】设红片、黄片和蓝片的数目分别为x、y、zx、y、z被3除后的余数中必有两个是相等的否则x+y+z0+1+20（mod3）与 x+y+z19871（mod3）矛盾不妨设x=3a+m，y=3b+n，z=3c+n，其中m、n0，1，2），cb若c=b，则可将黄片、蓝片一对一地全变成红片若cb先将3b+n片黄片与3b+n片蓝片一对一对地换成红片，这时黄片数为0，蓝片数为3（cb）接着，将1片红片，1片蓝片变成2片黄片，再将2片黄片、2片蓝片变成2片红片经过这一过程，黄片数仍为0，蓝片数减为3（cb1）如果cb1=0，结论已经成立否则，类似地再操作若干次，直至蓝片数减少至0最后所有玻璃片都涂上了红色由于经过一次操作，黄片、蓝片数均减少1，或一种减少1，另一种增加2所以两种片数除以3所得余数仍然相同如果最后只剩下一3的余数才能相等，即所有玻璃片均为红色E4020 在黑板上有1，2，1987这些数作这样的变换：将黑板上的数擦去一些，并添加上被擦去的数的和被7除所得的余数经过若干次变换后，黑板上的数只有二个，一个是987，求另一个数【题说】第十三届（1987年）全俄数学奥林匹克九年级题5（理论部分）【解】黑板上所有数的和被7除所得余数永远不变数1+2+187=19871427被7整除所以最后黑板上的两个数的和也被7整除因为987=1417，所以另一个数应该是某些数被7除所得的余数0E4021 在黑板上写下从1到1988的所有自然数对这些数依次反复施行运算A和B：先是A后是B，接着再是A，然后再是B，如此继续下去运算A是从每个写在黑板上的数减去同一个自然数（对不同次的运算A，减数可以不相同）运算B是抹去黑板上写着的两个数，然后写下它们的和数运算A和B如此顺次施行，直至某次运算B后，黑板上只留下一个数，并且它是非负的，问这个数是多少？【题说】第十四届（1988年）全俄数学奥林匹克十年级题3【解】施行运算A和B各一次后，黑板上的数就少了一个所以运算A和B各施行1987次后，黑板上就留下一个数设施行第k次运算A时，减数为自然数dk，k=1，2，1987经第k次的运算A后，写在黑板上的数的和少了（1989k）dk；而经运算B后，这个和数是不变的所以运算A和B各施行1987次后，黑板上写的数是x=（1+2+1988）1988d11987d22d1987=1988（1d1）+1987（1d2）+（1989k）（1dk）+2（1d1987）+1显然（1989k）（1dk）0，并且若对某个k，有dk2，则（1989k）（dk1）2故 x（1989k）（1dk）+11与题设矛盾因此，对一切k=1，2，1987，dk=1所以x=1，即黑板上最后留下的数是1E4022 在大小为nn的正方形表格中写上实数，并且任意一行与任意一列中各数之和等于0对这个表格施行如下运算：任何一行加到一列上去，并从另一列中减去；列的第i个元素加上或减去行的第i个元素试证：进行若干次这样的运算，可以得到全由0组成的表格【题说】第二十二届（1988年）全苏数学奥林匹克九年级题8【证】以Cij，k表示将第i行加到第j列上去，并从第k列减去第i行依次施行下列运算：C1n,1，C2n,2，Cn-1n,n-1得出一个表格，对角线上的所有元素（位于第n行、第n列的元素除外）都等于0考虑运算序列Cij,i，Cii,j，Cji,j，Cin,i，Cij,n不难验证，应用这些运算得到的新表格，位于第i行、第j列的数等于0，而不在最后一行或最后一列的数都不变对i=1，2，n1和i=1，2，n1，依次应用上述运算序列，得到一个表格，其中不为0的数只能位于最后一行或最后一列因为任意一行和任意一列上各数之和都等于0（应用上述运算时，这个性质保持不变），所以最后一行和最后一列上的数也是0E4023 桌面上放有1989枚硬币，其中有的正面朝上，其余的正面朝下今有1989人按下述方法依次翻转硬币，第一人翻转其中的一枚，第二人翻转其中的二枚，第k人翻转其中的k枚，最后第1989人将所有硬币全部翻转证明：1不论硬币最初正反面的分布情况如何，他们总可采取适当步骤，使得1989人都进行过翻币手续后，恰将所有硬币朝同一方向2硬币最后的统一朝向与具体翻币方案无关（只依赖于初始分布）【题说】1989年南昌市赛二试题3【证】11989可换成任一奇数n对n用数学归纳法当n=1时，结论显然成立假设在n=2k1时结论成立，当n=2k+1时，分两种情况讨论（1）如果这2k+1枚硬币不全同向，其中必有一枚正面朝上的（记为正）和一枚正面朝下的（记为负），将它们标上记号让前2k1人对其余2k1枚硬币进行翻币手续，依假设可翻成同向，设为正第2k人翻动2k个正向币，使得所有2k+1枚硬币都成负向最后第2k+1人将所有硬币翻成正向（2）如果这2k+1枚硬币方向都相同将这2k+1枚硬币排成一圈，让第一人翻转其中一枚，第二人按顺时针方向翻转后续的二枚，第三人接着翻转后续的三枚，如此下去，当2k+1人全部翻转之后，由于1+2+（2k+1）=（k+1）（2k+1），所以，每枚硬币都翻动了k+1次，因而也同向2假设结论不真，则存在1989枚硬币的某种初始状态T及两种翻法A、B由状态T开始，按方法A可翻成全正，而按方法B可翻成全反由全正状态出发，按方法A的逆步骤翻回T状态，再按B方法翻成全反这样每枚硬币都改变了方向，从而每枚硬币翻动了奇数次，硬币总数1989为奇数故由全正状态到全反状态总共翻转了奇数次另一方面，在由全正状态到全反状态的过程中，每个人均翻转了偶数枚，因此总共翻转了偶数次，矛盾从而结论成立 E4024 在黑板上相继写下四个数：7956、3923、5857、9725再接着写出这四个数的和除以10000所得的余数，然后擦去第一个数，对留下的四个数，再按前面的方法处理，如此继续下去，试问黑板上出现的四个数能否是1989、1989、1989、1989？【题说】第十五届（1989年）全俄数学奥林匹克九年级题4【解】由（1989、1989、1989、1989）出发，按所述方法处理，第5组为（7956、3923、5857、9725）由于不同的四元数组的组数1016，在（1016+1）组中，必有两组相同易知，每一组也唯一地确定其前一组，从而必有一组等于第1组，因此，黑板上可出现（1989、1989、1989、1989），而且可出现无限多次E4025 7个六边形的网眼（如图）涂上两种颜色：白色或蓝色每次允许选择任一网眼，将它及所有相邻的网眼改涂为另一种颜色证明：由图a经有限次地上述改涂手续后，1可变为b；2不可能变为c【题说】第十五届（1989年）全俄数学奥林匹克九年级题5【证】1先选图a正下方网眼，改涂后可得图d再选图d正上方网眼，改涂后便得到图b2分别用A、B、C、D、E、F、G记7个网眼涂白色的网眼用+1表示，涂蓝色的网眼用1表示考虑A、C、D、F四格，不论选7个网眼中哪一格进行改涂，它们中必有两格或四格变号（改涂颜色相当于乘以1），因而这4个数之积总是不变对于图a这个积为+1；而对于图c，这个积为1因此，图a不可能变为图cE4026 数1，2，n 以任意方式写在圆周上，每次允许调换相邻两数的位置，如果它们差的绝对值大于1的话证明：经有限次的调换后，所有的数可按自然数列的顺序排列【题说】第十五届（1989年）全俄数学奥林匹克十年级题2【证】首先将数1与其相邻的数调换位置，沿同一方向直至与2相邻；然后1、2两数沿前述方向向3靠拢（先调换2，然后调换1）；继而1、2、3三数向4靠拢，等等这样便能将写出的数（沿顺时针或反时针方向）调整成按自然数列的顺序排列E4027 ABCDA1B1C1D1是单位立方体黑白二蚁同时从A点出发，沿着棱爬行，一条棱称为一段白蚁爬行的路线是AA1A1D1，黑蚁爬行的路线是ABBB1，它们都遵循如下规则：爬行的第i段与第i+2段所在直线是异面直线（其中iN）如果白、黑二蚁走完第1990段后各自停止在某顶点处，问此时二蚁相距多远？【题说】第一届（1990）希望杯高一二试题1（5），原为选择题【解】按行动规则，白蚁爬行路线必然是：AA1A1D1D1C1C1CCBBA循环进行下去黑蚁爬行路线必然是：ABBB1B1C1C1D1D1DDA也循环进行下去因此黑、白二蚁每爬行6段，又回到原出发地A点，循环进行由于1990=3316+4，故它们爬行1990步后，白蚁停在C点上，E4028 设有两个完全相同的齿轮A、B，B被平放在一个水平面上，A放在B上面并使两者完全重合（从而两者在水平面上的投影完全重合），然后任意去掉四对重合的齿如果两齿轮各有14个齿，试问：能否将齿轮A绕两齿轮的公共轴旋转一个适当的位置，使得两齿轮在水平面上的投影合为一个完整齿轮的投影？如果两齿轮各原有13个齿，又是怎样呢？请证明你的论断【题说】第五届（1990年）全国冬令营选拔赛题5【解】将每个断齿赋值“0”，好齿赋值“1”对A齿轮的每个位置，作两轮对应位置齿值的乘积之和，初始位置除外的13个位置总和为109=90137，故必有一个位置的和6此时必定任二断齿不相重合当齿数为13时，将A、B重合时各对齿依顺时针记为0，1，12锯掉0，1，5，11四对齿0，1，5，11两两之差恰取遍1，2，12（mod 13）故对A的任一位置总有两个断齿重合，始终得不到完整的投影E4029 森林中有12名矮子，每一名住在自己的房子里，房子染蓝色或红色在每一年的第i个月，第i名矮子拜访他的所有朋友，如果朋友中多数的房子与他自己的房子颜色不同，那么他就将自己房子的颜色改为另一种，以与大多数朋友一致证明：经过一段时间，每一名矮子均无须变更房子的颜色（朋友是互相的，并且不会变化）【题说】 1990年匈牙利阿拉尼丹尼尔赛高年级较高水平题2【解】在每两名朋友间连一条线如果他们房子的颜色相同，则将这条线染为黄色，否则不染色考虑黄线的变化当某个矮子需要改变自己房子的颜色时，根据本题条件，黄线总数至少增加1个但是黄线的总数不会超过C2n条因此黄线不可能永远增加换句话说，经过一段时间后，每一名矮子均无须变更自己房子的颜色E4030 在黑板上写下n个数，每次允许擦掉任意两个数，例如a和b，换成（a+b）/4这样的运算重复n1次，结果在黑板上只剩下一个数证明：若开始时在黑板上写的是n个1，则最后留在黑板上的数不小于1/n【题说】第二十五届（1991年）全苏数学奥林匹克九年级题2【解】易知所以经过一次运算后，黑板上各数的倒数和不大于运算前的倒数和最E4031 给定55格的正方形一个方格中填“”号，而其余的方格中填“+”号每次可以取出一个以方格线为边界的多于一个方格的正方形，将其中各格改变符号问开始时应将“”号置于哪个方格，才能使得经过若干次变号程序后，正方形中所有方格均成为“+”号？【题说】第二十五届（1991年）全苏数学奥林匹克九年级题8【解】如图所示，不难验证，任何一个取出的正方形都必包含偶数个带斜线的方格如果“”号标在带斜线的方格上，那么经过每次的变号程序后，在带斜线的格中仍有奇数个标有“”号的格（这是因为在所取的正方形中，若2m个带斜线的方格里有k个“”变号后，则有2mk个“”号，2mk与k的奇偶性相同），因此不能使所有变格都变为“+”号将正方形绕中心旋转90，即知只要起初“”号不是标在中心那个方格，不论变号程序如何，总不能使所有方格均变为“+”号如果“”号标在中心格，那么经过五次变号程序，即可使55格正方形均标“+”号这五次所取的正方形依次为：（1）左下角33的正方形；（2）右上角33的正方形；（3）左上角22的正方形；（4）右下角22的正方形；（5）整个55的正方形E4032 在平面上画一个99的方格表，每一小方格中任意填入+1或 1对任意一个小方格，将与它有一条公共边的所有小方格（不包含此格本身）中的数相乘，于是每取一格，就算出一个积在所有小格都取遍后，再将这些积放入相应的小方格中，这称为一次变动是否总可以经过有限次变动，使得所有小方格中的数都变为1？【题说】 1992年中国数学奥林匹克题3【解】答案是否定的如图a（未填数的空格中填1）经一次变换得图b，再经一次变换又恢复为图a，反反复复，永远不能使所有的数都变成1E4033 一个正n边形A被分成n个具有公共顶点（即A的中心）的全等的等腰三角形在这些等腰三角形中随意放入n+1只青蛙后，每秒钟都恰有某两只同在一个等腰三角形中的青蛙分别跳入两侧相邻的等蛙（x表示x的整数部分）【题说】1993年江苏省高中数学竞赛二试题2【证】由抽屉原理，总有两只或更多只青蛙在同一个（等腰）三角形中，所以这种蛙跳，将无限继续下去依顺时针方向依次将各三角形编号为1，2，n，且令青蛙的号码与它所在的三角形的号码相同设S是n+1只青蛙的号码的平方和，则总有S（n+1）n2如果某一个三角形（可设它编号为1）永远无青蛙跳入，则当青蛙作一次跳动后，S的某两项i2+i2变为（i+1）2+（i1）2，故S增加2由于这种跳动无限继续下去，与S有上界矛盾，故每个三角形都会有青蛙跳入由青蛙的跳法，任何一对相邻的三角形，若其中至少一个有青蛙，个三角形有青蛙；若n是奇数，取去一个有青蛙的三角形，余下的n1E4035 按某种顺序把从1到1993的自然数排成一行，对这一行数实行下述变换：如果数k占有第一个位置，则把这行中的前k个数按相反的顺序重新进行排列，证明：经过有限次这种变换以后，一定可以使数l占有第一个位置【题说】第十九届（1993年）全俄数学奥林匹克十一年级二试题6【解】将1993改为n并用归纳法来证明n=1显然设对n1，结论成立，考虑n个数的情形，如果经过有限次变换，数n排在最后则对前n1个数应用归纳假设便得到所需的结论（因为n已不会再移动）如果数n不可能移到最后，这时它也不可能占有第一个位置所以，位于最后的数在任何一次变换中不会移动从而参与变动的仅有前面的n1个数，应用归纳假设就可以达到我们的目的E4036 在一次竞选中，一个候选人到国家各地去游说我们假设整个国家在一个平面上，第一天他向东，第二天向北，第三天向西，么第40天结束时，他距离第一天出发点多少公里？【题说】第十一届（1993年）美国数学邀请赛题2【解】答：580公里以候选人出发点为原点建立直角坐标系，正实轴x指向东，正y轴指向北，第40天晚上候选人在点=（-4-12-76，-6-14-78）=（400，420）E4037 在一个圆上给了2000个点，从某点开始标上1，按顺时针方向隔一点标上2，再隔二点标上3（如图），继续下去，标出1，2，1993有些点会有不只一个数标记在其上，有的点没有标上任何数问：被标上1993的那个点被标上的数中最小的是多少？【题说】第十一届（1993年）美国数学邀请赛题9标n所以，两个正整数l、m标记同一个点当且仅当从而，如果标1993的点也标k，则必须是4000的倍数因为（1993k）+（1994+k）=3987不被2与5整除，所以1993k和1994+k奇偶不同，且不能同时被5整除若k1993，则1994+k32125=4000，所以1993k和1994+k中一个是125的倍数，另一个是32的倍数考虑以下两种情况：（1）125|1993k，321|1994+k因为1993=15125+118，所以125|k118，k118，在k=118时，125|1993k并且32|1994+k（2）125|1994+k，32|1993k，因为1994=15125+119，所以k=125r119，1993k=3262125r，从而32|r，k12532119118因此，所求的数是118E4038 ABC的顶点为A=（0，0），B=（0，420），C=（560，0）一个骰子的六个面分别标上两个“A”，两个“B”，两个“C”从ABC内部选出点P1=（k，m），重复掷骰子，依下列法则选出点 P2，P3，：如果骰子露出标记L的那面，LA，（14，92），问k+m=？【题说】第十一届（1993年）美国数学邀请赛题12【解】因为点P1在ABC内，所以所有的Pn都在ABC内设Pn坐标为（xn，yn），L坐标为（xL，yL），则由公式可从Pn+1及L的坐标标出Pn的坐标注意当Pn+1在如图区域中时，只有取L为 A，用公式标出的坐标才都是非负的，所以此时应取L为A同样，Pn+1在中时，取L为B；在中时，取L为C于是，应用上述公式依次推出各点坐标为P6（28，184），P5（56，368），P4（112，316），P3（224，212），P2（448，4），P1（336，8）所以k+m=336+8=344E4039 设n是一个大于1的整数有n个灯L0，L1，Ln1作环状排列，每个灯的状态要么“开”，要么“关”现在进行一系列的步骤S0，S1，Si，步骤Sj按下列规则影响Lj的状态（它不改变其它灯的状态）：如果Lj1是“开”的，则Sj改变Lj的状态，使它从“开”到“关”或者从“关”到“开”；如果Lj1是“关”的，则Sj不改变Lj的状态上面的叙述中灯的编号应按mod n同余的方式理解，即L1=Ln1，L0=Ln，L1=Ln+1，假设开始时全部灯都是“开”的，求证：（a）存在一个正整数M（n），使得经过M（n）个步骤后，全部灯都是“开”的；（b）若n为2k型的数，则经n21个步骤之后全部的灯都是“开”的；（c）若n为2k+1型的数，则经n2n+1个步骤之后全部的灯都是“开”的【题说】第三十四届（1993年）国际数学奥林匹克题6【证】（a）设步骤Sk后，n个灯的（总）状态为Tk+1，Tk只有2n种，k（mod n）只有n种所以，（k（mod n），Tk+1）只有n2”种，因此，存在自然数kh，使得kh（mod n），Tk+1与Th+1相同对Tk+1进行步骤Sk就得到Tk，对Th+1（即Tk+1）进行步骤 Sh（即 Sk）就得到Th，所以Tk与Th相同这样逆推上去，直至得到Thk与T0相同，其中T0是初始状态，即n个灯全开所以M（n）=hk满足要求（b）首先用数学归纳法证明：从只有Ln1“开”的状态开始，依倒序逐一进行步骤（2i1）际上，只要是（2i1）n步，从哪步开始没有关系，但必须依倒序进行）i=1时，显然经过Sn1，Sn2，S0后，只有Ln1，L0开假设当i=m（k1）时结论成立对于i=m+1，先进行前如果将“开”记为1，“关”记为0，则每个步骤Sj将Lj的值变为加（即每个灯的两个值相加（mod 2）Sn2，S0，后，由归纳假设，变为Ln1，L0，L1，因此，对Ln1和L2m1开，其余灯关的状态，再进行上述（2m这样共进行了（n2n）+（n1）=n21个步骤即（b）证毕（c）完全类似（b），由L1“开”其余“关”的状态开始，依倒（2k1）n=n（n2）次步骤，即进行完S2后，L1，L2，L2k“开”，其余“关”再进行S1与S0就变至全“开”状态T0（n1）个步骤即变至全“开”这样共进行了（n22n+2）+（n1）=n2n+1个步骤之后，从状态T0又变至状态T0。（c）证毕E4040 n（n4）个盘子里放有总数不少于4的糖块，从任选的两个盘中各取一块放入另一个盘子中，称为一次操作问能否经过有限次操作，把所有糖块集中到一个盘子里去？证明你的结论【题说】1994年中国数学奥林匹克（第九届数学冬令营）题2【解】回答是肯定的设有糖块的盘中的糖块数分别为a1a2ak（kn）若k3，可从最后两盘中各取1个放入第1盘，连续操作ak次，则上述各盘糖块数变为（a1+2ak，a2，ak2，ak1ak，0）继续采用这种作法，直至最后只有两盘有糖块，设糖块数为（a，b）（1）如果b=0，则目的已经达到（2）如果b=1，则作如下操作：（a，1，0，0）（a1，0，2，0）（a2，2，1，0）（a3，2，0，2）（a1，1，0，1）（a+1，0，0，0）（3）如果b2，则作如下操作：（a，b，0，0）（a1，b1，2，0）（a1，b2，1，2）（a1，b，0，1）（a+1，b-1，0，0）重复进行这样的操作，便可使第二盘中糖块数减少为1，化为（2）中情况，从而可将糖块集中到第一个盘子中去E4041 P在坐标平面的格点上移动，当P的坐标为（a，b）时，若a+b除以4所得的余数分别为0，1，2，3时，点P分别向右、上、左、下移动一个单位从某个格点P0出发，按上述规则移动10次，P走到（0，10）点求P0的一切可能位置【题说】1994年日本数学奥林匹克预选赛题4【解】对于P=（a，b）记a+b除以4的余数为m（P），点移动的情况如下表所示设从P0出发，经n次移动后移动到Pn处由上表知，当i1时，m（Pi）=1或2，且Pi+2=Pi+（1，1）所以P10=P8+（1，1）=P2+4（1，1）即P2=P104（1，1）=（4，6）P1=（4，5）由上表即知P0=（3，5）或（5，5）E4042 25个人围一圆桌坐，每小时表决一次，回答为是或否如果一个人第n次表决时，至少与一个相邻的人回答相同，即么他第n+1次表决与第n次相同如果第n次表决时，与两个相邻的人回答均不同，那么他第n+1次表决与第n次不同证明不论开始时大家怎样回答，从某一时间起，每个人的回答都不会改变【题说】第二十六届（1994年）加拿大数学奥林匹克题3【解】首先注意如果两个相邻的人第n次的回答相同，那么他们第n+1次的回答也相同因而在第n次回答后，都不会再改变令An为第n次回答时，至少与一个相邻的人回答相同的那些人的集合，则根据上面所说，由于25为奇数，所以第一次回答时不可能每个人与相邻的人回答均不相同，即A1至少含两个人人第m次的回答也不同这样y第m+1次的回答应与他自己第m次的回答不同，即与x第m+1次的回答相同，从而yAm+1=Am，矛盾！因此Am含全部25人并且从第m次起，每个人的回答都不会改变E4043 将99边形的边染色，使得相邻边的颜色依顺时针方向为红，蓝，红，蓝，红，蓝，黄然后进行一系列的变换，每一次变换将一条边的颜色改变，变为红，蓝，黄中的一种并且相邻的边颜色不同试问能否经过一系列的变换使得相邻边的颜色依次是红，蓝，红，蓝，红，黄，蓝？【题说】第二十三届（1994年）美国数学奥林匹克题2【解】对每一种染色法，给这个多边形的每个顶点打分：如果按照顺时针方向过这点的两条相邻的边染色为（红，蓝），（蓝，黄）