- UID
- 16
- 帖子
- 590
|
4#
发表于 2012-12-10 22:07
本帖最后由 realnumber 于 2012-12-10 22:11 编辑
3.提案有p个,那么国家最多是$2^{p-1}$个,(我是先做实验,p=2,p=3,p=4后,猜的)
存在这样的情景,所有国家都含有1号提案,那么从余下的p-1个方案中挑不同的方案办法有$2^{p-1}$种.(自然这不是唯一的一个办法,可以试下p=3,或4就会发现)
以下证明大于等于$2^{p-1}+1$的国家数目是不可能的,
(1)若所有国家有1个公共提案,比如1号,那么余下的p-1个提案最多有$2^{p-1}$个选择.
(2)若所有的国家没有1个公共的提案,对于含有1号提案的国家不作变化,
对于不含1号提案的国家逐个做如下处理,把它的提案变为全体提案构成集合的补集,(每改变一个国家,考察任意两个国家,此时依然满足题中所给条件,如果变化前符合的话),经过如此处理,问题转化为(1) 的情景,完毕.
|
|