中学奥数中的组合问题.doc

目 录

1. 前言 ............................................................................................................................................................ 2

2. 基础知识 .................................................................................................................................................... 3

2.1 抽屉原则 .......................................................................................................................................... 3

2.2 容斥原理 .......................................................................................................................................... 4

3. 经典例题 .................................................................................................................................................... 6

3.1抽屉原则 ........................................................................................................................................... 6

3.1.1 抽屉原则在代数问题中的应用 ........................................................................................... 7

3.1.2 抽屉原则在几何问题中的应用 ........................................................................................... 9

3.2容斥原理 ......................................................................................................................................... 10

3.2.1 容斥原理在错排问题中的应用 ......................................................................................... 10

3.2.2 容斥原理在数论中的作用 ................................................................................................. 11

4. 总结 .......................................................................................................................................................... 15

参考文献： ................................................................................................................................................... 15

致谢： ........................................................................................................................................................... 16

中学奥数中的组合问题

王芳

西南大学数学与统计学院，重庆 400715

摘要：抽屉原则和容斥原理是组合问题中的重要组成部分。本文通过给出抽屉原则和容斥原理

的多种形式，详细证明过程及对一些经典例题的剖析，来探讨抽屉原则和容斥原理在数论，图论和代数等多个领域中有关存在性问题和计数问题方面的应用。

关键词：数学奥林匹克；抽屉原则；容斥原理

Portfolio problems in middle school mathematical olympiad

Fang Wang

School of Mathematics and Statistics, Southwest University, Chongqing 400715, China

Abstract: The drawer principle and the Inclusion-Exclusion Principle are important parts of combination

problems. In this paper we give detailed proof processes and analysises of the classic examples, and

explore the application of the drawer principle and the Inclusion-Exclusion Principle in problems respect to number theory, graph theory, algebra and other fields related to the existence problems and count

problems.

Key words: mathematical olympiad ;the drawer principle; the Inclusion-Exclusion Principle

1. 前言

数学奥林匹克是一种智力的比拼。数学奥林匹克的试题，大部分出自数学名家，而

且是通过巧妙构思、精心策划编写出来。所以，数学奥林匹克试题中有很多令人赞不绝口的佳题。求解或论证一道数学奥林匹克试题，往往既不需要烦琐的计算演绎，也不需要冗长的论证推理，但需要“灵感”。有了这种“灵感”，才能在“山重水复疑无路”时，有“柳暗花明又一村”的顿悟。那些数学奥林匹克获奖者就是在考场上的灵感，能立即抓住题目的本质内容，从而使得问题迎刃而解。然而“灵感”的到来，不仅仅需要拥有

一定的数学知识储备，同时也需要形象思维和逻辑思维的能力。组合数学作为奥林匹克数学的重要组成部分，则更需要“灵感”。

组合数学是数学的一门重要分支。近几年来，由于计算机科学的日益发达以及逐渐

增多的组合问题，使组合理论得到了极大地丰富和发展，这对数学竞赛的命题工作产生了一定的影响。解决奥数中出现的初等组合问题并不需要高等的数学理论知识，仅仅是在趣味命题中包含了特别的解题技巧，因此无论是对智力训练还是竞赛准备，学习和研究这些问题都是非常有意义的。奥数试题许多来源于数学最新研究成果的初等命题，体现着深层的数学内容，独特的数学思想，巧妙的数学构思和生动有趣的阐述。

本文是基于分析了历届国际数学奥林匹克试题的基础上，留意到组合数学是每届

IMO必考的内容，并且在试题中占到很大的比例。在组合问题中，涉及到的知识多而广，如抽屉原则，容斥原理，组合计数，组合几何，图形覆盖，图论问题等等。如果参赛选手拥有一定的知识储备，见过各式各样的题目，在做题时就会更容易产生灵感，找到题眼，试题最终迎刃而解。鉴于此，创作了此文。本文尝试通过对一些赛题的分析，探索有关组合问题的解题思路，与广大热爱数学奥林匹克竞赛的同胞们共同分享。

2. 基础知识

组合数学包含了数学竞赛中除去代数、几何、数论以外的所有内容，如组合计数、

容斥原理、凸包、覆盖、染色问题、抽屉原则、图论等。由于组合体系异常庞大，本文仅从其中选择两个在数学奥林匹克中常见的问题进行分析，讨论。

2.1 抽屉原则

抽屉原则也叫鸽巢原理，它是德国数学家狄利克雷首先提出来的，也称狄利克雷原

则。它是组合数学里最简单也是最基本的原理，它有如下几种表现形式：

I.把n+1个元素分成n个集合，那么必有一个集合中含有两个或两个以上的元素。

证明：用反证法极易得到证明。

设把n+1个元素分成n个集合：A1,A2, ,An，再用a1,a2, ,an表示这n个集合里相

应的元素个数。需要证明至少存在某个ai大于或等于2。

（反证法）假设结论不成立，即对每一个ai都有ai 2，则因为ai是整数，应有ai 1，

于是有a1 a2 an 1 1 1 n n 1,这与题设矛盾。

所以，至少有一个ai 2。

II.把nm＋1个元素分成n个集合，那么必有一组中含有m＋1个或m＋1个以上

元素。

III.把n个元素分成k个集合，那么必有一个集合中元素的个数≥[

个集合中元素的个数≤[n]，也必有一kn]。其中，[x]为高斯函数。 k

IV.把q1 q2 qn-n 1个元素分给n个集合，那么必有一个i(1≤i≤n)，在第i

个集合中元素的个 …… 此处隐藏：12883字，全部文档内容请下载后查看。喜欢就下载吧 ……