抽屉原理


定义

抽屉原理,亦称鸽巢原理(the pigeonhole principle)。

它常被用于证明存在性证明和求最坏情况下的解。

简单情况

个物体,划分为 组,那么有至少一组有两个(或以上)的物体。

这个定理看起来比较显然,证明方法考虑反证法:假如每个分组有至多 个物体,那么最多有 个物体,而实际上有 个物体,矛盾。

推广

个物体,划分为 组,那么至少存在一个分组,含有大于或等于 个物品。

推广的形式也可以使用反证法证明:若每个分组含有小于 个物体,则其总和 矛盾。

此外,划分还可以弱化为覆盖结论不变。
给定集合 , 一个 的非空子集构成的簇

  • 若满足 则称为 的一个覆盖(cover)
  • 若一个覆盖还满足 则称为 的一个划分。

鸽巢原理可以有如下叙述:对于 的一个覆盖 有至少一个集合 满足

参考文献

贡献者:@queenwen@WenzelTian@Great-designer

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组