题目

离散数学鸽巢原理中的一道证明题
那位帮我给个下面这道题的证明过程：在任何人数不少于2的人群中,至少有两个人在其中有同样多的熟人.

提问时间：2021-03-04

答案

例四一样的思路.
例4：某校校庆,来了n位校友,彼此认识的握手问候.请你证明无论什么情况,在这n个校友中至少有两人握手的次数一样多.
共有n位校友,每个人握手的次数最少是0次,即这个人与其他校友都没有握过手；最多有n-1次,即这个人与每位到会校友都握了手.然而,如果有一个校友握手的次数是0次,那么握手次数最多的不能多于n-2次；如果有一个校友握手的次数是n-1次,那么握手次数最少的不能少于1次.不管是前一种状态0、1、2、…、n-2,还是后一种状态1、2、3、…、n-1,握手次数都只有n-1种情况.把这n-1种情况看成n-1个抽屉,到会的n个校友每人按照其握手的次数归入相应的“抽屉”,根据抽屉原理,至少有两个人属于同一抽屉,则这两个人握手的次数一样多.