王树磊9号奥数

1、济南幼儿师范高等专科学校初等教育学院20132014 学年第二学期 2009 级理科专业（初中起点）高等数学期末考试王树磊 09 号有趣的方法在这章中我们将要学习运用组合论方法中的图论法、抽屉法、计数法解决一些有趣的实际问题。在人们从事的各种活动中，为了反映事物之间的关系，常在纸上用点和线画出各种各样的示意图。我们把它称为图论法。抽屉原理 又称 鸽巢原理 ，它是 组合数学 的一个基本原理，最先是由德国 数学家 狭利克 雷明 确地提出来的，因此，也称为狭利克雷原理。例 1 附属小学四年一班有49 名学生，一天，数学课的其昌老师对同学们说：“我可以断定，你们中至少有5 名同学的生日在同一个月。”同

2、学们通过老师的解释，才明白其中的奥妙。即把1 年的 12 个月看作12 个“抽屉”，并且按照月份把这12 个“抽屉”编上112 号；把 49 名同学看作49 个“桃子”，对于每个同学来说，他（她）是几月份生日的，就把他（她）放入第几号“抽屉”。于是问题转化为将49 个桃子放入12 个抽屉，由于49=124+1，根据抽屉原理，一定有一个抽屉里被放入了 5 个桃子。我们再把这些话翻译回去，就是：49 名学生中至少有5 名学生的生日在同一个月。例 2 把 1600 元人民币奖给100 名优秀学生，为什么至少有4 名学生得到的钱一样多？要使没有4 名学生得到的钱一样多，那么至多有3 名学生得到的一样多

3、。这样3 名学生分为一组，最经济的分法为：3 人每人只得0 元，3 人每人只得1 元 3 人每人只得32 元，还有 1 人得 33 元。这样一共需要3（ 0+1+2+3+ +32）+33=1617（元）比实际钱数多出17 元，这 17 元无论从哪一组或哪几组中取出，都至少有4 名学生得的一样例 3木箱里装有红色球3 个、黄色球5 个、蓝色球7 个，若蒙眼去摸，为保证取出的球中有两个球的颜色相同，则最少要取出多少个球？解：把 3 种颜色看作3个抽屉，若要符合题意，则小球的数目必须大于3，故至少取出4个小球才能符合要求。例 4一幅扑克牌有54 张，最少要抽取几张牌，方能保证其中至少有2 张牌有相同

4、的点数？解：点数为1(a) 、2、3、4、 5、6、7、8、9、10、11(j) 、 12(q)、 13(k) 的牌各取1 张，再取大王、小王各 1 张，一共 15 张，这 15 张牌中，没有两张的点数相同。这样，如果任意再取1 张的话，它的点数必为 113 中的一个，于是有2 张点数相同。例 5 某公司在六个城市a、b、c、d、e、f 设有分公司。各城市间的直接航线的票价如下表所示。a b c d e f a b c d e f 50 40 25 10 15 20 25 10 20 10 25 55 求 a城市到各城市间票价最低的航线。答案： 由表知从a到 b、c、d、e、f 票价最低的航线

5、分别为： a 10 f 25 b； a 25 e 20 c；a 25 e 10 f；a 25 e；a 10 f 。例 6 有甲、乙、丙、丁、戊、已六名运动员报名参加a、b、 c 、d、e、f 六个项目的比赛。表中打的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，才能保证每名运动员都不连续地参加两项比赛。解：把比赛 项 目 作 为研究对象， 用点表示。 如果两 个 项 目 有同 一 名 运 动员参加， 就在代 表 这 两 个项 目 的 点 之间 连 成 一 条线，可得一图。在该图中只要找出一个点的序列，使依次排列的两个点间没有连线，就能保证每名运动员不会连续参加两项比赛。例如，从

6、图上可看出，按照a、c、b、 f、e、d顺序安排比赛，即可满足要求。例 7：有 27 支小足球队参加足球比赛，（1）如果每两队比赛一场（即进行单循环比赛），需要比赛多少场？（2）如果进行淘汰赛最后决出冠军，共需比赛多少场？【解】 （ 1） 27 支小足球队参加足球比赛a b c d e f 甲乙丙丁戊已第一支足球队比完26 场，第二支还需比25 场，第三支比24 场以此类推下去，即需要比赛26+25+24+1=226126）（=351（场）（2） 每比赛一场球赛就会淘汰一支足球队，所以进行淘汰赛最后决出冠军，共需比赛27-1=26场例 8 ：47 人参加一次数学竞赛，比赛共有三道题，结果30

7、人做对了第一道题，11 人做对了第二道题，7人做对第三道题. 做对了第一、二题的有3 人， . 做对了第一、三题的有5 人， . 做对了第二、三题的有4 人，全部做错的人数在810 之间，试求三道题都做对的人数. 【解】第一道 30 3 11 第二道 5 4 7 810 第三道全部做错全部做错的人数在810 之间 47-8=39，47-10=37 做对题的人数：47-8=39 ，47-10=37 在 3739 之间除全部做错和全部做对外的人数：30+11+7-3-5-4=36 （人）则三道题都做对的人数：37-36=1 （人）或38-36=2 （人）或39-36=3 （人）例 9 ：有红、白、

8、黑三种颜色的球各10 个混合放在一个袋子里，从中至少要摸出多少个球，才能保证摸出的球中有两对颜色不同的球. 【解】从最不利的情况考虑，开始摸出的10 个球都是红球，接着摸出1 个白球与1 个黑球，在这种情况下要保证摸出的球中有两对颜色不同的球，还得再摸1 个球，即至少要摸出10+1+1+1=13 个球例 10：数角数角的方法可以采用数线段的方法来数，就是角的总数等于从1 开始的几个连续自然数的和，这个和里面的最大的加数是角分线的条数加1 解：在 aob内有 4 条角分线，所以共有角：5+4+3+2+1=15（个）；在aob内有 9 条角分线，所以共有角： 10+9+8+7+6+5+4+3+2+

9、1=55 （个）； 周角内含有6 个基本角， 所以共有角： 6 （6-1 ） +1=31 （个）. 练习1、 求证：任给四个两两不等的整数，其中必有两个数，它们的差是3 的倍数 . 【解】一个数除以3 后的余数有三种情况：0 或 1 或 2 四个两两不等的整数除以3，其中必有两个余数相同，那么余数相同的两个整数的差必是3 的倍数，得证 . 2、 从 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

10、、13 ，19 、 15，17 在 8 个集合中各取1 个数，共取了8 个数，如果再取1 个数必在8 个集合中，即取9 个数，其中一定有两个数在同一集合中，之和为32，得证 . 3. 一条直线分一个平面为两部分两条直线最多分一个平面为四部分问5 条直线最多分这个平面为多少部分 ? 解析：我们可以在纸上试着画出1 条直线， 2 条直线， 3 条直线，时的情形，于是得到下表：由上表已知5 条直线最多可将这个平面分成16 个部分，并且不难知晓，当有n 条直线时，最多可将平面分成2+2+3+4+ +n 个部分4. 如下图为一幅街道图，从a出发经过十字路口b，但不经过c走到 d的不同的最短路线有多少条?

11、 解析如下：5. 有十名研究生要参加六门课程的考试。由于选修的课程不同，考试门数也不一样。表6-4 给出了每个研究生应参加考试的课程（打号的）。规定考试应在三天内结束，每天上下午各安排一门。研究要求每人每天最多考一门，又课程a必须安排在第一天上午考，课程f 安排在最后一门考，课程b只能安排在下午考试，试列出一个满足各方面要求的考试日程表。表 6-4 考试课程研究生a b c d e f 1 2 3 4 5 6 7 8 9 10 解： 把考试课程作为研究对象，用点表示。如果两门课程有同一名研究生参加考试，就在代表这两门课程的点之间连成一条线，可得一图如下。这个图就是练习6.3 问题的图模型。在该图中第一天上午写入a，第三天下午写入f，因 b 课程与课程 a和 f 有联系，故只能排入第二天下午，剩下的课程c、d、e要找出两个点间没有连线，例如，从图上可看出，按照a点与 e点间无连线，故e课程可排第一天下午，同理c、d课程安排