数学竞赛求指导考虑集合{1,2,...2000}的满足下述条件的子集a,a中没有一个数是另一个数的五倍,求a元素个数最大
3个回答

首先我们可以构造一个集合Tn,尽可能的使他中元素最多（设其中元素按小到大排列,第n个元素的值为sn） 易 知满足2000≥sn>400的所有数都可以（400的5倍为200）又可知满足80≥sn>16的数也都可以（16的5倍为80,80的5倍为400）又有sn=1、2、3,也满足所以Tn={sn│sn=1,2,3或80≥sn>16或2000≥sn>400}共有1667个数,所以a元素个数最大应该≥1667下面证1667为最大（反证法）假设存在一个集合a使得a中集合大于Tn中的元素个数即≥1668首先a中不含以下数对（1,5）、（2,10）、（3、15）、（k,5k）、（t、5t）4≤k≤16,81≤t≤400一共336个数对而a中出去672个数后还剩下1328个数,集合a元素个数≥1668,则应该从336个数对中选340个数则一定存在一个数是另一个数的五倍.故假设不成立即最大为1667

相关问题