离散数学第三讲

二、容斥原理与鸽巢原理 1、 容斥原理(§1。3。) （计数原理、包含排斥原理） 容斥原理（包含排斥原理）： 设A，B是有限集，则

A?B?A?B?A?B

容斥原理的相关推论： (i)

A?B?C ?A?B?C?A?B?B?C?A?C?A?B?C (ii) 利用归纳法

A1?A2?A3???An??Ai?

i?1n1?i?j?n?A?Aij?1?i?j?k?n?A?Aij?Ak

???(?1)n?1A1?A2???An(iii)

A?A?U, A?U?A

(iv)

A1?A2???An?U?A1?A2???An

（注意基的具体含义）

设S是有限集，P1,P2,?,PrPi的子集，即

是r条性质，

Ai是S中具有性质

A?i

?xx?S,x具有性质Pi?

（i=1,2,…，r） 则 （1）S 中至少具有性质

P1,P2,?,PrA1?A2?A3???Ar??Ai?i?1r1?i?j?r一条的元素数是：

?A?Aij?1?i?j?k?r?A?Aij?Ak

???(?1)r?1A1?A2???Ar （2）S 中不具有性质 元素数是：

P1,P2,?,Pr的

A1?A2???Ar?U?A1?A2???Ar

e.g 1 设n?2，?(n)表示不超过n 且与n 互质的 正整数的个数，求?(n)

该函数在计算机中称为EURTER函数。 解：

S??1,2,3,?,n?

不妨令：

n?p1p2???pr数； 设

?1?1?r p1,p2,?,pr为互异的质

Ai??xx?S,且xpi?n,AiAj?pipji?1,2,?,r

?

nAi?则pi?(n)?A1A2?Ar……

2、 鸽巢原理（抽屉原理、鞋盒原理）（教材P63）

n+1个鸽子飞进n个鸽巢，则可以找到一鸽巢里至少有2只鸽子。 或者：

如果k+1个或更多的物体放入k个盒子，那么至少有一个盒子包含了2个或更多的物体。

e.g 1 把10个点放入边长为1的正三角形内，证明，可以

找到两个点，它们之间的距离不超过三分之一。

（具体问题，找鸽子，做笼子）

推广1、n个鸽洞，（多于）r?n?1个鸽子，必有一个鸽洞住有至少r+1 只鸽子。

推论2、 （平均数原理） 设

xi是自然数，且

x1?x2???xn?r(r?N) n 则 ?

xk，使得 xk?r?1。

证明：……

e.g 2 一个园盘划分为36个扇形，把1~36这36个数放入扇形中，每格一个数，证明无论怎样放，总可以找到三个连续的扇形，使得这三个扇形中的数之和?56。 解：…… 练习

No1 有n个乒乓球运动员比赛，每人至少赛一场，同一对手至多比赛一场，证明这n个运动员可以找到二个运动员，他们比赛的场数一样。 No2 设

x1,x2,?,xn是n个正整数，

证明，其中至少存在若干个（下标）连续的数，使得它们的和是n的倍数。

e.g 3 假定一组6个人，任意两个人或者是朋友或者是敌人，证明在这组人中或存在3个人彼此都是朋友，或存在3个人彼此都是敌人。(教材P65：例3.12)

本文来源：https://www.bwwdw.com/article/x2xa.html