Here is my solution (and I think it's the only solution). There is an $x$ such that there exist $a_1,a_2,...,a_m \in A$ and $a_1-x,a_2-x,...,a_m-x \in B$. Then take D=$\{2a_1-x,2a_2-x,...,2a_m-x\}$ for $m= \frac{|A|\cdot |B|}{2n-1}$.

Click to reveal hidden text

61plus wrote: Define the operations $S+T=\{s+t|s\in S, t\in T\}$ and $2R=\{2r|r\in R\}$. Let $A,B$ be two subsets of $\{1,2\ldots,n\}$. Show that there exists a set $D$ such that 1) $D+D\in 2(A+B)$ 2) $|D|\geq\frac{|A||B|}{2n}$ For nonempty number set $S,T ,$ define the set $S+T=\{s+t|s\in S, t\in T\}$ and $2S=\{2s|s\in S\}$. Let $n$ be a positive integer , $A,B$ be two nonempty subsets of $\{1,2\ldots,n\}$.Show that : There exists the subsets $D$ of $A+B$ such that 1) $D+D\subseteq 2(A+B),$ 2) $|D|\geq\frac{|A|\cdot|B|}{2n},$ where $|X| $ be the number of elements of the finite set $X$.

tq. edited

duanby wrote: Here is my solution (and I think it's the only solution). There is an $x$ such that there exist $a_1,a_2,...,a_m \in A$ and $a_1-x,a_2-x,...,a_m-x \in B$. Then take D=$\{2a_1-x,2a_2-x,...,2a_m-x\}$ for $m= \frac{|A|\cdot |B|}{2n-1}$. A little cryptic. Let's detail that. For each $a\in A$ consider the set $a - B = \{a-b\mid b\in B$, with clearly $|a-B| = |B|$. Clearly $a-B \subset \{-n+1,-n+2,\ldots,-1,0,1,\ldots n-2,n-1\} = M$, with $|M|=2n-1$. Together, there are $|A|\cdot |B|$ positions to be filled in these sets by elements of $M$, since $\sum_{a\in A} |a-B| = |A|\cdot |B|$. By the pigeonhole principle, there must exist some $x\in M$ that belongs to at least $m = \left \lceil \dfrac{|A|\cdot |B|}{2n-1} \right \rceil \geq \dfrac{|A|\cdot |B|}{2n-1} > \dfrac{|A|\cdot |B|}{2n}$. Now use that $x$ to build the set $D$ with $|D| = m$, as stated.

For every $x$ in $[-n+1,n-1]$, define $S_x$ as follows : $$S_x = \{ (a,b) \quad a-b=x\}$$Note that the sum of $\mid S_x\mid$ over all $x$ is $\mid A \mid \cdot \mid B \mid $. Hence by PHP, there exists a $x_0$ such that $\mid S_{x_0}\mid \ge \tfrac {\mid A \mid \cdot \mid B \mid}{2n-1}> \tfrac {\mid A \mid \cdot \mid B \mid}{2n}$. Define $D=\{ a+b \quad (a,b) \in S_{x_0}\}$. Obviously, $D\subset A+B$. Now if $a_1+b_1$ and $a_2+b_2$ are elements of $D$ then we have : $$a_1+b_1+a_2+b_2=2a_1-x_0+2b_2+x_0 = 2(a_1+b_2)$$Hence $D+D \subset 2(A+B)$, and hence this choice of $D$ works. $\square$

Suppose $|A|=p$ and $|B|=q$, for each $-(n-1)\leq k\leq n-1$, define $$S_k=\{(i,j):1\leq i\leq p:1\leq j\leq j: a_i-b_j=k\}$$Notice that $$\sum_{k=-n+1}^{n-1}|S_k|=|A|\cdot|B|$$Therefore, there exists $k$ such that $|S_k|>\frac{pq}{2n}$. Suppose $$S_k=\{(i_1,j_1),...,(i_m,j_m)\}$$Define $$D=\{a_{i_1}+b_{i_1},a_{i_2}+b_{i_2},...,a_{i_m}+b_{i_m}\}$$Notice that for $1\leq x\leq y\leq m$, $$a_{i_x}+b_{i_x}+a_{i_y}+b_{i_y}=2(a_{i_x}+b_{i_y})$$Hence $D+D\subset 2(A+B)$, this completes the proof.

Motivation: Suppose $|A|\cdot |B|>2n$. Then we can get $a_i+b_j=a_k+b_l$. Then $a_i+b_l, a_k+b_j$ works. However, if we generalize, we may get stuck. After a while, we can rewrite this condition as $a_i-a_k=b_j-b_l$ or $a_i-b_l=a_k-b_j$. The key idea is to consider the set $A-B$. Note the MULTISET $A-B$ has $|A| \cdot |B|$ elements. Therefore, an element $k$ can be represented as $A-B$ at least $\frac{|A|\cdot |B|}{2n-1}$ times since $A-B \subseteq \{-n+1, \cdots, n-1\}$. Suppose $a_{x_j}-b_{y_j}=t$ for $j=1,\cdots, m$ where $m\ge \frac{|A| \cdot |B|}{2n-1}$. Then I claim $D=\{a_{x_i}+b_{y_i}\}$ works. Since $a_{x_i}$'s are distinct, it follows that $D$ has exactly $m$ elements. Furthermore, $a_{x_i}+b_{y_i}+a_{x_j}+b_{y_j} = 2(a_{x_i}+b_{y_j})$ so the conclusion follows.

can we use density to prove the conditions mentioned in the problem and take help of additive combi ?