Problem

1-200中取出100个数{a_1,a_2,a_3\cdots a_{100}}
Prove:\\ \ if\ a_1<16 \ then\\\exists i,j(i,j\leq 100)\ s.t. a_i\mid a_j

sol

如果题目这样:

1-200中取出101个数{ a_1,a_2,a_3\cdots a_{100}}
Prove:\\ \exists i,j(i,j\leq100)\ s.t. a_i\mid a_j

考虑每个数都可以分解为2^k\cdot a(a\mod2\equiv1)的形式
以不同的a为鸽巢那么1~200中一共有100个奇数, 所以取101个必定会有2个在同一位置
也就是说它们是2^k倍的关系!

那么同理利用上述方法:
如果100个数, 一定在不同的鸽笼之中
假设not\ \exists i,j(i,j\leq100)\ s.t. a_i\mid a_j
– 设最小元a_1x

case1:

x\mod2\equiv 1
由于每一个”笼”都有且仅有一个数
显然会有一个奇数倍的关系, 如13 \cdot 15 = 195 \leq 200
矛盾.

case2:

x=2^n

考虑2^n, 3\cdot2^{n_1},9\cdot2^{n_2},27\cdot2^{n_3}
易得n_3n<4
所以0,1,2分配到4个笼中, 必定有一个数至少出现两次!
矛盾

case3:

x=b\cdot 2^n

考虑b\cdot2^n, b^2\cdot2^{n_1},b^3\cdot2^{n_2}(3\leq b \leq7)
易得n_2n<3
同理, 所以0,1分配到3个笼中, 必定有一个数至少出现两次!
矛盾

证毕!

发表评论

电子邮件地址不会被公开。 必填项已用*标注