当前位置: > 设S是由2n个人组成的集合.求证:其中必定有两个人,他们的公共朋友的个数为偶数....
题目
设S是由2n个人组成的集合.求证:其中必定有两个人,他们的公共朋友的个数为偶数.

提问时间:2020-11-07

答案
证明:假设每两人的公共朋友数均为奇数,则任一人的朋友数为偶数.
理由如下:
任取一人A,有朋友F1,F2,…,Fk
用(AFi)表示A与Fi的公共朋友数,(AFi)为奇数.
∵每两个Fi之间增加一对朋友关系,AFi之和加2.
(比如,F1与F2是朋友,则AF1中会计算一次F2,AF2中会计算一次F1),
k
i=1
AFi
一定是偶数,
则k一定是偶数.
同理Fi朋友数一定也是偶数,且包括A.
由于k是偶数,
∴Fi朋友数之和也是偶数.
A在Fi朋友数之和中出现了k次,
剩余2n-1人如在Fi朋友数之和均出现奇数次的话,
Fi朋友数之和应是奇数,
所以剩余2n-1人中至少有一人B在Fi朋友数之和中出现偶数次,
这意味着A与B在Fi朋友中共同好友为偶数个,
即AB为偶数.
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
1,人们染上烟瘾,最终因吸烟使自己丧命.
版权所有 CopyRight © 2012-2019 超级试练试题库 All Rights Reserved.