《Mathematical Olympiad——组合数学》——抽屉原理

时间:2022-01-02 20:50:44

抽屉原理可以说是组合数学中最简单易懂的一个原理了,其最简单最原始的一个表达形式:对于n本书放到n-1个抽屉中,保证每个抽屉都要有书,则必存在一个抽屉中有2本书。但是这个简单的原理在很多问题中都能够巧妙的应用到,融合将问题一步步抽象转化来接近抽屉原理的原始模型,是用好抽屉原理的关键。

问题一:两个半径相等的圆盘上各有一个内接正2n边形,每个正2n边形的顶点有一半染上黄色,一般染上蓝色,将这一个圆盘放在另一个圆盘上并使得两个正2n边形的顶点均重合,这样得到2n对顶点,如果一对顶点中两个重合的顶点颜色相同,则称其为“匹配点对”。证明:存在一种放置方式,使得至少有n对匹配点对。

证明:我们首先从任意一种重合方式开始,用a1表示当前方式含有的匹配点对的个数,然后我们将其中一个圆盘旋转2n - 1次,每次旋转的角度π/n,这样我们便得到了多有的放置方法——{a1,a2,a3……a(2n)}。考察所有情况匹配点对的总和,利用简单的计数原理,我们得到等式:a1 + a2 + a3+……+a(2n) = 2n*n,由此再利用抽屉原理,得证。

问题二:正整数1~200分成50个集合。证明:可以从其中某一个集合中找出三个数,它们形成三角形的三边之长。

证明:我们考虑100~200这101个数字,分到50个集合当中,必然存在3个数字分到某个集合当中,考察分布在[100,200]的整数,任取三个数都是满足三角形三边定理的,得证。

问题三:一次射箭比赛共有30名选手参加。将靶子分为两个区域,规定:射中区域一得10分,射中区域二得5分,未射中靶子不得分,每名选手射16箭。比赛结束后,统计显示射中区域二的箭超过50%,射中区域一和未射中靶子的箭数相同。证明:有两名选手得分相同。

证明:我们设第i个人射中区域一、区域二、未射中的箭数分别是ai、bi、ci.则首先有∑ai = ∑ci < 16*30 /4 = 120.

第i个选手的得分可以这样表示:10ai + 5bi = 5ai + 5(ai + bi) = 5ai + 5(16 - ci) = 80 + 5(ai - ci)。

现在考虑反证法,假设30个选手的分数各不相同,则ai - ci有30个各不相同的取值。考虑到ai - ci∈[-16 , 16],由抽屉原理得,存在满足ai-ci>0或ai - ci < 0的组数大于等于15的情况,我们以ai - ci > 0为例,我们将ai - ci按照严格递增的顺序排列,则有ai - ci >=i , 所以ai >= i.

因此,对于满足ai - ci > 0的ai,有不等式∑ai >= 1 + 2 + 3+……+15 = 120成立,这与已知事实矛盾,因此假设不成立。

证毕。

证明: