题目

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

提问时间：2020-11-07

答案

证明：假设每两人的公共朋友数均为奇数，则任一人的朋友数为偶数．
理由如下：
任取一人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为偶数．