数学竞答 {1，2，3，……，100}，所有子集中，有些子集满足每个数都不是另一个数的2倍，求这

Question

数学竞答 {1，2，3，……，100}，所有子集中，有些子集满足每个数都不是另一个数的2倍，求这些子集 中元素最多是多少

Answer 1

把这100个元素分成如下几组：
第1组：1、2、4、8、16、32、64
第2组：3、6、12、24、48、96
第3组：5、10、20、40、80
第4组：7、14、28、56
第5组：9、18、36、72
第6组：11、22、44、88
第7组：13、26、52
第8组：15、30、60
第9组：17、34、68
第10组：19、38、76
第11组：21、42、84
第12组：23、46、92
第13组：25、50、100
第14组：27、54
第15组：29、58
第16组：31、62
第17组：33、66
第18组：35、70
第19组：37、74
第20组：39、78
第21组：41、82
第22组：43、86
第23组：45、90
第24组：47、94
第25组：49、98
第26组：51、53、…、97、99
前25组中，相邻两个数的后一个数恰好是前一个数的两倍，第26组是从51至99这25个奇数
要使子集中不存在某两个数之间存在两倍关系，第1组中最多可取四个数，如：1、4、16、64；
第2、3组中最多可取3个数，如第2组中可取：3、12、48；
第4——13组中最多都可取2个数，如第7组中可取：13、52；

第14——25组中最多都可取1个数，如第14组中可取：27；
第26组中所有的数都可以取。
因此，要使子集中每个数都不是另一个数的2倍，子集中的元素最多可以有：
4＋3×2＋2×10＋1×12＋25＝67个追问

不对。

太烦杂

追答

或者：

第一组：1、3、5、…、97、99，共50个奇数；
第二组：1×2、3×2、5×2、…、49×2，共25个数；
第三组：1×4、3×4、5×4、…、25×4，共13个数；
第四组：1×8、3×8、5×8、…、11×8，共6个数；
第五组：1×16、3×16、5×16，共3个数；
第六组：1×32、3×32，共2个数；
第七组：1×64，只有一个数
可见，相邻两组的数不能取，故子集中元素最多的是选第一、三、五、七组，共有50＋13＋3＋1＝67个元素

Answer 2

如果一个偶数不是4的倍数。那么我宁愿选这个偶数/2所得的奇数。为什么？
有7,14,宁愿选7,因为选14了之后，就一定不能选7，而选7，还可以选28.选14之后就不能28和7了。

所以选奇数是最优的法则。
所以，首先选上{1,3,5,7,...,99} 50个。

好了，刚说了，不是4的倍数的偶数不能选。但还可以选是4的倍数的偶数。
有多少个？
有{4,8,...,96,100} 把4这个因子提出来，变成了4{1,2,...,24,25}
现在又需要在{1,2,...,25}中挑选，同样刚才的程序，宁愿选奇数。
所以先选了{1,3,...,25} 共 13个。

剩下的8的倍数不能选。所以要选16的倍数。
于是还有{16,32,...,96} 抽出因子16{1,2,...,6}
同样选奇数，{1,3,5}共3个。

剩下32的倍数不能选，选64的倍数。就1个。

所以总共有50+13+3+1=67个。

上面是一种取法，以下来个最多是67的严格证明。
令A1=｛51，52，…，100｝，A2=｛26，27，…，50｝，A3=｛13，14，…，25｝，A4=（7，8，9，10，11，12），A5=（4，5，6｝，A6={2，3}，A7={1}．
现在知道集合B满足"每个数都不是另一个数的2倍"条件
因此|B∩A2|＋|B∩A1|≤50． 因为A2的两倍在A1,。
同样|B∩A4|＋|B∩A3|≤13，因为A4的两倍在A3
|B∩A6|＋|B∩A5|≤3．因为A6的两倍在A5
|B∩A7|<=1
∵B∈{1,2,3,,,100}=A1∪A2∪A3∪A4∪A5∪A6∪A7
∴|B|= B∩{1,2,3,,,100} = B∩（A1∪A2∪A3∪A4∪A5∪A6∪A7）
=|B∩A2|＋|B∩A1|+|B∩A4|＋|B∩A3|+|B∩A6|＋|B∩A5|+|B∩A7|<=50+13+3+1=67
可见B的元素个数最多是67.

Answer 3

应该是63吧，感觉是...
所有奇数共有50个，它们的约数中没有2，自然不会出现谁是谁的2倍，所以先全部填入。
然后考虑剩下的偶数，将它们除以2，然后就会得到25个奇数，和25个偶数，因为奇数已经填入了，所以将商是奇数的排除，这样得到25个新的数进行考虑。
分别是4,8,12,16,20，24,28,32,36,40,44,48,52,56,60,64,68,72,76,80,84,88,92,96,100
从中选出互不为2倍的最多的组合是4,12,16,20,28,36,44,48,52,60,64,68,76,80,84,92,100
这样结果就是13+50=63，这应该是最多的组合了吧...追问

漏了

追答

我2了，不是13，是17

追问

对了

Answer 4

不是另一个数的二倍 明显都是奇数 算1 一共追答

49个元素

追问

不对

全部奇数都50个了。怎么才49个

追答

1不算

追问

算

2不算

追答

1是所有数的质数

追问

看题目

追答

2是偶数了

追问

要我教你算吗？

追答

好吧 高中知识忘没了

追问

。。。。。。

100内奇数都满足

追答

嗯

追问

所以先得50个

追答

对啊

追问

然后把这些奇数都×2

就得25个偶数不符合

追答

你赢了

追问

剩25个偶数需要排除

剩下的偶数为 4，8，12，16……96

满足an＝4n的数列。

追答

你赢了 不和你玩了

高几了

追问

开学高三

明年就高考了

追答

能考多少分？

追问

……我成绩很一般的。别看好我

追答

高三一年很快的 珍惜时间吧！ 拜拜 我英语还算不错 不会问我啊

高考130呢

追问

嗯

谢谢

可以加qq吗？这里觉得联系不方便

追答

496304694

不总上qq的

追问

那怎样才能联系你呢？

学长╱姐

追答

长

追问

嗯。

给qq吧。或者email也行

我文理都过关。呵呵。

追答

将及格？

4963 04 694qq

看到？

追问

qq没看到

追答

我发了啊

追问

我这个百度知道有问题的

追答

4 9 6 3 0 4 6 9 4 q q

追问

这样。我给我的，你加我好吗。

看到了

我现在就加

追答

没有啊

追问

学长。我想考南大

追答

我发了照片