在一次集会上,其中必有两个人,他们认识的人数一样多.试证明之(这里甲认识乙,则乙也认识甲)
问题描述：
在一次集会上,其中必有两个人,他们认识的人数一样多.试证明之(这里甲认识乙,则乙也认识甲)
用抽屉原理证明
答
设这次集会共n个人.如果有一个人谁也不认识那么每个人至多认识n-2个人,则n个人认识的人数至多有n-1种可能:0,1,2,…,n-2.所以其中必有两个人认识的人数相同.如果每个人都至少认识一个人,则n个人认识的人数至多有n-1种可能:1,2,…,n-1,所以其中必有两个人认识的人数相同.