Question

一道离散数学题从{1,2,...,200}中选出100个数,其中一个小于16,求证在选出的100个数中存在两个数,他们其

Answer 1

假设命题成立.

首先将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