Question

来个难点的初中数学竞赛题

黑板上写有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。
　这个答案也和华杯赛的最后标准答案是一致的。

Answer 1

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个。

追问

如果是2048个数，你的思路是对的。但现在是2013个数，1024到2013间你的选法显然不成立，比如假设题目是1025个数，你并不知道1025这个数该取不该取，因为你不知道1023是否在前面已经取了。所以不能简单说1024到2013间有(989-511)种取法。

追答

你说得对，最开始是这样考虑的，后来不知不觉忽略了。应该改进。
理下思路，我错误的算法实际上是能取1+2047,2+2046，……，1023+1205。然后除去了之前所讲的1024组合中的511组。
但由于实际上只能从35+2013开始取，因此要考虑1.2.3.……34中之前被取了的数。在32的组合中显然知道1,2……32之中被取了15个数。所以现在只需要关注33与34两个数。而容易知道，若在之前取了1且2，那么33与34两个数能同时被取到。这也是使得剩余数最多的取法。
那么，在2048组合中，取得数应该是989-（511-17）+1=496个数。因此剩余数=1+2+4+……+256+496=1007。因此最多擦去2013-1008=1005

追问

　　个人觉得你的思路再换一个方向会更简单，梳理一下思路。放在问题里面，共探讨。

Answer 2

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.

Answer 3

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。

Answer 4

应该是2011

追问

答案错误，你题目没看懂

Answer 5

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

追问

答案错误，你题目没看懂