题目

在1～2009个自然数中最多取出多少个数,使其中任意两个数的和不是两个数差的倍数?

提问时间：2020-11-25

答案

1到2009中,被3除
余1的有：1、4、7……、2008共670个
余2的有：2、5、8……、2009共670个
余0的有：3、6、9……、2007共669个
考虑取被3除余1的整组.组内的各数可表达为3A + 1、3B + 1…….
组内任取2个数
相加,和 = 3A + 1 + 3B + 1 = 3(A + B) + 2,和被3除余2
相减,差 = 3A + 1 - 3B - 1 = 3(A - B),差被3整除
显然和必然不是差的倍数.
此时,再从剩下的两组内任取一数N,则都能在第一组中找到一个数M,使得M与N相差1.（即|M - N| = 1）,则此时(M + N) 整除 (M - N),不符合题意.
综上,最多可取1到2009中被3除余1 （或余2）的一组共670个数,
可使其中任意两个数的和不是两个数差的倍数.