数学奥林匹克题解e组合数学--计数和离散最值061-070

《数学奥林匹克题解e组合数学--计数和离散最值061-070》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计数和离散最值061-070.E2-061网球协会为全体会员排定名次，最强的为第1号，其次为第2号等等．已知，在名次相差高于2的运动员比赛时，总是高名次的运动员获胜．在由1024名最强的选手参加的循环赛中（即参加者为1号选手到1024号选手），按奥林匹克规则进行：每一轮比赛的每对选手都由抽签决定，胜者进入下一轮．因此，每一轮比赛后参赛者将减少一半．这样一来，第十轮后将决出胜者．试问，胜者的最大号码是多少？【题说】第七届（1973年）全苏数学奥林匹克九年级题4．【解】胜者的最大号码是20号．因为不计比他强的选手时，k号选手

2、只可能输给k+1号和k+2号选手，所以，胜1号选手的号数至多为3，胜3号的号数至多为5，…．因此，冠军的号数不可能低于1+2×10=21．但在冠军号数为21时，第一轮比赛后应淘汰1号和2号选手，他们分别败于3号和4号选手；在第二轮中3号，4号被淘汰，5号、6号取胜，等等．依此类推，直到第九轮，在该轮比赛中19号和20号选手应分别战胜17号和18号选手，这样，21号选手将不会进入决赛．下面举一个第20号选手获胜的赛例，全体参赛者按每组512人分成两组，第一组中包括第19号，20号及其他510名较弱的选手，该组的比赛使得第2

3、0号选手获胜（显然，这是可能的）．在第二组中有1号至18号选手及其余较弱的选手，在该组比赛中使第18号选手获胜，这只要出现前面所说的情况，是可以作到的：第一轮中3号，4号分别战胜1号，2号；第二轮中5号，6号战胜3号，4号等等；到第八轮，第17号和18号选手战胜15号和16号选手，在第九轮中18号选手战胜17号选手．这样，参加决赛的将是第20号选手和第18号选手，于是，20号选手可能获胜． E2-062把一个8×8的棋盘（指国际象棋棋盘）剪成p个矩形，但不能剪坏任何一格，而且这种剪法还必须满足如下条件：（1）每一个矩形中

4、白格和黑格的数目相等；（2）令ai是第i个矩形中的白格的个数，则a1＜a2＜…＜ap求出使上述剪法存在的p的最大可能值，同时对这个p求出所有可能的a1，a2，…，ap．【题说】第十六届（1974年）国际数学奥林匹克题4．本题由保加利亚提供．由此可知p≤7．p=7时只有五种可能的组合：5第一种组合不可能在棋盘上实现，因为棋盘上剪出的矩形不可能是22格的，其他四种情况都是可以实现的，如上图所示（图中数字表示该块含方格数）．E2－063在一张正方形纸上画出n个边与纸的边平行的矩形，这些矩形中任两个都没有公共内点，证明：如果剪下

5、所有的矩形，那么纸片数不大于n+1．【题说】第十届（1976年）全苏数学奥林匹克十年级题3．【证】设纸片数为k，在每张纸片上标出4个顶点（纸片上可能不止四个顶点），这些顶点每一个都是矩形的顶点，或原正方形的顶点，如果两张纸片上标出的两个顶点实际上是同一个点，那么这一点一定是原来靠在一起的两个矩形的共同顶点．因此4k≤4n+4从而k≤n+1 E2－064某区学生若干人参加数学竞赛，每个学生得分都是整数，总分为8250，前三名的分数是88、85、80，最低是30分，得同一分数的学生都不超过3人．问至少有多少学生得分不低于60

6、分（包括前三名）？【题说】1979年全国联赛二试题7．【解】除了前三名外，得分为30～79，总分为8250-（88+85+80）=7997．其中分数为30～59的人至多（每种分数三人），共得（30+31+…+59）×3=4005分，因此至少有7997-4005=3992分分配给60～79分的人．由于（79+78+…+61）×3=3990＜3992，所以60～79的人数至少为3×（79-61+1）+1=58．故得分不低于60分的学生总数为61人（包括前三名）． E2－065一个团体有1982人，在任何4人的小组中，至少有一

7、人认识其他3人，问在此团体中，认识其他所有人的最少人数是多少？【题说】第十一届（1982年）美国数学奥林匹克题1．【解】认识可能是双方的，也可能是单方的．1．假设认识按双向性理解，作一个有1982个点的图G，每点代表一个人，若两人彼此不认识，就将相应两点连一条边，认识者不连．于是，我们的问题变为：已知在此图中，每四点所成之子图，至少有一孤立点，问图中最少有多少个孤立点？设G中有边AB．若又有边CD连结另两点C、D，则A、B、C、D四点所成子图中无孤立点，矛盾．因此G中任一点或者是孤立点，或者与A或B相连．设点C与A相连，

8、则对任一点D，由于A、B、C、D所成子图中有孤立点，所以D不与A、B相连，从而（根据上面所证）D为G的孤立点．于是G中至多有A、B、C三点非孤立点，至少有1979个孤立点，即该团体中至少有1979个人认识其他所有人．2．若认识是单向的，设1982人围成一圆圈，每人皆不认识其右邻，但认识其余的人．容易证明，任4人中都至