今天的题目是组合数学问题，是邻居家孩子问我的题目，据邻居说他自己想了一个多小时没想出来，还因此遭到了儿子的鄙视，简直受到了3000点暴击，为人父母可真不容易。
题目：在1到2019的所有自然数中，任意取出n个数，为保证其中定有一个数是另一个数的整数倍，n的最小值是多少？
这道题属于排列组合问题，学通这道排列组合题，到高考都够用了
如果你想思考一下，可以暂停滚屏，思考1分钟后，再继续。
思路分析：
这道题属于组合数学问题，要说明某个n是最小值，首先要构造出n-1个数不满足条件，接着要证明任意n个数都满足条件。
由于1到2019的所有自然数中，而2019/2=1009.5，故大于1009的1010自然数显然不满足，也就是说n一定大于1010，因此考虑n=1011是否满足条件。
先思考对于任意1011个数，是否一定有2个数的最大奇数因数相同；再考虑这2个数是否成整数倍关系；最后说明1010个数不满足条件。
步骤1：
先考虑第一个问题，在1到2019中的任意1011数中，是否一定有2个数的最大奇数因数相同？
1011个数共有1011个最大奇数因数，但1到2019中共有1010个奇数，把这1010个奇数看作鸽笼，把1011个最大奇数因数看作鸽子，则应该用鸽笼原理可得，一定有2个数的最大奇数因数相同。
步骤2：
再考虑第二个问题，对步骤1中得到的2个数，是否一定有一个是另一个的整数倍？
假设这两个数的最大奇数因数是p，则一定存在两个不同的自然数m和n，使这两个数分别是p*2^m和p*2^n。(注：2^n表示2的n次方。)
由于m和n存在大小关系，因此一定有一个数是另一个数的整数倍。
步骤3：
综合上述几个问题，
考虑原题目的答案。
综合步骤1和2的结论，
我们得到了n=1011时一定满足条件。
当n=1010时，
从1010到2019共有1010个自然数，
任意一个都不是另一个的整数倍，
故n=1010不满足条件。
所以n的最小值是1011。
你学会了吗？
有兴趣的读者可以考虑自行练习下面的扩展题
思考题：原题目改一个条件。
从1到20的所有奇数中，任意取出n个数，为保证其中定有一个数是另一个数的整数倍，n的最小值是多少？
联系客服
