Cardinality of a subset of $A$ without elements $x = 2y$

Question

Given set $A = \{1, 2, 3, ..., 256\}$, find the cardinality of the biggest subset $A'$ of $A$ such that elements $x, y$ of the form $x = 2y$ do not belong to $A'$

Attempt

Split $A$ into odd and even integers.

$128$ odd integers belong in $A'$. Even integers which are divisible by $2$ but not by $4$ are out.

Then take $32$ integers divisible by $4$ but not by $8$. They belong in $A'$. Those divisible by $8$ but not by $16$ are out.

Same with $8$ integers divisible by $16$ but not by $32$

Same with $2$ integers divisible by $64$ but not by $128$

Same with $1$ integer divisible by $256$

Answer: $128 + 32 + 8 + 2 + 1 = 171$.

How do I prove formally this is indeed the max cardinality?

Answer 1

Let: $$A_1 = \{129,130,...,256\} \implies |A_1| =128$$ $$A_2 = \{33,34...,64\} \implies |A_2| =32$$ $$A_3 = \{9,10,...,16\} \implies |A_3| =8$$ $$A_4 = \{1,3,4\} \implies |A_4| =3$$

---

Let $$B_1 = \{65,66,...,128\} $$ $$B_2 = \{17,18,....,32\} $$ $$B_3 = \{5,6,7,8\} $$ $$B_4 = \{2\} $$ and let $C_i = A_i \cup B_i$.

Lemma: From set $C_1$ we can take at most 128 elements in $A'$.

Proof: Since we have 64 pairs $(64+i,128+2i)$ for $i=1,..64$, we can take at most one element from each pair in $A'$ so we have at most 64 elements form that pairs in $A'$ and we have at most 64 elements which are left in $C_1$. So we can take at most 128 elements form $C_1$ in to $A'$.

Simillary lemma we can do for other $C_i$...

So $|A'|\leq 171$ and this number is achieved with following example: $$A' = A_1\cup A_2\cup A_3\cup A_4$$

Answer 2

Consider the partition $$A = \{ 1, 2 \} \cup \{ 3, 6 \} \cup \{ 4, 8 \} \cup \{ 5, 10 \} \cup \cdots \cup \{ 127, 254 \} \cup \{ 129 \} \cup \{ 131 \} \cup \cdots \cup \{ 255 \} \cup \{ 256 \}.$$ More explicitly, $$A = \left(\bigcup_{1 \le n < 128, 2 \mid \operatorname{ord}_2(n)} \{ n, 2n \}\right) \cup \left(\bigcup_{128 < n \le 256, 2 \mid \operatorname{ord}_2(n)} \{ n \} \right).$$ Now, any set $A'$ satisfying the required condition can have at most one element in common with each part of this partition. However, the partition has exactly 171 parts - which can easily be seen from the fact that your candidate $A'$ has exactly one element in each part of the partition.