【算法面试题】从1-200中任意选出101个自然数,其中一个数必是另一个数的整数倍

【爱奇艺】现有1-200之间的正整数，假设从中任意抽取101个数，试证明其中必然有一个数可以被另外一个数整除？

证明：

任意整数都可以写成(2^a)*b的形式,其中a>=0，b为奇数.

把这200个数分类如下：

以上共分为100类，即100个抽屉。显然在同一类中的数若不少于两个，那么这类中的任意两个数都有倍数关系。从中任取101个数，根据抽屉原理，一定至少有两个数取自同一类，因此其中一个数是另一个数的倍数。