解题小品——架桥结网

《解题小品——架桥结网》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据12中等数学◆命题与群题■解题小品二一架桥结网陶平生(江西科技师范学院数学与计算机科学系，330013)例110名选手参加乒乓球赛，每两名选手对赛一局．如果选手i胜选手歹，毯手．『胜选手k，选手k胜选手i，则称为有上个“三角形”．设职和厶．分别表示第i名选事胜和败的局数j又如果选手1：胜选手_『时，总有厶+职≥8．求证：这次球赛恰有40个三角形．(1994，中国香港数学奥林匹克)本题原先的解答较为繁琐，而锲人适当媒介(文中盼啡)后，惆题便得以简化⋯，解：用点～秒l’。秽2，。一，秽lo表示这10名选手．如果钝胜似，，则在相应两点间连-．条有’向边{竹斗％．如此

2、得lo阶有向图f，则d+(研)_、IV,，d一(耽)=厶，且奢职+厶=9(i=1，2，⋯，10)．1不妨设Wt≥耽≥⋯≥W，o．则￡l≤L2≤⋯≤Llo．．由于图G共有45条边，每条边产生一个“出度”和一个“入度”，故10‘∑形=∑L；=45．}=1．i=l从而，W1≥5，W10≤4，LI≤4，Llo≥5．由题设，当让胜秽f时，有厶t％≥8．则形+岛≤10．下面证明：W。，职，⋯，形。。只在5和4两个数中取值．．，。(1)用反证法证明：WI=5．假若形。≥6，则Ll≤3j若vj是被移。击收稿日期：2008—05—05败的任一人，由L。+职≥8，得彤≥5．又由W，o≤4

3、，知掣。o不属于被秒，击败的人．从而，‰击败了口。．于是，被移。击败的选手(至少6人)属于集合{口j，移，，⋯，口，}．再由W。。≤4，L。o≥5，知击败秽。o的人(至少5个)必在集合{移：，l}。，⋯，t，，}中，其中必有一人坼，他既被钉，击败；又击败了口m．由“。'。击败””知彤≥5，故厶≤4．‘、又由“％击败∥盎?’知厶+W，ot>8，得Wlo≥4．再结合WIo≤4得W。o兰4．这样，职，耽，⋯，形。。的取值情况是W，≥6，{耽，职，⋯，％}中至少有六个数大于或等于5，其余的数大于或等于4．’”10因为肜。。=4，所以，∑v／,t>48，矛盾．故所设不真．从而，

4、形．≤5．前面已证Wl>15，因此，Wl_5．用同样的方法可得Lm=5，从而，阢。=4．注意到5=Wl≥W2≥⋯≥WIo=4．设其中有k个5，10一k个4．由45=5k+4(10一．j})得k=5．故Wi=鹦=⋯=职j5，Iv,=w7=⋯=Wlo=4．进而，Ll=厶=⋯=L5=4，L6=岛=⋯=Lm=5．(2)称题设中的三角形为“连环套三角形”．万方数据2009年第3期13注意到在图G中，连环套三角形个数+非连环套三角形个数=c％=120．先求非连环套三角形个数．-因为从一点发出的每一对出度(或者每一对人度’确定_个非连环套三角形，而对于图G中任一点P，它或者有5个出

5、度、4个人度(或者有5个人度、4个出度)，共组成《个“出度蹦’，氆个“人度对”(或者《个人度对，仨个出度对)，‘共得以P为一顶点的暖+口=16个非连环套三角形．如不计重复’，则10个点共产生160个非连环套三角形．由于每个非篷环套三角形含有一个出度对和一个人度对；故被计算了两次．因此，非连环套三角形共有掣：80个．从而，连环套三角形个数为120}一80=40个．’例2在_个正六边形的顶点上写着6个和为2003的非负整数．伯特做如下操作：他可以选出一个顶点，把它上面的数擦去，然后写上相邻两个顶点上数的差的绝对值．证明：伯特可以进行一系歹IJ操作，使得最后每个顶点的数都为

6、0．(第32届美国数学奥林匹克)1解：用，菇、Y分别表示奇数与偶数．显然，有运算：I石一YI=算，I菇一算l=Y，lY—YI=Y．将六个顶点划分成如图l所示的“正”鸟?‘缁’!两个三角形．由于六个顶点填数之和为奇数2003，故这两个三角形互顶点初始填数之和必定‘奇一偶(但经操作之后，这种情况可能发生改变)．(1)分析结构特征．。图l如果六个顶点处恰有一个顶点填)，，其余五个顶点填z，则称此状态是A型的(如图2(甲))．如果六角形恰有一组对顶点填Y，其余两组对顶点填石，则称此状态是曰型的(如图2(乙))．二窜¨率二图2显然，一旦操作进入曰型状态，则无论再经过多少次操作后

7、仍为B型．此时，不可能是全变为0情况．而A型填数状态，可以经过若干次操作后，重新变为A型状态，具体操作如图3：．三枣)：拿≯嚓≥(A3)茹率一窜：砖硌Y(A．)Y(A5)图3注意到，在前后两个A型填法A。一A。中，相应的Y转移到了相邻的顶点上，因此，经若干轮这种操作后得到的A型填法中的Y可移到任一顶点上．于是，经过六轮这种操作后，A型中的Y可沿逆时针方向遍历六角形的每个顶点，重新回到原来的顶点上．将此过程中的每个状态，称为一个“A型有向圈”，圈中的任两个状态可沿箭头方向彼此到达．(2)考虑数字特征．对于六边形顶点的一组填数口r，口：，⋯，万方数据14