Let $n \geq 5$ be a positive integer and let $A$ and $B$ be sets of integers satisfying the following conditions: i) $|A| = n$, $|B| = m$ and $A$ is a subset of $B$ ii) For any distinct $x,y \in B$, $x+y \in B$ iff $x,y \in A$ Determine the minimum value of $m$.
Problem
Source: China Mathematical Olympiad 2015 Q3
Tags: absolute value, combinatorics proposed, combinatorics
20.12.2014 12:23
Ah,I misread the problem,but still here is a solution.The answer is $3n-3$.Proof that $3n-3$ is minimum: First,it is obvious that $0$ is not in the set-Just divide $A$ in $2$ sets,one with positive integers and one with negative,now one of these subsets has more than $2$ elements,now pick $2$ largest elements $x,y$ from one of these subsets and now $0$,$x+y$ and $x+y$ are in $B$ and $x+y$ is not in $A$,so contradiction. Lemma :There are no $3$ elements $x,y,z$(all bigger or all less then $0$) in $A$ such that $x+y=z$(If $|A|>=4$). Proof of Lemma: Denote $S$ the largest positive(negative) element in $A$ and $M$ the smallest positive(negative) .Now,if $z$ is not $S$,in $B$ we will have $S+y$ and $S+z$ and then we have a contradiction.Now,if $z=S$,we have $x+y=S$ and pick another element $t$($t$ is different from $x,y,S$) and we have $x+t$ and $S+t$ are in $B$ and none of them is in $A$,so contradiction and we proved Lemma.Applying this lemma,we conclude that if there are $m$($m>=4$) positive(negative) terms in $A$,$B$ will have at least $3m-3$ positive terms. (I realized that this lemma holds for the hole set but it is not suficent and the proof goes pretty much the same:If $P$ and $N$ have both at least two elements then WLOG $x+y=z$, let $x$ be positive and $y$ and $z$ be negative,then in the set are also $S+x$,$S+z$ and $y$ so contradiction.Also if some of them has one element,WLOG $N$ and we have $x+y=z$ $y$ is negative,then in the set are also $S+x$ and $S+z$ ) Now,name the subset of positive terms of $A$ $P$ and of negative terms $N$.At least one of the subsets $P$ and $N$ will have $3$ elements($n>=5$),$WLOG$ $P$.Now,pick the biggest in $N$ and name it $x$ and $2$ smallest in $P$ and name them $y,z$($y<z$).Obviously $x+y$ will have smaller absolute value then all sums $x+y$ where both $x$ and $y$ are in $P$ or in $N$ .Now,suppose there is another element in $B$ that is of the form $m+n$ where $m,n$ are both in $P$ or both in $N$ or an element of $A$ that is equal to $x+z$ ,then it will be equal to $y$,but that is a contradiction if we pick the biggest in $P$ $t$,then $t+y$ and $t+z$ are in $B$ and not in $A$.Also,if some of subsets $P$ or $N$ has $3$ elements $x,y,z$ such that $x+y=z$($WLOG$ $N$),then pick the smallest one in $P$ $t$ and then we will have $t+x$ and $t+y$ are in $B$ but not in $A$ so contradiction.Now,we conclude that for all integers if $A$ has $m$ positive(negative) terms then $B$ will have at least $3m-3$ positive terms(this doens't hold if $m=1$(it is more than $3m-3$) and if one of $P$ or $N$ is empty).Now,if some of sets $P$ or $N$ is empty we get the answer is $3n-3$,but if not then we obtain $3n-3$.Now,an example is easy:Let $A$ be $1,6,...1+5*(n-1)$,now it is trivial that $B$ has $3n-3$ elements and the second condition is true cause all elements in $B$ that are not in $A$ are congruent $2mod5$ and all elemnts in $A$ are $1mod5$.
20.12.2014 13:27
If the contradiction is that $S+y$ is in $A$ and it will be bigger than $S$ then it is not entirely true since they can be negative.
22.01.2015 17:17
Yes. So actually by junioragd's proof we only have to do when $ n=5 $ or $ 6 $ . It can be done in the same way too.
06.08.2021 08:44
Ans: $m=3n-1$. Proof: Clearly, 0 is not in A. Claim: If $x,y \in A$ then $x + y \notin A$. Assume that there exists $x,y \in A$ such that $x + y \in A$ We will prove by induction on $k$ that \[\left( {k + 1} \right)x + ky,\left( {k + 1} \right)y + kx \in A,\,\,i = {\kern 1pt} \overline {1,k} \,\,\,\,\,{\,^{\left( * \right)}}\]The case $k=0,1$ is clearly, now assume that $\left( {i + 1} \right)x + iy,\left( {i + 1} \right)y + ix \in A,\,\,i = {\kern 1pt} \overline {1,k} $. We have \[\begin{gathered} \left( {k + 1} \right)x + ky,\left( {k + 1} \right)y + kx \in A \Rightarrow \left( {2k + 1} \right)x + \left( {2k + 1} \right)y \in B\,\, \Rightarrow \left\{ \begin{gathered} \left( {k + 2} \right)x + \left( {k + 1} \right)y + \left( {k - 1} \right)x + ky \in B \hfill \\ \left( {k + 2} \right)y + \left( {k + 1} \right)x + \left( {k - 1} \right)y + kx \in B \hfill \\ \end{gathered} \right. \hfill \\ \left( {k + 1} \right)x + ky,\left( {k + 1} \right)y + kx,x + y \in A \Rightarrow \left( {k + 2} \right)x + \left( {k + 1} \right)y,\left( {k + 2} \right)y + \left( {k + 1} \right)x \in B \hfill \\ \end{gathered} \]\[ \Rightarrow \left( {k + 2} \right)x + \left( {k + 1} \right)y,\left( {k + 2} \right)y + \left( {k + 1} \right)x \in A\]So, (1) is proved. Now, taking $k$ big enough we have a contradiction. Therefore, \[\left| B \right| \geqslant \left| A \right| + \left| {A + A} \right| \geqslant n + 2n - 1 = 3n - 1\]Equality holds for $A = \left\{ {1;6;..;5\left( {n - 1} \right) + 1} \right\},\,\,B = \left\{ {2;7;..;10\left( {n - 1} \right) + 2} \right\}$