Find the number of subsets $A$ of $S= \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}$ such that: $x\in A\wedge 2x\in S\implies 2x \in A$

Question

Find number of subsets $A$ of $S= \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}$ such that: $$x\in A\;\;\;\wedge \;\;\;2x\in S\;\;\;\implies \;\;\;2x \in A$$

Solution: Let $A= X\cup Y$ where $X \subseteq \{1,2,3,4,5\}$ and $Y\subseteq \{6,7,8,9,10\}$.

• If $|X|= 0$ then we have $32$ possibilities for $Y$ and the same for $A$.
• If $|X| = 1$ (so we have $3$ choises for $X$) then we have $|Y|\geq 1$ so we have $3\times 2^4 = 48$ possibilities for $A$;
• If $|X| = 2$ then if $X= \{2,4\}$ we have $16$ choises for $Y$ else we have $|Y|\geq 2$ so we have ${3\choose 2}\times 2^3= 24$ possibilities for $A$ so in total in this case $40$ posibilities;
• If $|X| = 3$ then we have $16+2\cdot 8 + 4= 36$ possibilities for $A$.
• If $|X| = 4$ then we have $2\cdot 8 +4= 20$ possibilities for $A$;
• If $|X| = 5$ then we have $|Y|\geq 3$ so we have $1\times 2^2=4 $ possibilities for $A$.

So in total $\boxed{180}$ possibilities.

Any shorter solution?

Answer 1

Partition $S$ into sets that include all the numbers forced to be in $A$ if the least one is, so $\{1,2,4,8\},\{3,6\},\{5,10\},\{7\},\{9\}$. For each subset of $k$ elements you have $k+1$ choices for how many elements to include in $A$ because once you include one you must include the larger elements, but you can include none. $5 \cdot 3 \cdot 3 \cdot 2 \cdot 2=180$