作业帮证明：从1,2,…,200个数中取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.可能要用到鸽巢原理麻烦帮证明一下上面的命题，不是让你叙述一下鸽巢原理，
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/02 14:41:01
证明：从1,2,…,200个数中取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.可能要用到鸽巢原理麻烦帮证明一下上面的命题，不是让你叙述一下鸽巢原理，
证明：从1,2,…,200个数中取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.
可能要用到鸽巢原理
麻烦帮证明一下上面的命题，不是让你叙述一下鸽巢原理，
证明：从1,2,…,200个数中取100个整数,其中之一小于16,那么必有两个数,一个能被另一个整除.可能要用到鸽巢原理麻烦帮证明一下上面的命题，不是让你叙述一下鸽巢原理，
假设命题成立.
首先将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
有n+1只鸽子进入n个笼子，那么必然有至少两只鸽子在同一个笼子中。
q1，q2，q3，……，qn是n个正整数，则 q1+q2+q3+……+qn-n+1 个物体放入n个盒子中，那么，或者第一个盒子中至少有q1个物，或者第二个盒子中至少 有q2个物体，或者第三个盒子中至少有q3个物体，……，或者第n个盒子中至少有qn个物 ...
全部展开
有n+1只鸽子进入n个笼子，那么必然有至少两只鸽子在同一个笼子中。
q1，q2，q3，……，qn是n个正整数，则 q1+q2+q3+……+qn-n+1 个物体放入n个盒子中，那么，或者第一个盒子中至少有q1个物，或者第二个盒子中至少 有q2个物体，或者第三个盒子中至少有q3个物体，……，或者第n个盒子中至少有qn个物 体。 我们通常提到的鸽巢原理的定义是这种严谨的定义的一个特例，也就是设qx=2（其中x为1，2，3，……，n），那么上面定义中的q1+q2+q3+……+qn-n+1就简化为n+1
收起