Cardinality of a subset of $A$ without elements $x = 2y$ 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?
 A: 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$$
A: 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.
