来个难点的初中数学竞赛题黑板上写有1,2,...,2013这2013个数,某人擦去黑板上的任意n 个数,要使得剩下的数中至少有两个数的和是2 的幂次,请问:n 最大是多少?根据部分网友思路梳理一下，供探

来个难点的初中数学竞赛题黑板上写有1,2,...,2013这2013个数,某人擦去黑板上的任意n 个数,要使得剩下的数中至少有两个数的和是2 的幂次,请问:n 最大是多少?根据部分网友思路梳理一下，供探
来个难点的初中数学竞赛题
黑板上写有1,2,...,2013这2013个数,某人擦去黑板上的任意n 个数,要使得剩下的数中至少有两个数的和是2 的幂次,请问:n 最大是多少?
根据部分网友思路梳理一下，供探讨：
个人觉得思路再换一个方向会更简单，
　（1）比如考虑1-2^n个数里面，只需保留后面这一系列数{2^(n-1)，2^(n-1)+1，2^(n-1)+2，...2^n}（共2^(n-1)+1个数），这后面一半数是可能共存的最多个数的数字，使得任何两个数字之和不为2的幂次。于是假设f(m)表示1-m个数字里面可能存在的最多的数字个数的话，则f(2^n)=2^(n-1)+1；
　（2）考虑1-2013的情况，此时应该从大数开始考虑取数，因为从1开始取的话情况会太复杂。首先可以全部选取1024-2013之间的数字（共989+1=990个），此时从35至1023之间任何数字都不能选取，但是1-34之间还是可以再选取数字的，由（1）可知f(32)=17，并且33,34是肯定可以选取的。所以最多存在的数字和是990+17+2=1009个。也就是说如果多于或等于1010个数字的话，就肯定存在一种组合方式，其中有两个数字和为2的幂次，从而n最大为2013-1010=1003。
　这个答案也和华杯赛的最后标准答案是一致的。

来个难点的初中数学竞赛题黑板上写有1,2,...,2013这2013个数,某人擦去黑板上的任意n 个数,要使得剩下的数中至少有两个数的和是2 的幂次,请问:n 最大是多少?根据部分网友思路梳理一下，供探
n有最大值,换言之n+1就存在一种擦去方式使得任意两个数之和均不是2的幂次.那么也就是求n+1最小值使得存在一种方式擦去n+1个数让剩余数没有一对数的和为2的幂次,那么满足题设的剩余数自然就有最大值m=2013-（n+1）.
也就是说要考虑构造出一个剩余方式使得包含的剩余数最多.
由于2013范围内数和最多到4025,所以只考虑2幂次最多为2048.
显然和为4有1种组合方式（1+3）,8有3种组合方式（1+7；2+6；3+5）,16有7种组合方式（略）……,1024有511种组合方式；2048有35+2013,……,1023+1025共989种组合方式.
下面分别考虑4到2048,对每个幂次都不存在两个数和来构造最多剩余数：
4来说,1与3只能取一个,比如说取3；
8来说,3种组合方式中含3的那一组无效,剩余两组中各取其一（1+7那组只能取7,2+5那组随意）,比如说7与2；
16来说,7种组合方式中含2.3.7的三组无效,剩余4组中各取其一（其中3组只能有一种取法,4+12那组随意）；
……
2048来说,989种组合方式中有511组无效,剩余478组各任取其一（其中477组只能有一种取法,512+1536那组随意）,这里需要特别注意：1024是显然可以存在的,他没有任何数可以配对.
Ps：取法的随意性就算用初等方法也容易验证,也比较好想明白.由于这个题没有问擦去方式的多少种,因此本题求解与取法的随意性没有一点关系,但是考虑到竞赛本来就是锻炼思维,顺带提提.
按照我的取法规则,显然取出来的1+2+4+……+256+478+1=990数任意两个数之和都不会是2的幂次,且任意添加一个数均能凑成2幂次.所以对任意擦去方法,最多剩余990个数中任意两个数都不和为2的幂次.换言之剩余991个数就至少存在两个数之和为2幂次.
因此最多擦去2013-991=1022个.

应该是2011

1.假设和是2^11=2048（2^12=4096>2012+2013），
那么就有35+2013，36+2012，......，1023+1025共989种相加可能，
那么最多只能擦去988个数
（根据抽屉原理，989种相加可能中至少有一种可能两个数都未被擦去）；
2.假设和是2^10=1024，
那么就有1+1023，2+1022，......，511+...

全部展开

1.假设和是2^11=2048（2^12=4096>2012+2013），
那么就有35+2013，36+2012，......，1023+1025共989种相加可能，
那么最多只能擦去988个数
（根据抽屉原理，989种相加可能中至少有一种可能两个数都未被擦去）；
2.假设和是2^10=1024，
那么就有1+1023，2+1022，......，511+513共511种相加可能，
那么最多只能擦去510个数；
3.假设和是2^9=512，
那么就有1+511，2+510，......，255+257共511种相加可能，
那么最多只能擦去254个数；
......
设从1，2，...，2013中任意取出m个数，使得取出的数中至少有两个数的和是2 的幂次，
则m(min)=2013-n(max)，
构造一个取出的集合，使得取出的数中不存在两个数的和是2 的幂次，
取2013舍35，取2012舍36，...，取1025舍1023，取1024，
取34舍30，取33舍31，取32，
取29舍3，取28舍4，...，取17舍15，取16，
取2，取1，（把这个取法称为A取法）
A取法覆盖了1到2013，取出了1009个数，
这1009个数中不存在两个数的和是2 的幂次，
那么m(min)≥1010，n(max)≤1003，
A取法中取出1，2，16，32，1024时（共5次取数）没有舍去其他的数，
其他共1004次取数时每次舍去了另外一个数，
如果A取法是舍数最少的取法，
那么n(max)=1003。

收起

1. 在2013内的两个数最大为2013+2012=4025，由于2的幂次为4096，其达不到，故应该考虑2048和1024.本题属于夹挤法解决的。

2. 现在考虑2013，其与35的和为2048，这是可以擦去的任意数为34。以此类推，到1023+1025=2048.如果把2013一直到1025共989个数字擦掉，那么就没有2048的情况了。但还有其他情况，...

   全部展开

   1. 在2013内的两个数最大为2013+2012=4025，由于2的幂次为4096，其达不到，故应该考虑2048和1024.本题属于夹挤法解决的。

   2. 现在考虑2013，其与35的和为2048，这是可以擦去的任意数为34。以此类推，到1023+1025=2048.如果把2013一直到1025共989个数字擦掉，那么就没有2048的情况了。但还有其他情况，故先设下限为989.

   3. 如果把1到1021都擦掉，剩下的数没有可以达到2的幂次的了，故设上限为1021.此时只需不擦1021，其就可以达到2048，故结果应该为1到1020，答案为1020.

   收起

   ∵2^10＝1024, 2^11＝2048＞2013
   ∴ 10－2＝8
   n≥2013－8＝2005