1至100中,最多能取出多少个数,使得选出的数中任意两个数的和都不能被3整除.

Question

1至100中,最多能取出多少个数,使得选出的数中任意两个数的和都不能被3整除.

Answer 1

您好!
把这一百个数分成3类
A类：模3余1的,就是{1,4,……,100},共34个
B类：模3余2的,就是{2,5,……,98},共33个
C类：模3余0的,就是{3,6,……,99},共33个
结论是最多取出35个数.证明如下：
首先,C类中不可能取出多于1个的数,否则这两个数之和必为3的倍数
其次,不能同时存在A类和B类的数,否则他们之和也是3的倍数
所以可以取的总数一定≤max{A的个数,B的个数}+1（C类的一个）=35
接下来,再构造出35个数即可.
构造很容易,就是A类的34个再加C类的任意一个就可以了.
这样任何两个数之和都不是3的倍数.
如果认为讲解不够清楚,请追问.如果满意,请采纳,谢谢!
祝：学习进步!