今天的题目是组合数学问题,是邻居家孩子问我的题目,据邻居说他自己想了一个多小时没想出来,还因此遭到了儿子的鄙视,简直受到了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的最小值是多少?
联系客服