Question

设S是由2n个人组成的集合．求证：其中必定有两个人，他们的公共朋友的个数为偶数．

Answer 1

考点：进行简单的演绎推理

专题：推理和证明

分析：假设每两人的公共朋友数均为奇数，则任一人的朋友数为偶数．任取一人A，有朋友F₁，F₂，…，F_k，则F_i朋友数之和也是偶数，A在F_i朋友数之和中出现了k次，剩余2n-1人如在F_i朋友数之和均出现奇数次的话，F_i朋友数之和应是奇数，所以剩余2n-1人中至少有一人B在F_i朋友数之和中出现偶数次．

解答： 证明：假设每两人的公共朋友数均为奇数，则任一人的朋友数为偶数．
理由如下：
任取一人A，有朋友F₁，F₂，…，F_k，
用（AF_i）表示A与F_i的公共朋友数，（AF_i）为奇数．
∵每两个F_i之间增加一对朋友关系，AF_i之和加2．
（比如，F₁与F₂是朋友，则AF₁中会计算一次F₂，AF₂中会计算一次F₁），
故

k

i=1

AFi一定是偶数，
则k一定是偶数．
同理F_i朋友数一定也是偶数，且包括A．
由于k是偶数，
∴F_i朋友数之和也是偶数．
A在F_i朋友数之和中出现了k次，
剩余2n-1人如在F_i朋友数之和均出现奇数次的话，
F_i朋友数之和应是奇数，
所以剩余2n-1人中至少有一人B在F_i朋友数之和中出现偶数次，
这意味着A与B在F_i朋友中共同好友为偶数个，
即AB为偶数．

点评：本题考查的知识点是合情推理，本题比较抽象，解答过程中语言组织比较困难，不容易理解，属于难题．