Solution?

Hello! Let $T_{n}$ be the set $\{1,2,\ldots,2^{n}\}$ and $A_{n}$ one of its acceptable subsets.The answer is $|A_{n}|_{\max}=2^{\lfloor \frac{n+1}{2}\rfloor}$ We will proceed by induction.Obviously $|A_{1}|_{\max}=2$ and $|A_{2}|_{\max}=2$ thus our assumption is satified. Suppose that $|A_{2k}|_{\max}=2^{\lfloor \frac{2k+1}{2}\rfloor}=2^{k}$.We have to prove that $|A_{2k+1}|_{\max}=|A_{2k+2}|_{\max}=2^{k+1}$. We will prove the equality for $|A_{2k+1}|_{\max}$ first. Observe that the relation $|A_{2k}|_{\max}=2^{k}$ implies that we can choose at most $2^{k}$ elements from the set $T_{2k+1}-T_{2k}$ so that the conditions are satisfied. (Keep this in mind because we will use it later). Suppose that the elements $s_{1},s_{2},\ldots ,s_{2^k}\in T_{2k}$ satisfy the conditions of the problem.Then consider the numbers $2^{2k}+s_{1},2^{2k}+s_{2},\ldots ,2^{2k}+s_{2^{k}}$ which belong to the set $T_{2k+1}-T_{2k}$. The set $B=\left(\bigcup_{i=1}^{2^k} s_{i}\right)\cup \left(\bigcup_{i=1}^{2^k} 2^{2k}+s_{i}\right)$ is acceptable. Indeed,the difference between two of its elements is either of the form $s_{i}-s_{j}$ or of the form $2^{2k}+(s_{i}-s_{j})$. The greatest power of $2$ that divides these numbers is even.Thus $|A_{2k+1}|_{\max} \geq |B|=2^{k+1}$ However if there was an acceptable set with more than $2^{k+1}$ elements then one of the sets $T_{2k},T_{2k+1}-T_{k}$ would contain at least $2^{k}+1$ of them. This is a contradiction (see observation a few lines above). Thus $|A_{2k+1}|_{\max}=2^{k+1}$ which is what we wanted to prove.It remains to show that $|A_{2k+2}|_{\max}=2^{k+1}$ Let $C$ be an acceptable subset of the set $T_{2k+2}$. If it contains elements only from $T_{2k+1}$ or $T_{2k+2}-T_{2k+1}$ then according to what we have proved so far,it can't have more than $2^{k+1}$ elements. Suppose on the contrary that it contains elements from both $T_{2k+1},T_{2k+2}-T_{2k+1}$.Obviously,it can't contain a pair of elements of the form $(m,2^{2k+1}+m)$ Let $x,y$ be two of its elements with $y=2^{2k+1}+z$ with $z\in T_{2k+1}$ and $z\neq x$ Then $y-x=2^{2k+1}+(z-x)$.Since $z-x<2^{2k+2}$ we have $v_{2}(y-x)=v_{2}(z-x) \ \bf \color{red} (1)$.This must be even. Let $D\subset C$ be a set that contains only the elements of $C$ that belong to $T_{2k+2}-T_{2k+1}$. If we subtract $2^{2k+1}$ from each of $D$'s elements then we create a new set $E$.Observe that $F=E\cup (C-D)$ is acceptable and all its elements belong to $T_{2k+1}$. It is acceptable because according to $\bf \color{red} (1)$ the greatest power of $2$ that divides the difference of $2$ of $C$'s elements doesn't depend on the term $2^{2k+1}$. Since all the pairwise differences between elements of $F$ are equal to the pairwise differences between elements of $C$, with the possible subtraction of $2^{2k+1}$ and $C$ is acceptable,$F$ is acceptable as well. Also $|F|=|C|$ and $|F|\leq 2^{k+1}$ thus $|C|\leq 2^{k+1}$. This value can be achieved if we select the set $B$ (see a few lines above). $\rule{430pt}{1pt}$ If you find any mistakes,or you need additional clarification,let me know.

too easy problem for TST: my solution: let $a_n$ be the maximum number of elements of $S=\{1,2,\cdots ,2^n\}$ for example $A$ such that for any two elements $x,y\in A\longrightarrow v_2(x-y)$ is even similarly let $b_n$ be the maximum number of elements of $S=\{1,2,\cdots ,2^n\}$ for example $B$ such that for any two elements $x,y\in B\longrightarrow v_2(x-y)$ is odd.note that $a_0=1,a_1=2,a_2=2,b_1=1,b_2=2$ Lemma:for every natural $n\ge 1$ we have $b_n=a_{n-1}$. prove:let $B=\{ a_1,a_2,\cdots ,a_{b_{n}}\}$ note that for any two elements $x,y\in B\longrightarrow v_2(x-y)\ge 1$ so all of the elements of $B$ are odd or all of them are even now consider two cases: $1)$ all of the elements of $B$ are even so $B=\{ 2k_1,2k_2,\cdots ,2k_{b_n}\}$ now note that from the condition for any two elements $2k_i,2k_j; v_2(k_i-k_j)$ must be even and because $k_i\le 2^{n-1}$ so in this case $b_n=a_{n-1}$. $2)$ all of the elements of $B$ are odd. similarly we get that $b_n=a_{n-1}$. so $b_n=a_{n-1}$ and the lemma proved. back to the main problem: let $A=\{ a_1,a_2,\cdots ,a_{a_{n}}\}$ now consider two cases: $1)$ there is one element $x$ of $A$ such that $v_2(x)=1$ now take another element $y\in A$ obviously $v_2(y)\le 1$(if $v_2(y)\ge 2$ then $v_2(x-y)=1$ which is absurd. so for any $x\in A$ we have $v_2(x)\le 1$ let $A=C\cup D$ such that $C$ is a subset of odd numbers of $A$ and $D$ be the subset of even numbers of $A$ then from the induction we get that $|C|=|D|=b_{n-1}=a_{n-2}$. so in this case $a_n=|C|+|D|=2a_{n-2}$. $2)$ there doesn't exist $x\in A$ such that $v_2(x)=1$ then let $A=C\cup D$ such that $C$ is a subset of odd numbers of $A$ and $D$ be the subset of even numbers of $A$ then from the induction we get that $|C|=a_{n-2},|D|=b_{n-1}=a_{n-2}$ so in this case $a_n=|C|+|D|=2a_{n-2}$. so for $n\ge 2$ we must have $a_{n}=2a_{n-2}$ because $a_0=1,a_1=2,a_2=2$ we get by induction that $a_n=2^{\lfloor \frac{n+1}{2}\rfloor}$. DONE

wow didnt read your solutions but mine nearly obvious. the odd and even numbers dont have any effect on each other so we talk about them separately . now is we add each element of the set {1,3,...,2^n-1 -1} by 1 and then divide by2 then we will have {1,2,3,...,2^n-1}=A and....

and we want to choose maximum elements of A whoch each two difference have an odd V2. which if we call it g(n-1) and problem desire f(n) then we will have f(n)=2.g(n-1) . since you can say the exact thing for {2,4,....,2^n} . and for g(n) : all elements belonging to the maxim set of g are congruent mod2 so like before we can observe that g(n)=f(n-1) the rest is obvious.

Answer: $2^{\lfloor \frac{n+1}{2}\rfloor}$. Lower Bound: We can choose $1,2$ for $n=1$. If we choose $\{a_1,...,a_{2^k}\}$ for $n=2k-1,$ then we choose $\{a_1,...,a_{2^k},a_1+2^{2k},...,a_{2^k}+2^{2k}\}$ for $n=2k+1$. We choose the same set for $n=2k$ with $n=2k-1$. Upper Bound: Assume that $\geq 2^k+1$ numbers can be chosen for $n=2k-1$. $\textbf{Claim:} \ $ Let $x=\overline{x_1...x_{2k+1}}$ and $y=\overline{y_1...y_{2k+1}}$ be two binary strings. If $2|v_2(x-y)$ and $\overline{x_i...x_{2k+1}}=\overline{y_i...y_{2k+1}}$, then $i$ is even. Construct $2^k+1$ binary strings. Pair $x_{2k+1}-x_{2k},...,x_3-x_2$ for each string where $x_i$ is the $i.$ digit and $x_{2i}-x_{2i+1}$ pair is the $i.$ pair. By the claim and piegonhole principle, there exists $\geq 2^{k-1}+1$ strings whose $k.$ pairs are same. Similarily, there exists $2^{k-2}+1$ strings among $2^{k-1}+1$ whose both $(k-1).$ and $k.$ pairs are same. With this process, we get that there exists $\geq 2^0+1=2$ strings whose $1.,...,k.$ pairs are same. Since the largest string is $\leq 10...0$ with $2k$ times $0'$s. Also there are two strings whose last $2k$ digits are same so one of their first digit is $1$ and the other's is $0$. Hence last $2k$ digits must be $0...0$ but this is not possible since $0...0$ with $2k+1$ times $0'$s is not a positive integer. Thus, there are at most $2^k$ numbers in $A=\{1,2,...,2^{2k}\}$. $\{1,2,...,2^{2k-1}\}$ is a subset of $A$ so the answer cannot be larger for $2k-1$. These complete the proof.$\blacksquare$