有哪些信誉好的足球投注网站- 1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
- 2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
- 4、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
- 5、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
- 6、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 7、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第二章、鸽巢原理和Ramsey定理.pdf
组合数学讲义(内部资料，严禁商用) 第二章 鸽巢原理和Ramsey定理 2008-2009学年第二学期 第二章 鸽巢原理和Ramsey 定理 一、鸽巢原理 鸽巢原理是组合数学中的一个重要而又基本的原理，它可以用来解决很多日常生活和科 学技术上的趣题，并且常能得到一些令人惊异的结果。这个原理有各种称呼，最常用的名称 是鸽巢原理、Dirichlet 抽屉原理和鞋盒原理。 1、问题的引入 1) 366 个人中必然有至少两个人生日相同。 2) 抽屉里散放着10 双手套，从中任意抽取11 只，其中至少有两只是成双的。 3) 某次会议有n 位代表参加，每位代表认识其他代表中某些人，则至少有两个人认识的 人数是一样的。 4) 任给5 个不同的整数，其中至少有3 个数的和被3 除尽。 这些例子的道理都很简单，以第一个例子为例，一年 365 天，366 个人至少有一天是某 两个人的生日。最后一例子也有类似的道理，5 个数中至少有 3 个同为奇数或同为偶数，无 论哪种情况，它们的和都能被3 除尽。 2、鸽巢原理的简单形式 定理 1、如果把n +1 n 只鸽子放入 个鸽巢，则至少有一个鸽巢里含有两只或两只以上鸽 子。 n n 证明：反证法。假设每个鸽巢里至多包含一只鸽子，则 个鸽巢里鸽子的总数小于等于 ， 这与已知矛盾。 注：此原理不能用来寻找究竟是那个鸽巢里含有两只或两只以上鸽子。即此原理只能用 来断定这种鸽巢的存在，并未指出怎样构造这种安排或怎样寻找出现这种现象的场合，除非 检查所有的可能情况。 此原理的应用： 例1、 已知每个人的头发根数都小于20 万，对20 万人以上的城市就可以断定，至少有 两个人头发根数相等。 1 例2 、在边长为1 的正三角形中任意放5 个点，证明至少有两个点之间的距离不大于 。 2 1 证明：构造鸽巢原理如图1,将5 个点放在4 个边长为 的小正三角形内，根据鸽巢原理， 2 第1页本章共27页 组合数学讲义(涉外学院数学本科用) 2008-2009学年第二学期 制作人 陈勇 1 必有一个小三角形内至少有两个点，这两个点的距离就小于或等于 。 2 图1 2n n +1 n +1 例3、从1 到 的正整数中任取 个，则这 个数中：1)至少有一对数，其中一个 数是另一个数的倍数。2) 至少有一对数是互素的。 证明：1) 设所取的n +1个数是 a ,a ,L,a ,a
文档评论（0）