8
$\begingroup$

Let $S = \{1, 2, \dotsc, 1000\}$, $T$ is a subset of $S$. For any $a, b\in T$ (can be the same), $a + b$ is not a power of $2$. Find the greatest possible value of $|T|$.

Notice that if $a+a=2^N=2a$, then $a$ must be a power of $2$ as well. Namely $2^{N-1}$. Hence we can't include any power of 2 in the set of $T$ as $a$ and $b$ could be the same.

That leaves us for $T=\{1,3,5,6,...,513,514,...,1000\}$. Now notice that if $1+b=2^N$, then $b=2^N-1$, which means every number such that it is one less than a power of $2$ can't be included inside, or $1$ could not be inside.

Similar for $3, 5, 6, \dotsc$ as a number with $1, 3, 5, \dotsc$ less than a power of $2$ is much more than a single number $1, 3, 5$ etc. Hence I think it would be more clever to exclude the single number $1, 3, 5, \dotsc$ (I don't know if it's right).

From here on I'm stuck and I have no idea.

$\endgroup$
  • 8
    $\begingroup$ I'm voting to close this question as off-topic because just like every other question of yours, you show no effort whatsoever in attempting to answer it on your own. Asking 'Can anyone help me with it?' is simply not enough. $\endgroup$ – barak manos Aug 9 '16 at 9:59
  • 3
    $\begingroup$ @barakmanos I'm sorry that my questions bother you to vote, but if I already know how to solve it, then I doesn't even need to put it onto here, right? :) $\endgroup$ – blastzit Aug 9 '16 at 10:42
  • 5
    $\begingroup$ Right, but if you don't know how to solve it, then it doesn't mean that you can dump it here and expect others to solve it for you without showing any attempt so solve it on your own, since this is not a 'do my homework for free' service. Please show the same amount of effort that you're expecting others to make for you. $\endgroup$ – barak manos Aug 9 '16 at 11:13
  • 1
    $\begingroup$ @barakmanos I did attempt to try it, but failed so I said "I have totally no idea how to do this". The level of the problem is way off my knowledge base, or what I think can be used to solve it. That's why I posted it and hopes that someone can give me a hint, or a way to solve it easily. $\endgroup$ – blastzit Aug 9 '16 at 11:18
  • 1
    $\begingroup$ BTW, I am not trying to discourage your from posting questions here, or to put you down in any other manner. I've personally answered (nicely IMO) one of your questions, which was closed pretty soon after you had posted it, for the exact same reason. And I'd hate to see my answer deleted along with your question. But it shows you that even if one chooses to make an effort and answer the question, your lack-of-effort eventually renders their work in vain... $\endgroup$ – barak manos Aug 9 '16 at 11:23
17
$\begingroup$

For any $n\in\mathbb N$, let $h(n)$ mean the distance from $n$ up to the next power of $2$ -- that is, in symbols, $$ h(n) = 2^{\lfloor 1+\log_2 n\rfloor} - n $$ It is easy to see that if $a+b$ is a power of $2$ and $a\le b$, then $a=h(b)$. Therefore, the condition of $T$ is equivalent to saying that $T$ does not contain both $b$ and $h(b)$ for any $b$, or in yet other words $T\cap h(T)=\varnothing$.

Let $S^*$ be $S\setminus h(S)$, the elements of $S$ that are not hit by $h$. These elements are "gratis" to add to $T$ in the sense that if $T_1$ satisfies the condition, then $$ T_2 = \bigl(T_1 \setminus h(S^*)\bigr) \cup S^* $$ will be another qualifying $T$, and in addition $T_2$ that has at least as many elements as $T_1$. Namely, each element of $h(S^*)$ that was in $T_1$ but is removed corresponds to at least one element of $S^*$ that is added.

Therefore, we can assume without loss of generality that a $T$ of maximal size contains $S^*$.

For $S=\{1,2,3,\ldots,1000\}$, we have $S^*=\{513,514,\ldots,1000\}$, so these $488$ elements are certainly in $T$. And $h(S^*)=\{24,25,\ldots,511\}$ so these elements cannot be in our $T$. Neither can $512$, of course, being a power of $2$ itself.

So all we have to do now is to supplement with as many elements of $S_2=\{1,2,3,\ldots,23\}$ as we can. But that's just a smaller instance of the problem we're already solving, so we can proceed recursively:

$$ S_2^* = \{17,18,\ldots,23\} \\ h(S_2^*) = \{9,10,\ldots,15\} \\ S_3 = \{1,2,\ldots,7\} $$ (ignoring $8$ which is a power of $2$) $$ S_3^* = \{5,6,7\} \\ h(S_3^*) = \{1,2,3\} $$ at which point we have exhausted the entire original $S$. Therefore, a $T$ with maximal size is $$ \{5,6,7,17,18,\ldots,22,23,513,514,\ldots,1000\}$$ with $$ 3+7+488 = 498 $$ elements.


This is not the only possible $T$ with $498$ elements, though. For example, $$ \{5,6,7,17,18,\ldots,22,23,24,513,514,\ldots,999\}$$ would also work.

$\endgroup$
5
$\begingroup$

According to the approach described by Henning Makholm if $S=\{1,2,\dots,n\}$ it seems that the maximum size of such set $T(n)$ is related to $[n]_2$ (the binary expansion of $n$). It should be $$|T(n)|=\frac{n-\mbox{number of runs in $[n]_2$}}{2}$$ For $n=1000$ then $[n]_2=1111101000$ and $$|T(1000)|=\frac{1000-4}{2}=498.$$ Is there any connection between Gray code and this problem?

$\endgroup$
  • $\begingroup$ The connection with coding theory would be much easier if we wanted numbers less than $8192$ or some other power of $2$. $\endgroup$ – Patrick Stevens Aug 9 '16 at 10:33
2
$\begingroup$

This is not a solution, but some random thought you might find usefull.

If $a + a = 2a$ is a power of two, then a must be a power of two.

For every $a \neq 1$ that is a power of two we can't include both $a+b$ and $a-b$, where $b$ is odd and $a > b$. Thus, a choice is to be made, and it feels like one should include $a-b$ and not $a+b$ since distance between powers of 2 grows but this needs to be proved.

Lastly, any even number a that is not a power of two is fine to include always.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.