【水】鸽巢原理
chenruixi2024/02/07原创 蒟蒻妙妙屋 IP:湖南
关键词
组合数学鸽巢原理

鸽巢原理是这样叙述的:如果有k个鸽巢,多于k只鸽子,每只鸽子在一个鸽巢内,那么必有一个鸽巢内至少有两只鸽子。或者跟普遍地说,对于k个巢,n只鸽,那么必有鸽巢至少有\(\left\lfloor \frac{\text{n}}{k} \right\rfloor \)另一些鸽巢必定至多有\(\left\lfloor \frac{\text{n}}{k} \right\rfloor \)只鸽子。其实它有大家更为耳熟能详的一个名字:抽屉原理。它虽然简单,但是可以创造性地用来证明一些意想不到的复杂结果。用它处理问题的时候需要明确哪些对象代表鸽子,哪些对象代表巢。

例题一:假设有n个人参加一次会议,有些人与另一些人握手,证明至少有两个人与同样多个人握手。

解:

每个人的握手次数及他和对方握手的人数必在0、1、.....n-1的范围之内,人就是鸽子,握手次数就是巢。是否可能将每个巢都占有呢?或者说有一个人握0次手,却有一个人和参加会议的除他以外的每一个人都握手,这就产生了矛盾,所以必定至少有一个巢没有被占有。现在有n只鸽子,n-1个巢,所以必有两只鸽子在一个巢里,也就是说至少有两个人的握手次数相同,得证。


例题二:证明存在每个由4个数字组成的数列,有无穷多次出现在2的幂的前4位数字中。(除掉零开头的)

证:假设对每一个由4个数字组成的数列构造一个集合,把2的幂的前4位分类放入集合内,前9个幂不放入集合内,因为2的幂有无穷多个,所以有一些集合必容纳无穷多个2的幂。对于这个集合的由4个数字组成的数列,有无穷多次出现在2的幂的前4位数字中。


例题三:给出一个由1985个不同的正整数组成的集合M,其中任何一个都没有大于23的质约数。证明M含有一个由4个元素组成的子集,这4个元素的积是一个整数的4次幂。

证明:因为集合大写的m中没有元素大于23的制约数,所以每一个元素都可以写成以下形式。对于一些整数\({{\alpha }_{\text{i}}}\)>=0,有

\[{{2}^{{{\alpha }_{1}}}}{{3}^{{{\alpha }_{2}}}}{{5}^{{{\alpha }_{3}}}}{{7}^{{{\alpha }_{4}}}}{{11}^{{{\alpha }_{5}}}}{{13}^{{{\alpha }_{6}}}}{{17}^{{{\alpha }_{7}}}}{{19}^{{{\alpha }_{8}}}}{{23}^{{{\alpha }_{9}}}}\]


需要注意,如果两个数的质因数分解式中的每一个质因数的质数的奇偶性都相同,那么他们的积是完全平方数。因为对9个指数中的每一个数都有积或偶这两种可能,所以奇偶性共有2的9次方等于512种不同的分布。

根据鸽巢原理,因为有1985个不同的整数以及有512种既有型的分布情况,所以必定至少有两个数的奇偶性的分布相同。除这两个数以外,还有1983个不同的整数,再利用鸽巢原理找出另一些对奇偶性的分布相同的数。不必与第一对数的奇偶性的分布相同,这一过程我们可以重复513次,此时我们已经排除了这1985个数中的1026个数,还多出959个数,因为还比512多,所以在这种情况下还可以利用鸽巢原理。

现在有513对乘积是完全平方数的数。考虑这513个完全平方数,我们考察这些数的质因数分解式中各指数除以4的余数,因为这些数都是完全平方数,所以余数只可能是0和2,注意与前面的基偶性情况一样,如果两个完全平方数有同样的余数分布,那么这两个完全平方数的积是一个整数的4次方,因为我们有513个完全平方数以及有512种余数的分布情况,根据鸽巢原理必定有两个完全平方数有同样的余数分布。

从原来的集合M中取出这两个数乘以我们乘到完全平方数的两个数,就得到完全4次幂,于是我们就有一个含有4个元素的子集,他们的积是一个整数的4次幂。


注:例题有其他解法。


最重要的还是把握好对象特点,对应好鸽和巢,比较抽象,但很有意思。


来自:数理化 / 数学严肃内容:专业科普
1
5
已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也
孙益楠_BG5BNA
8个月0天前 IP:英国
929200

突然想到假如结合一下编程类书籍特色,那么组合学开头便是这样:

你已经掌握鸽巢原理了,下面来完成这道例题吧:

Ex.1 证明霍尔婚配定理(答案略)

引用
评论(1)
2
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

所属专业
上级专业
同级专业
chenruixi
进士 机友 笔友
文章
6
回复
114
学术分
0
2022/07/21注册,6时20分前活动

常常想,生活本没有意义,人们所创造的文化永远脱离不了人本身。静静地看着,奢求时间会给我答案,这大概是不好的。

我们走吧,路远着呢

亦常常想,总有一天会在最美的地方停下,从此便是永远

AKCSP-J!

蒟蒻妙妙屋参谋长

主体类型:个人
所属领域:无
认证方式:手机号
IP归属地:湖南
相似文章推荐
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}
视频暂不能访问,请登录试试
仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。
音频暂不能访问,请登录试试
支持的图片格式:jpg, jpeg, png
插入公式
评论控制
加载中...
文号:{{pid}}
投诉或举报
加载中...
{{tip}}
请选择违规类型:
{{reason.type}}

空空如也

加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
收藏
取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}