一道组合数学题求证:从1,2,…,200中任取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.

来源:学生作业帮助网 编辑:六六作业网 时间:2024/11/28 03:27:14
一道组合数学题求证:从1,2,…,200中任取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.一道组合数学题求证:从1,2,…,200中任取100个整数,其中之一小于16,那么必有

一道组合数学题求证:从1,2,…,200中任取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.
一道组合数学题
求证:从1,2,…,200中任取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.

一道组合数学题求证:从1,2,…,200中任取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.
要用到鸽巢原理(抽屉原理):
如果n+1个物体被放进n个盒子,那么至少有一个盒子包含两个或更多的物体.
假设命题成立.
首先将1-200按照连续除以2,直到不能被2整除的结果分为100组,即:
1,1*2,1*4,...
3,3*2,3*4,...
...
197
199
每一组中的数都能互相整除.所以如果想取100个不能互相整除的数,只能每个组取一个.设取的数为
a1 = 1*2^k1
a3 = 3*2^k3
a5 = 5*2^k5
...
a199 = 199*2^k199
设那个小于16的数为ai=i*2^ki,i>0.
则a3i=3i*2^k3i,于是k3i

也就是有至少一个要从1到15里选,我们这样看,一个能被另一个整除意味着一个是另外一个的倍数,怎么证呢?反证法
反设100个里面任意两个a,b都不满足a=bc,c是整数,那么很明显,1 2是不能用的 然后