Show that if 151 integers are selected from the set(1,2,3,…,300)there exist a,b In the selection such that la-bl = 1.(鴿籠原理)?
回答 (1)
2016-06-21 6:02 pm
✔ 最佳答案
把 1 至 300 分成 150 組, 使各組兩數相差 1 如下 : (1,2) , (3,4) , (5,6) , ... , (299,300). 由鴿籠原理, 所選 151 個數分佈在 150 組中必有兩數於同一組, 令該組為 (a,b) 即有 |a - b| = 1。
別解(反證法):
設所選 151 個數中找不到相差為 1 的兩數 , 則所選數中任 2 數之差不少於 2 , 於是所選 151 個數當中最大者不少於 1 + 2×150 = 301 > 300 矛盾! 故必存在兩數 a , b 滿足 |a - b| = 1。
收錄日期: 2021-04-30 21:36:40
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20160621071338AA0Vifu