用鸽巢原理求证

题目

用鸽巢原理求证
5个孩子分76个糖果,求证3个孩子一共会分到45个或者更多的糖果.

答案

证法一：
用反证法.
假设任何三个孩子分到糖的和都小于45.
现设5个孩子分到糖的数量分别是
a,b,c,d,e
设k=a+b+c
易知k＜45
又有d+e=76-k
根据鸽巢原理,a,b,c三个数中至少有一个不小于k/3
无妨设a≥k/3
从而
a+d+e≥k/3+ 76-k=76-2k/3 ①
再据前面的假设,应有
a+d+e＜45 ②
综合①,②得
76-2k/3＜45
解之得
k＞46.5
这与前面的k＜45矛盾.证完.
证法二：
仍然用反证法.
假设任何三个孩子分到糖的和都小于45.
现设5个孩子分到糖的数量分别是
a,b,c,d,e
则从这5个数中任取3个,共有10种情况.
且有：
a+b+c＜45
a+b+d＜45
……
c+d+e＜45
把这10个式子相加,便有
6（a+b+c+d+e）＜45×10=450
从而a+b+c+d+e＜450/6=75
这与a+b+c+d+e=76矛盾.证完.