第十节 组合论方法（计数法、抽屉法、图论方法）

第十节 组合论方法（计数法、抽屉法、图论方法）

1、有27支小足球队参加足球比赛，

（1） 如果每两队比赛一场（即进行单循环比赛），需要比赛多少场？ （2） 如果进行淘汰赛最后决出冠军，共需比赛多少场？

【解】（1）∵27支小足球队参加足球比赛

∴第一支足球队比完26场，第二支还需比25场，第三支比24场……以此类推下去，即需要比赛26+25+24+…

（26?1）?26+1==351（场）

2（2）每比赛一场球赛就会淘汰一支足球队，所以进行淘汰赛最后决

出冠军，共需比赛27-1=26场

2、47人参加一次数学竞赛，比赛共有三道题，结果30人做对了第一道题，11人做对了第二道题，7人做对第三道题.做对了第一、二题的有3人，.做对了第一、三题的有5人，.做对了第二、三题的有4人，全部做错的人数在8~10之间，试求三道题都做对的人数. 【解】

第一道 30 3 11 第二道 5 4 7 8~10

第三道 全部做错

∵全部做错的人数在8~10之间 47-8=39，47-10=37

∴做对题的人数：47-8=39，47-10=37在37~39之间

除全部做错和全部做对外的人数：30+11+7-3-5-4=36（人）

则三道题都做对的人数：37-36=1（人）或38-36=2（人）或39-36=3（人） 2、求证：任给四个两两不等的整数，其中必有两个数，它们的差是3的倍数. 【解】一个数除以3后的余数有三种情况：0或1或2

四个两两不等的整数除以3，其中必有两个余数相同，那么余数相同

的两个整数的差必是3的倍数，得证.

3、从1，3，5，…，29，31这16个奇数中，任取9个数，证明：其中一定有两个数之和是32

【证明】把1，3，5，…，29，31这16个奇数分成8个集合，{1，31}、{3，

29}、{5，27}、{7，25}、{9，23}、{11，21}、{13，19}、{15，17}

在8个集合中各取1个数，共取了8个数，如果再取1个数必在8

个集合中，即取9个数，其中一定有两个数在同一集合中，之和为32，得证.

4、有红、白、黑三种颜色的球各10个混合放在一个袋子里，从中至少要摸出多少个球，才能保证摸出的球中有两对颜色不同的球.

【解】从最不利的情况考虑，开始摸出的10个球都是红球，接着摸出1个白

球与1个黑球，在这种情况下要保证摸出的球中有两对颜色不同的球，还得再摸1个球，即至少要摸出10+1+1+1=13个球