读书人

组合数学证明题,该如何处理

发布时间: 2012-03-18 13:55:38 作者: rapoo

组合数学证明题
证明对任意给定的52个整数,存在其中的两个数必定满足下列两个约束之一,1.两者和被100整除;2.两者差被100整除

[解决办法]
感觉不太好说清楚,但愿能让楼主能明白。
所有的数可以分成51个桶
(100*k), (k*100 + 1, k*100 + 99), (k*100 + 2, k*100 + 98), ...... , (k*100 + 50)
根据鸽巢原理,51个桶取52个数必有2个数在同一个桶里
而同一个桶里的数是满足 或者和被100整除,或者差被100整除
故题目得证
[解决办法]
可以这么考虑:
设者52个数为N(K) {0<=k<52}
令N(K)%100=n(k)
令任意两者的和为n(i)+n(j) ------条件1,
任意两者的差为n(i)-n(j) ------条件2,
把0~99分组 {0}, {1,99},{2,98} 。。。。。。{49,51}, {50} 共51组
如果有两个数是从以上同一个组中选出来的, 必然满足以上条件1或2为100的整数
因为有52个数, 必有两个数是同一组里面选出来的。

证毕!


探讨
证明对任意给定的52个整数,存在其中的两个数必定满足下列两个约束之一,1.两者和被100整除;2.两者差被100整除

[解决办法]
1、考察52个整数的末2位,必在0~99,如果有两个末2位相同,则这两个的差能被100整除。
2、假设52个整数的末2位两两不同,在考察它们末2位到50的距离,只有0~50种可能,至少有2个相同,即它们的和能被100整除。

读书人网 >软件架构设计

热点推荐