证明:从1,2,…,200个数中取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.

问题描述:

证明:从1,2,…,200个数中取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.
如题
从1,200 这200个数中任意取100个整数,其中至少有一个小于16。证明:这100个数中,必有两个数,一个能被另一个整除。
还看不懂题目的绕道吧

(200,100)(198,99)……(102,51)这50对
(50,25)(48,24)……(26,13)
()()
2,4,8,16,32,64,128
3,6,12,24,48,96,192
5,10,20,40,80,160
7,14,28,54,108
11,22,44,88,176
13,26,54,108
17,34,68,136
19,38,76,152
23,46,92,184
29,58,116
31,62,124
………………
89,178
97,194
101
103
107
…………
197
199
质数排完46组51+18+20+21=110个数每一组只能取一个
再排剩下54个大于100的数
200,100,50,25
198,99,33
…………
105,35
排法排法可以让小于100的数(还有36个)都排在其中,每组数只能取一个
其中至少有一个小于16,可以在这些组中去掉几组(把小于100的数分到其他组去)从而会在一组中取两个数,一个能被另一个整除