Question

【題目】有個(gè)人聚會(huì)，已知：

（1）每個(gè)人至少同其中個(gè)人互相認(rèn)識(shí)；

（2）對(duì)于其中任意個(gè)人，或者其中有2人相識(shí)，或者余下的人中有2人相識(shí)，證明：這個(gè)人中必有3人兩兩相識(shí).

Answer 1

【答案】見解析

【解析】

假設(shè)這個(gè)人中無(wú)3人彼此相識(shí).

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

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

當(dāng)為奇數(shù)時(shí)，.若這幾個(gè)人中每人與或相識(shí)，則與上述討論類似，可推出矛盾.

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

假設(shè)有個(gè)人同，皆相識(shí)，個(gè)人同，皆相識(shí)，不難由題設(shè)推出，并且這個(gè)人構(gòu)成與相識(shí)的人的全部.因而，.不妨設(shè)，由可知.

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