1.1、 中外奥赛概述
数学奥林匹克是专门解决数学难题的竞赛,它起源于16世纪意大利数学家菲奥的挑战塔塔利亚开始,举行公开竞争的三次方程的解决方案.奥林匹克数学竞赛的发展,从1894年匈牙利首开数学竞赛的先河,到1956年罗马尼亚的罗曼教授向东欧七国建议举办国际数学竞赛,并于1959年7月,在罗马尼亚的古都不拉索夫举行了第一届国际数学奥林匹克(IMO) [1],这一数学竞赛跨国界的创举".在此之后,有不少国家纷纷加入到数学竞赛的队伍中来,从1981年的第22届开始,是IMO走向成熟的开端.
中国数学竞赛[2]始于1956年,由我国华罗庚、苏步青等数学家发起,但是由于“文化大革命”中断了13年,直到1978年恢复,慢慢走向国际.1985年,我国首次参加第26届IMO.从1990年的第31届IMO开始,我国数学竞赛迅速的成长起来,在比赛中取得优异的成绩.
数学竞赛已成为国际公认的教育活动,从小学、中学到大学,参赛人数之多、范围之广、试题难度之高等均不比奥运会逊色.单墫教授指出:“数学竞赛是才智的角逐”.试题的难度不在于解决问题所需要许多高深的知识,而在于对数学本质的洞察力,创造力和数学机智.在对IMO试题的统计表明,试题范围主要稳定在数论、组合数学、数列、不等式、函数方程和几何等.与通常题目相比,这些题更多的是在考察一个人的数学思维,以及数学技巧.
1.2、 奥数中的组合数学方法
数学竞赛题中出现组合问题往往表达形式上简单明了,然后求解这类问题却需要一定的技巧,没有固定的套路,骆祖英[3]说:“竞赛题中组合数学实乃非常规数学知识和方法之统称,变化多端,技巧性强的组合数学题的解题关键,在于精通解题策略,但策略本身就是对各种方法的熟练掌握,真所谓万变不离其宗,只要掌握好了方法,难题就迎刃而解.”无论是以退为进还是运动变换,或是模式归化,亦是涂色转换,这些野路子都是组合数学的魅力所在,所以要解决组合问题需要掌握好组合的基本方法.
在组合数学中主要由以下几个问题:存在性问题,计数问题,构造问题以及最优化问题.在这些问题中,在组合数学中,数学归纳法是一个最常用的证明方法,反证法是解决存在性问题最有力的武器.解决组合问题常常需要“对症下药”,一般考察的一些组合方法有:基本计数原理以及公式(加法原理和乘法原理,排列组合公式,二项式定理),容斥原理,递推公式法,生成函数方法,抽屉原理等其他方法.
1.3、 研究现状
2、 奥赛中的组合数学方法介绍
本文主要介绍容斥原理法,递推公式法以及生成函数方法,容斥原理有着以退为进的特点,且容斥原理方法以及其对偶形式在奥数中有着广泛的应用.递推关系方法在解决数列的问题中有着重要的作用,著名的Hanoi塔问题(梵塔之谜),Fibonacci数列都属于经典的利用生成函数解决递推关系的例子,所以生成函数和递推关系之间有着非常密切的联系,所以在例子中也将递推关系和生成函数方法合并一起介绍.
2.1、 容斥原理法
容斥原理又称包含排斥原理,逐步淘汰原理,它有着非常广泛的应用,可以解决一些十分有趣的问题.