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

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

ID:13825826

大小:67.50 KB

页数:5页

时间:2018-07-24

数学奥林匹克题解e组合数学--计数和离散最值061-070_第1页
数学奥林匹克题解e组合数学--计数和离散最值061-070_第2页
数学奥林匹克题解e组合数学--计数和离散最值061-070_第3页
数学奥林匹克题解e组合数学--计数和离散最值061-070_第4页
数学奥林匹克题解e组合数学--计数和离散最值061-070_第5页
资源描述:

《数学奥林匹克题解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人中都至

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。