Question

設(shè)S是由2n個人組成的集合．求證：其中必定有兩個人，他們的公共朋友的個數(shù)為偶數(shù)．

Answer 1

考點：進行簡單的演繹推理

專題：推理和證明

分析：假設(shè)每兩人的公共朋友數(shù)均為奇數(shù)，則任一人的朋友數(shù)為偶數(shù)．任取一人A，有朋友F₁，F(xiàn)₂，…，F(xiàn)_k，則F_i朋友數(shù)之和也是偶數(shù)，A在F_i朋友數(shù)之和中出現(xiàn)了k次，剩余2n-1人如在F_i朋友數(shù)之和均出現(xiàn)奇數(shù)次的話，F(xiàn)_i朋友數(shù)之和應(yīng)是奇數(shù)，所以剩余2n-1人中至少有一人B在F_i朋友數(shù)之和中出現(xiàn)偶數(shù)次．

解答： 證明：假設(shè)每兩人的公共朋友數(shù)均為奇數(shù)，則任一人的朋友數(shù)為偶數(shù)．
理由如下：
任取一人A，有朋友F₁，F(xiàn)₂，…，F(xiàn)_k，
用（AF_i）表示A與F_i的公共朋友數(shù)，（AF_i）為奇數(shù)．
∵每兩個F_i之間增加一對朋友關(guān)系，AF_i之和加2．
（比如，F(xiàn)₁與F₂是朋友，則AF₁中會計算一次F₂，AF₂中會計算一次F₁），
故

k

i=1

AFi一定是偶數(shù)，
則k一定是偶數(shù)．
同理F_i朋友數(shù)一定也是偶數(shù)，且包括A．
由于k是偶數(shù)，
∴F_i朋友數(shù)之和也是偶數(shù)．
A在F_i朋友數(shù)之和中出現(xiàn)了k次，
剩余2n-1人如在F_i朋友數(shù)之和均出現(xiàn)奇數(shù)次的話，
F_i朋友數(shù)之和應(yīng)是奇數(shù)，
所以剩余2n-1人中至少有一人B在F_i朋友數(shù)之和中出現(xiàn)偶數(shù)次，
這意味著A與B在F_i朋友中共同好友為偶數(shù)個，
即AB為偶數(shù)．

點評：本題考查的知識點是合情推理，本題比較抽象，解答過程中語言組織比較困難，不容易理解，屬于難題．