作业帮来个难点的初中数学竞赛题
来源：学生作业帮 编辑：拍题作业网作业帮 分类：数学作业 时间：2024/05/01 14:07:34
来个难点的初中数学竞赛题
黑板上写有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 最大是多少?
根据部分网友思路梳理一下，供探讨：
个人觉得思路再换一个方向会更简单，
（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。
这个答案也和华杯赛的最后标准答案是一致的。
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
再问： 个人觉得你的思路再换一个方向会更简单，梳理一下思路。放在问题里面，共探讨。
也就是说要考虑构造出一个剩余方式使得包含的剩余数最多.
由于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
再问： 个人觉得你的思路再换一个方向会更简单，梳理一下思路。放在问题里面，共探讨。