I am struggling to understand the solutions to below question:
$p$ is a non-negative integer and $n=2^p$. Find the maximum number of elements in a subset $A$ that does not contain $2x∈ A$ for all $x$ that is $x ∈ A$ among all subsets of the set $\{1,2,...,n\}$.
Answers are:
if $p$ is odd, then its $(2n-1)/3$.
if $p$ is even, then its $(2n+1)/3$.
Could anyone help go through how they were derived?
Among all such (call them “valid”) sets of maximal size, let $A$ be one that has maximal sum of its elements. Suppose $x\notin A$ for some $\frac n2< x\le n$. Then $A\cup\{x\}$ has more elements, hence is “invalid”, which can only happen if $x$ is eben and already $x/2\in A$. But then $A\cup\{x\}\setminus \{x/2\}$ is valid, has the same size, but a greater sum of elements - contradicting the maximality of $A$.
We conclude that the $\frac n2$ elements $2^{p-1}+1,\ldots, 2^p$ are in $A$. Then the $\frac n4$ elements $2^{p-2}+1,\ldots,2^{p-1}$ cannot be in $A$. (Strictly speaking, this reduction works only when $p\ge2$; the cases $p<2$ must be treated ad base case of this induction proof). The rest, that is $A\cap\{1,\ldots,2^{p-2}\}$ is a maximum size valid subset of $\{1,\ldots,2^{p-2}\}$, and this allows us to do induction.