中文XML论坛--离散学习讨论专区（请牛人帮忙解答）

贴子主题：离散学习讨论专区（请牛人帮忙解答）

本主题类别:

有疑问的进来讨论一下
也请牛大哥马大姐进来指点指点啊

我先请教两个问题啊
什么是鸽巢定理

一笑而过 (280008207) 11:39:48
鸽巢原理
鸽巢原理（也称Dirichlet抽屉原理或者鞋盒原理）一般用于解决下面的问题：具有给定性质的项是否存在？当成功地使用了鸽巢原理时，原理只是告诉我们对象存在；而不告诉我们有多少个对象和怎样找到它们。
将讨论的鸽巢原理的第一种形式：如果n只鸽子飞入k个巢且k<n，那么某些巢至少包含两只鸽子。这句话正确的原因可以通过反证来得出。如果结论是错误的，每个巢至多有一只鸽子，这时我们有至多k只鸽子。因为有n只鸽子，且n>k，得出矛盾。
鸽巢原理（第一种形式）
如果n只鸽子飞入k个巢且在k<n，那么某些巢饮食至少两只鸽子。
鸽巢原理（第二种形式）
如果f是一个从有限集合X到有限集合Y的函数|X|>|Y|，那么对于某些x1,x2属于X，且x1不等于x2，有f(x1)=f(x2)。
鸽巢原理（第三种形式）
令f是一个从有限集合X到有限集合Y的函数。假设|X|=n，|Y|=m，令K=[n/m]，（[]代表取上整，因为不好表示，所以这样了），那么有至少k个值a1,...,ak属于X使得
f(a1)=f(a2)=...=f(ak)

枫の红林_天大(286602387)  (2006-04-18 11:32:47)
简单的说就是n+1只鸽子飞进n个鸽巢，则必定有一个鸽巢里有两只以上的鸽子
风(260427696)  (2006-04-18 11:32:21)
也有啊，在底下的注释里面吧，好象是的
一笑而过 (280008207)  (2006-04-18 11:31:50)
也是离散数学里面的，在屈婉宁的那本书上没有，但是在一些国外的书上有。。
一笑而过 (280008207)  (2006-04-18 11:31:26)
鸽巢原理还简单一些，就是代表多少个鸽子多少个巢，到最后通过运算至少有多少个鸽子占一个巢。

什么是等势集合


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	93.002ms