问题标题：
在一次国际会议上,k个科学家共使用p种不同语言.若任何两个科学家都至少使用一种共同的语言,但没有任何两个科学家使用的语言完全相同,求证：k小于等于2的p－1次方.将P种不同的语言记为M
问题描述：
在一次国际会议上,k个科学家共使用p种不同语言.若任何两个科学家都至少使用一种共同的语言,但没有任何两个科学家使用的语言完全相同,求证：k小于等于2的p－1次方.
将P种不同的语言记为M={M1,M2,M3,...MP}
则M的子集有2^P个
每个科学家所掌握的语言是M的一个子集
因为没有任何两位科学家使用的语言完全相同
所以子集两两不等
又由于任何两个科学家都至少使用一种共同的语言
则任何两个子集都不是互补子集
所以这K个语言子集不能超过M的子集数2^P的一半
即k大于或等于2^p-1
也有说k小于等于2^p-1的
为什么子集两两不等,任何两个子集都不是互补子集,所以这K个语言子集不能超过M的子集数2^P的一半.这是什么思路╯□╰
刘永立回答：
是这样的,这个M集合是又一系列的集合构成,每个集合都有其互补的集合,例如：{m1,m2}对应这{m3,m4,m5.mp}.所以互相不是补集的集合的个数2^p的1/2（p为偶数）或是2^p的1/2加一（p为奇数）.又由于任何一个科学家不可能是空集,所以的话,k个语言的子集不可能超过2^p/2即2^（p-1）
点击显示
科学推荐
热门科学推荐