Question

【題目】在名學(xué)生中，已知任意三人中有兩人互相認(rèn)識，任意四人中有兩人互相不認(rèn)識，則的最大值為______.

Answer 1

【答案】8

【解析】

當(dāng)時滿足要求.

只需證明：.

首先證明以下兩種情形不可能出現(xiàn).

（1）若某學(xué)生至少認(rèn)識6人，由拉姆塞定理，知這6人中存在3人要么互相認(rèn)識，要么3人互相不認(rèn)識.若為前者，則與這3人共有4人兩兩互相認(rèn)識，這與已知矛盾；若為后者，這與已知3人中有兩人互相認(rèn)識矛盾.

（2）若某學(xué)生至多認(rèn)識人，則剩下至少4人均與不認(rèn)識，從而，這4人兩兩認(rèn)識，與已知矛盾.

其次，當(dāng)時，（1）、（2）必有一種情形出現(xiàn)，這是不可能的.

當(dāng)時，要使（1）、（2）均不出現(xiàn)，只能每名學(xué)生恰認(rèn)識其他5人，于是，這9人產(chǎn)生的朋友對（互相認(rèn)識的—對人）的數(shù)目為，矛盾.

綜上，的最大值為8.