Question

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

Answer 1

【答案】8

【解析】

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

只需證明：.

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

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

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

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

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

綜上，的最大值為8.