题目

请问从1、2、3、4、...、2008这2008 个正整数中
请问从1,2,3,…2008这2008个正整数中至少可以取出多少个数,使得取出的数中任两数之和不能被除数这两个数之差整除?

提问时间：2021-04-01

答案

可以取出670个数.
显然,1到2008中
被3除余1的有1、4、……2008共670个
被3除余2的有2、5、……2006共669个
被3除余0的有3、6、……2007共669个
那么取所有被3除余1的数,他们之中任意两个数的和被3除余2,差被3整除,和、差必不能整除.最多能取到此组670个数.
此时无论再取某3K+P,P≠1的数,都有组中对应的3K+1使得
3K+P+3K+1 = 6K + P + 1
| 3K + P - 3K - 1 | = |P - 1| = 1
6K + P + 1 必被1整除.