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?
 A: Nice exercice,
Suppose that Alice chooses a subset $C\subset A$ satisfying the condition, whose sum is minimal and less than $n^2-n-1$ (or equivalently the sum of the complementary is at least $n^2+1$).
If $|C|>n-1$, you could take out the minimal element $m$ of $C$, without breaking the condition, so you have $|C|=n-1$.
On the one hand, the implies that the mean value of the elements of $C$ is small:
$$\frac1{n-1}\sum_{x\in C}x\leq \frac{n^2-n-1}{n-1}=n-\frac1{n-1}<n.$$
On the other hand, we can prove that the condition implies that this mean value cannot be that small:
By induction, all multiples of $m$ have to belong to $C$, and whatever $x\in C$, all integers $x+\lambda m\leq 2n-1$ also belong to $C$. One can decompose $C$ as a disjoint union of arithmetical progressions with difference $m$, with first term at least $m$ and last term between $2n-m$ and $2n-1$.
We shall prove that any such arithmetical progression has mean value bigger than $n$.
It is easier to consider the converse arithmetical progression first.
Consider $t\in[1,m]$ and $\ell$ such that $t+\ell m\leq 2n-m$, then the mean value of the arithmetical progression from $t$ to $t+\ell m$ is:
$$M(t,\ell+1)=\frac1{\ell+1}\sum_{\lambda=0}^\ell(t+\lambda m)=t+\frac \ell2m\leq n-\frac{m-t}2\leq n.$$
If you consider now a arithmetical progression in $C$ from $x\geq m$ to $x+\ell m\in[2n-m,2n-1]$, then its mean value is:
\begin{align*}
\frac1{\ell+1}\sum_{\lambda=0}^\ell(x+\lambda m)= & 2n-\frac1{\ell+1}\sum_{\lambda=0}^\ell(2n-(x+\lambda m))\\
= & 2n-\frac1{\ell+1}\sum_{\lambda=0}^\ell((2n-(x+\ell m))+(\ell-\lambda)m)\\
= & 2n-\frac1{\ell+1}\sum_{\lambda=0}^\ell((2n-(x+\ell m))+\lambda m)\\
= & 2n-M(2n-(x+\ell m),\ell+1)\\
\geq & n.
\end{align*}
If all these arithmetical progressions have mean value bigger than $n$, the mean value of $C$ itself cannot be strictly below $n$ and we have a contradiction, so your subset is indeed optimal.
A: 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.
