If we remove $\lfloor (2^n-2)/3 \rfloor$ from a set of $\{1,\dots,2^n\}$, there is still a pair of integers $a, b$ such that $a=2b$

Question

To count the maximum number of integers from $1\dots 2^n$ s.t. none of them is twice the other we can group them by their biggest odd divisor, i.e. represent each $m$ as $m=2^k (2c+1)$, so we can take at most $$\lfloor \frac{\log_2 \lfloor \frac{2^n}{2c+1} \rfloor + 1}{2} \rfloor$$ of them. The log part of this expression is the biggest $k$ such that $2^k(2c+1)$ is not bigger than $2^n$, and then floor of division by $2$ is used to count how many integers can be taken from a group (we can take every second starting from the first one). So to answer the question of how many integers we can take so that none of them is twice the other we just need to sum the expression over $c$. However, I fail to see where $\lfloor (2^n-2)/3 \rfloor$ comes from, which is supposed to be at least $1$ bigger than the sum. So my question is about how we can relate the sum of the expression above to $\lfloor (2^n-2)/3 \rfloor$ or how we can derive that $\lfloor (2^n-2)/3 \rfloor$ integers are sufficient using other methods.

Any help is appreciated.

Update. I found a way to count it it the other way. As I said, we need to take every second element in each group, so we need to take every $1$-st, $3$-rd, $5$-th, ..., and so on. Every $1$-st element is every odd integer, every $3$-rd element is every integer $2^2(2c+1)$. We can count each $(2l+1)$-th element as $2^n/2^{2l}-2^n/2^{2l+1}$ (which is the number of multiples of power of two minus number of multiples of the next power of two). Therefore, the maximum number of integers we can keep so that there is no $a=2b$ can be expressed as a sum $$2^n \sum_{k=0}^n \frac{(-1)^{k}}{2^k} = 2^n \left[\frac{1}{3}\left((-1)^n+2^{n+1}\right)\right]$$.

To get the expression from the question we need to add one to this expression (so that there is $a=2b$ by pigeonhole) and subtract from $2^n$: $$2^n- 2^n \left[\frac{1}{3}\left((-1)^n+2^{n+1}\right)\right]-1=\frac{1}{3}\left(2^n+(-1)^{n+1}-3\right).$$

We can prove using casework on even and odd $n$ that the final expression is equivalent to $\lfloor (2^n-2)/3 \rfloor$ we have in the question.

Right now I know how to derive what I wanted, but my solution is heavily algebraic, and I feel like I started from the wrong direction: I tried to compute how many numbers we can keep so that there is no $a=2b$, but the question asks how many we can remove so that there is still $a=2b$. I mean the latter question can still be solved algebraically by changing sums a bit, but I'd like to find a simpler solution if there is any, one that doesn't require this summing argument. In my original question I asked for two possible directions to answer, and I worked myself through the first one, so I'll keep this as a question, not an answer in case there is an easier direct explanation to derive $\lfloor (2^n-2)/3 \rfloor$.

Answer 1

(I'm almost certain that this is a dupe, but can't seem to find one. If anyone can, please feel free to close.)

Fix $n$. Suppose we have removed enough pairs such that there's no $a = 2b$.

• The key observation, which OP made, is that for all odd $c$, if $ 2^k c \leq 2^n < 2^{k+1} c$, then
  • For odd $k$, we need to remove at least $ c_n = \frac{k-1}{2}$ elements. These have to be the "every second element".
  • For even $k$, we need to remove at least $c_n = \frac{k}{2}$ elements. These could either be "every second element" or "every second element starting from the first". The slight ambiguity here allows us some play, but also contributes to the difficulty of counting.
  • Explicit example if we "remove every second element" like in OP's construction: For $n = 3$, , we are removing $2, 6, 8$. For $n=4$, we are removing $2, 6, 8, 10, 14$.
• Let's construct such a set, described in terms of consecutive integers, which will make it easy to determine the number of integers that we removed, which is equal to $ \sum c_n$. As it turns out, the greedy algorithm starting from $2^n$ downwards works.
  • Keep $[2^n, 2^n-1, \ldots, 2^{n-1} + 1]$
  • Remove $[2^{n-1}, 2^{n-1} - 1 , \ldots, 2^{n-2} + 1]$
  • Keep $[2^{n-2} , 2^{n-2} - 1 , \ldots 2^{n-2} + 1$]
  • Remove ..., so on and so forth.
  • It is clear that this satisfies the above description for "remove every second element (possibly starting from the first if allowed)".
  • Explicit example: For $n=3$, we remove $4, 3, 1$. For $n=4$, we remove $8, 7, 6, 5, 2$.
• How many elements do we remove?
  • We are removing $\frac{ 2^n}{4} + \frac{2^n}{16} + \ldots + 1 = \lfloor \frac{2^n+1 } { 3}\rfloor $ numbers. (Be careful with the sum here. Some work required. In particular, the last term is always 1, corresponding to whether we remove $[2]$ or $[1]$.)
  • Explicit example: For $ n =3$, we remove $3 = \lfloor \frac{ 2^3 + 1 } { 3} \rfloor$ integers. For $n = 4$, we remove $ 5 = \lfloor \frac{ 2^4 + 1 } { 3 } \rfloor $ integers.
  • Thus $ \sum c_n = \lfloor \frac{ 2^n + 1 } { 3 } \rfloor $.

Corollary: If we remove strictly fewer than $ \lfloor \frac{ 2^n + 1 } { 3 } \rfloor $ integers (IE at most $\lfloor \frac{ 2^n -2 } { 3 } \rfloor$ integers), then there exists a $c$ such that we remove fewer than $c_n$ integers, hence we can find such an $ a = 2b$.

Answer 2

Let $m:= {\lfloor n/2 \rfloor} $. For each integer $ k \in [0,m]$, let $$A_k:= \bigl\{j \in [1,2^n]: \, j \equiv 0 \! \! \! \mod 2^{2k}, \; \, \text{but} \; \, j \ne 0 \! \! \! \mod 2^{2k+1} \bigr \} \,.$$ In particular, $A_0$ consists of the odd integers in $[1,2^n]$. Note that $A_k$ consists of integers in $[1,2^n]$ such that the first nonzero digit in their binary representation is the coefficient of $2^{2k}$. Thus $|A_k|=2^{n-2k-1}$ for $k<n/2$ and $|A_m|=1$ if $2|n$.

Let $A:=\cup_{k=0}^m A_K$. If $n$ is odd, then $$|A|=\sum_{k=0}^{m} 2^{n-2k-1} = \frac{ 2^{n+1}-1}{3} \,, $$ while for $n$ even, $$|A|=1+ \frac{ 2^{n+1}-2}{3} \,.$$ Clearly there is no $a \in A$ such that $2a \in A$.

On the other hand, $$\bigcup_{a \in A} \{a,2a\} \supset \{1,2,3,\dots,2^n\}\,.$$ Thus by the pigeonhole principle, if $S \subset \{1,2,3,\dots,2^n\}$ satisfies $|S|>|A|$, then $S$ must contain a pair $\{a,2a\}$ for some $a \in A$.