Maximum sum after some elements are deleted from the set Let $n$ be positive integer and set $A=\{1,2,...,2n-1\}$. Alice deletes at least $n-1$ integers from the set $A$, such that :

*

*For every $a\in A$ and $2a\in A$ if $a$ is deleted, $2a$ is also deleted.

*For every $a,b\in A$ and $a+b\in A$ if $a,b$ are deleted, $a+b$ is also deleted.

Find maximum sum of the elements in a set $A$ after Alice's operations.
I think the answer is $n^2$.The set $\{1,3,...,2n-1\}$ satisfies given conditions. But how can I prove that there isn't a better set?

There is another way to do this. First, let $A$ be the set of remaining integers. We may assume $A$ has exactly $n$ elements, indeed if $A$ does not, add the smallest integer $a \in \{1,2,\ldots, 2n-1\}$ not yet already in $A$.
We make 2 claims:

Claim 1: Let $a$ be an element in $A$. Then if $a$ is odd, then there must be at least $\frac{a-1}{2}$ integers $a'<a$ in $A$. If $a$ is even, then there must be at least $\frac{a}{2}$ integers $a'<a$ in $A$.

Indeed, for each pair of distinct positive integers $\{a_1,a_2\}$ w $a_1+a_2=a$, at least one integer of the pair must be in $A$. Then if $a$ is even, so must $\frac{a}{2}$ be in $A$.$\surd$

Claim 2: Let $x$ be an odd integer [not necesarily in $A$]. Then there must be at least $\frac{x+1}{2}$ integers $a'\le x$ such that $a'$ is in $A$.

Use induction on $x$. Indeed true if $x=2n-1$ [because $A$ has $n$ integers], or if $x$ is in $A$ [Claim 1]. So let us assume that there are at least $\frac{x+3}{2}$ $=\frac{x+1}{2}+1$ integers $a'\le x+2$ in $A$. Then on the one hand, if $x+1$ is not in $A$, then there must indeed be at least $\frac{x+3}{2} -|A \cap \{x+1,x+2\}|$ $\ge$ $(\frac{x+1}{2}+1)-1$ $=\frac{x+1}{2}$ integers $a'<x$ in $A$. However, on the other hand, if $x+1$ is in $A$, then as $x$ is odd, $x+1$ is even, so by Claim 1 there must indeed be at least $\frac{x+1}{2}$ integers $a'<x+1$ in $A$, or equivalently, $\frac{x+1}{2}$ integers $a'\le x$ in $A$. So either way Claim 2 follows. $\surd$
So now let us write $A=\{x_1,x_2,\ldots, x_n\}$, where the $x_k$s are in increasing order. Then by Claim 2, the inequality $x_k \le 2k-1$ must hold for each $k=1,2,\ldots, n$. This gives $$\sum_{x \in A} x \le \sum_{k=1}^n (2k-1) \ = \ n^2.$$ But then $A =\{1,3,5,\ldots,2n-1\}$ i.e., $A$ is the set of odd positive integers no larger than $2n-1$, has no more than $n$ integers and satisfies the conditions 1. and 2. above, and $\sum_{x \in A} x$ is precisely $n^2$. So this bound is tight, as the set $A$ above explicitly constructed meets this bound.

Note that we need both conditions for this bound to be tight. Take $n=4$.
Then the set $\{6,5,4,3\}$ haa no more than $4$ integers satisfies exactly one of the remaining conditions namely 2. , and the set $\{7,6,5,3\}$ satisfies the other of the remaining conditions, namely 1.
