证明从2n个数中找n+1个数,这n+1个数中至少有两个数,其中一个能被另一个整除（用数学归纳法写过程

Question

证明从2n个数中找n+1个数,这n+1个数中至少有两个数,其中一个能被另一个整除（用数学归纳法写过程

Answer 1

首先假设n=1时,1和2,显然成立
然后假设n=k时成立
即从1到2k之间找k+1个数,至少有两个数其中一个能被另一个整除
然后当n=k+1时,也就是1到2k+2,中找到k+2个数,
这时候我们分情况来讨论
1.如果只从1到2k里取k+2个数,根据假设明显成立
2.从1到2k里取k+1个数,根据假设明显成立
3.从1到2k里取k个数,然后取2k+1和2k+2
那么接下来就要证明了.
首先任何一个数都可以写作一个奇数a*2^n的形式.
那么我们假设所取的k个数都是奇数,且没有一个数能被另一个数整除（如果不是这样,那么显然成立）
假设中1到2k里取k个奇数,这显然必须取到1,所以之前的假设成立.
得证.