一道关于集合的数学题再一次国际学术会议上,k个科学家共使用p种不同的语言,如果任何两个科学家都至少使用一种共同的语言,但没有任何两位科学家使用的语言完全相同,求证:k≥2^(p-1)注
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/01 04:01:11
![一道关于集合的数学题再一次国际学术会议上,k个科学家共使用p种不同的语言,如果任何两个科学家都至少使用一种共同的语言,但没有任何两位科学家使用的语言完全相同,求证:k≥2^(p-1)注](/uploads/image/z/3002682-66-2.jpg?t=%E4%B8%80%E9%81%93%E5%85%B3%E4%BA%8E%E9%9B%86%E5%90%88%E7%9A%84%E6%95%B0%E5%AD%A6%E9%A2%98%E5%86%8D%E4%B8%80%E6%AC%A1%E5%9B%BD%E9%99%85%E5%AD%A6%E6%9C%AF%E4%BC%9A%E8%AE%AE%E4%B8%8A%2Ck%E4%B8%AA%E7%A7%91%E5%AD%A6%E5%AE%B6%E5%85%B1%E4%BD%BF%E7%94%A8p%E7%A7%8D%E4%B8%8D%E5%90%8C%E7%9A%84%E8%AF%AD%E8%A8%80%2C%E5%A6%82%E6%9E%9C%E4%BB%BB%E4%BD%95%E4%B8%A4%E4%B8%AA%E7%A7%91%E5%AD%A6%E5%AE%B6%E9%83%BD%E8%87%B3%E5%B0%91%E4%BD%BF%E7%94%A8%E4%B8%80%E7%A7%8D%E5%85%B1%E5%90%8C%E7%9A%84%E8%AF%AD%E8%A8%80%2C%E4%BD%86%E6%B2%A1%E6%9C%89%E4%BB%BB%E4%BD%95%E4%B8%A4%E4%BD%8D%E7%A7%91%E5%AD%A6%E5%AE%B6%E4%BD%BF%E7%94%A8%E7%9A%84%E8%AF%AD%E8%A8%80%E5%AE%8C%E5%85%A8%E7%9B%B8%E5%90%8C%2C%E6%B1%82%E8%AF%81%EF%BC%9Ak%E2%89%A52%5E%28p-1%29%E6%B3%A8)
一道关于集合的数学题再一次国际学术会议上,k个科学家共使用p种不同的语言,如果任何两个科学家都至少使用一种共同的语言,但没有任何两位科学家使用的语言完全相同,求证:k≥2^(p-1)注
一道关于集合的数学题
再一次国际学术会议上,k个科学家共使用p种不同的语言,如果任何两个科学家都至少使用一种共同的语言,但没有任何两位科学家使用的语言完全相同,求证:k≥2^(p-1)
注:请写出完整的过程,并写出每一步是怎么得出的
一道关于集合的数学题再一次国际学术会议上,k个科学家共使用p种不同的语言,如果任何两个科学家都至少使用一种共同的语言,但没有任何两位科学家使用的语言完全相同,求证:k≥2^(p-1)注
设p=3,用1,2,3表示3种语言,此时取k=3,3个科学家使用语言为{1},{1,2},{1,2,3},满足题中条件:任何两个科学家都至少使用一种共同的语言,没有任何两位科学家使用的语言完全相同,但k≥4=2^(3-1)不成立,
设p=4,用1,2,3,4表示4种语言,此时取k=4,4个科学家使用语言为{1},{1,2},{1,2,3},{1,2,3,4},同样满足题中条件,但k≥8=2^(4-1)不成立.
应将结论改为k≤2^(p-1)
在一次国际学术会议上,k个科学家共使用p种不同的语言,如果任何两个科学家都至少使用一种共同的语言,但没有任何两个科学家使用的语言完全相同,求证:k≤2^(p-1)
将P种不同的语言构成的集合记为A={1,2,3,...,P},每个科学家所掌握的语言是集合A的一个子集,没有任何两位科学家使用的语言完全相同,故所有子集两两不同,又由于任何两个科学家都至少使用一种共同的语言,即这些子集的交不空(或相交),该题化为如下组合问题:
P元集有K个互不相同的两两相交的子集,则k≤2^(p-1).
证明 设P元集为A={1,2,3,...,P},A1,A2,…,Ak是集合A的K个互不相同的两两相交的子集,由A1,A2,…,Ak互不相同,故它们相应的补集B1,B2,…,Bk也互不相同,如果存在1≤i,j≤k,i≠j,有Ai=Bj,由于Bj是Aj的补集,故Bj和Aj没有共同元素,即Ai和Aj没有共同元素,这与题设矛盾,故对任意1≤i,j≤k,i≠j,Ai≠Bj,这说明A1,A2,…,Ak,B1,B2,…,Bk这2k个集合两两不同且均是A的子集,但A的子集共有2^P个,故2k≤2^P,k≤2^(p-1).
将P种不同的语言记为M={M1,M2,M3,...MP}
则M的子集有2^P个
每个科学家所掌握的语言是M的一个子集
因为没有任何两位科学家使用的语言完全相同
所以子集两两不等
又由于任何两个科学家都至少使用一种共同的语言
则任何两个子集都不是互补子集
所以这K个语言子集不能超过M的子集数2^P的一半
即k大于或等于2^(p-1)
全部展开
将P种不同的语言记为M={M1,M2,M3,...MP}
则M的子集有2^P个
每个科学家所掌握的语言是M的一个子集
因为没有任何两位科学家使用的语言完全相同
所以子集两两不等
又由于任何两个科学家都至少使用一种共同的语言
则任何两个子集都不是互补子集
所以这K个语言子集不能超过M的子集数2^P的一半
即k大于或等于2^(p-1)
或参考http://iask.sina.com.cn/b/5359786.html
收起