已知9个人,ABCDEFGHI,其中A和两个人握过手,BC各和四个人握过手,DEFG各和五个人握过手,HI各和六个人握过手,请证明这九个人一定可以找出三个人相互握过手

Question

已知9个人,A B C D E FGHI,其中A和两个人握过手,B C各和四个人握过手,D E F G各和五个人握过手,H I各和六个人握过手,请证明这九个人一定可以找出三个人相互握过手

Answer 1

反证法.
假设不存在一个3人组使得这3个人互相握过手.
若H和I握过手,则H和I各和其他7个人当中的5个人握过手,肯定可以找到一个共同的人X,则H、I、X互相握过手,矛盾.因此H、I没有握手.
同理可证D、E、F、G任意两人之间都没握过手.
于是得到D、E、F、G都和其他5个人握过手,这与A和两个人握过手矛盾.
因此假设不成立,九个人一定可以找出三个人相互握过手.