组合专题:超难组合数学㈡ 1.在参观团的任意四个人中,有一个人认识其他三个人。证明:在任何四个团员中,总可以找到一个人,他认识所有的团员。 2.某个团体有n个成员(n≥5),并且有n+1个三人委员会,其中没有两个委员会有完全相同的成员。证明:有两个委员会恰好有一个成员相同。 3.有一个十人的会,在他们当中任何三人至少有两人互不相识。证明在这会中有四人,他们没一人认识四人中的其他人。 4.大厅中聚会了100个客人,他们中每个都与其余客人中至少67人相识。证明:这些客人中一定可以找到4个客人,他们中任何两人都彼此相识。 1 测 试 题 四个人的聚会,每人各带了2件礼品,分赠给其余三个人中的二人,请你证明,至少有两对人,每对人是互赠过礼品的。 答案与解析 【分析】将四个人看为4个点ABCD 如果某个人赠送另一个礼品,则在这两个点之间了连一条边 (如果互增礼品,则在这两点之间连两条边) 每个人赠送两件礼品 故总边数为4×2=8 若四个人两两之间至多连一条边,至多连(4×3)÷2=6 又因为两个点之间至多连两条边 所以必定又两组点之间连8-6=2条边 所以命题成立 2 本文来源:https://www.wddqw.com/doc/76c33e238662caaedd3383c4bb4cf7ec4afeb6a0.html