抽屉原理

  • 格式:doc
  • 大小:71.00 KB
  • 文档页数:2

抽屉原理 (第 1 页 共 2 页) 专题——抽屉原理

一、抽屉原理的基本形式

1、有n个元素放进m个集合,则必存在一个集合至少放有k个元素.

其中,的倍数不是的倍数是mnmnmnmnk1

推论1:若有1n个元素放进n个集合,则必存在一个集合至少放2个元素.

推论2:若把1mn个元素放进n个集合,则必存在一个集合至少放有1m个元素.

推论3:若把121nmmm个元素放进n个集合,则必存在一个集合)1(nkAk至少放有1km个元素.

推论4:若把无穷集合分成有限个集合,则必存在一个子集合含有无穷个元素.

2、若Saaan21,则必存在ka,la(nlk1),使nSak,nSal.

推论1:021naaa,则必存在ka,使0ka.

二、例题选讲

例1、能否在1010的方格表的每个空格中分别填上1、2、3这三个数之一,使得每行、每列及对角线上的各个数之和互不相同?对你的结论加以证明.

例2、任给5个整数,证明必能从其中选出3个,使得它们的和能被3整除.

例3、证明:从52个正整数中,必可找出两数使之和或差可被100整除.

抽屉原理 (第 2 页 共 2 页) 例4、任意给定正整数m,求证:一定有m的某一个整倍数,它完全由0和1两个数字所组成.

例5、一个棋手用11周时间参加一次比赛,每天至少比赛一局,但为免过于疲劳,他在每连续7天内比赛不超过12局,总共赛不超过132局.求证:必有连续若干天他恰好共赛了21局,是否必有连续若干天他恰好共赛了22局?

例6、把圆周分成36段,将1,2,…,36任意标在每一段上,那么一定存在连续的三段,它们的数字之和至少是56.

例7、设121,,,naaa是正整数,并且naaan21121.

证明:总能找到这样的两个数)11(njiaaji与,使得ja能被ia整除.

例8、已知整数1021,,,aaa,证明:存在一个非零数列1021,...,,xxx,使得对1,0,1ix,和10102211xaxaxa能被1001整除.

例9、任何十个不同的两位数之集合必能选出两个不相交的子集,使每个子集的各数之和相等.