Question

【題目】有個人聚會，已知：

（1）每個人至少同其中個人互相認識；

（2）對于其中任意個人，或者其中有2人相識，或者余下的人中有2人相識，證明：這個人中必有3人兩兩相識.

Answer 1

【答案】見解析

【解析】

假設這個人中無3人彼此相識.

設，是這個人中相識的2人，由反證假設可推出余下的個人中，無1人與，皆相識.因此，至少有個不同的人，其中每個人或同相識，或同相識.

當為偶數時，由上述討論可知，這個人中恰有一半人與相識，而另一半人則與相識.于是，由題設可推出在某一半人中必含2個相識的人.這與反證假設矛盾.

當為奇數時，.若這幾個人中每人與或相識，則與上述討論類似，可推出矛盾.

不然，存在，他同，皆不相識，于是，個人中除之外的個人中必有一半與相識，另一半與相識.所有相識的人互不相識，所有與相識的人也互不相識.

假設有個人同，皆相識，個人同，皆相識，不難由題設推出，并且這個人構成與相識的人的全部.因而，.不妨設，由可知.

設同，皆相識，與同，皆相識（如圖），由于個人中同相識的人至少為個，他們中除外同都相識，故必與，之一相識.不妨設與相識，則，與是彼此相識的人，此與反證假設相矛盾.因此命題為真.