Suppose $A_1,A_2,\cdots ,A_n \subseteq \left \{ 1,2,\cdots ,2018 \right \}$ and $\left | A_i \right |=2, i=1,2,\cdots ,n$, satisfying that $$A_i + A_j, \; 1 \le i \le j \le n ,$$are distinct from each other. $A + B = \left \{ a+b|a\in A,\,b\in B \right \}$. Determine the maximal value of $n$.
Problem
Source: 2018 China TST 3 Day 2 Problem 4
Tags: combinatorics, set theory
28.03.2018 15:49
My idea:let $A_i={a_i,b_i}$ ,$i=1,n$ and $a_i<b_i$ So $A_i+A_j={a_i+a_j,a_i+b_j,a_j+b_i,a_j+b_j}$ If $A_i+A_j=A_t+A_s$ then $a_i+a_j=a_s+a_t,b_i+b_j=b_s+b_t$ and $a_i+b_j=a_s+b_t$ or $a_t+b_s$ Put them to Oxy:give $n$ point $B_i(a_i,b_i)$ with $0=<a_i,b_i=<2018$ lie above $y=x$ If $A_i+A_j=A_t+A_s$,then $B_iB_j,B_tB_s$ have common mid point,and $B_iB_t$ or $B_iB_s$ is parallel to $y=x$ So we change the problem to: Find max $n$ such that there is $n$ point $(x_i;y_i)$ in $y=x+1,y=x+2,...,y=x+2018$ such that: 1)$x_i>0,y_i<2018$ 2)there is no 4 points A,B,C,D with A,B in same line,C,D in same line such that ABCD is paralleloram This is not too much hard
16.09.2018 22:51
nmd27082001 wrote: My idea:let $A_i={a_i,b_i}$ ,$i=1,n$ and $a_i<b_i$ So $A_i+A_j={a_i+a_j,a_i+b_j,a_j+b_i,a_j+b_j}$ If $A_i+A_j=A_t+A_s$ then $a_i+a_j=a_s+a_t,b_i+b_j=b_s+b_t$ and $a_i+b_j=a_s+b_t$ or $a_t+b_s$ Put them to Oxy:give $n$ point $B_i(a_i,b_i)$ with $0=<a_i,b_i=<2018$ lie above $y=x$ If $A_i+A_j=A_t+A_s$,then $B_iB_j,B_tB_s$ have common mid point,and $B_iB_t$ or $B_iB_s$ is parallel to $y=x$ So we change the problem to: Find max $n$ such that there is $n$ point $(x_i;y_i)$ in $y=x+1,y=x+2,...,y=x+2018$ such that: 1)$x_i>0,y_i<2018$ 2)there is no 4 points A,B,C,D with A,B in same line,C,D in same line such that ABCD is paralleloram This is not too much hard How would you use that to solve the problem? And are there any non-geometrical solutions, such as using mappings? I have tried mapping quadruples of sums and differences of numbers in sets, but have not gotten anywhere.
12.07.2019 15:16
Any solution?
14.05.2020 21:07
BUMMMMMMMMMMMMMMMMMMp
15.05.2020 03:41
$\boxed{4035}$. $\mathbb{YUH}$. Replace $2018$ by $m$, we will show that the answer is $2m-3$ for general $m$. Represent $A_i = \{a_1,a_2\}, a_1 < a_2$ by the point $(a_1,a_2)$ in the plane. Claim: $A_i + A_j = A_i' + A_j'$ if and only if the associated points form a (possibly degenerate) parallelogram with a pair of sides parallel to the line $y = x$. Proof: A sloth ate it up $\blacksquare$ Finish: In any right triangle lattice of $m$ points on each of its legs, if there are more than $2m-1$ vertices chosen then $4$ will form a parallelogram with a pair of sides parallel to the line $y =x$. Proof: Let $x_1,\dots, x_m$ denote the number of points lying on $y = x+c, c = 1,\dots m-1$. Consider pairwise differences of points on the same line $y = x+c$, there are $\sum \binom{x_i}{2}$ such differences and no two can be the same (else a possibly degenerate parallelogram with sides parallel to $y = x$ can be formed). Moreover, each diff must be of the form $r(1,1)$ for some $r\in [1,m-1]\cap \mathbb N$, and when $\sum x_i \ge 2m-2$, we have $\sum \binom{x_i}{2} \ge m$, contradiction. $\blacksquare$ For construction, take the $2m-3$ vertices along the legs of the right triangle. $$\mathcal{YUH}.$$ EDIT: thanks @below for point out the mistake; as you can probably tell from the way I wrote the post the other day, I was high...
11.06.2020 20:59
Stroller's main idea is correct, but his answer is actually not correct; the line $y=x+m$ and $(1,1)$ won't be considered. Furthermore, for $m=2,3$ the answers are $1,3$ respectively. This is the same outline phrased in a more algebraic manner. Let $m=2018$, we claim the answer is $2m-3$. Let $A_i=\{ a_i,b_i \}$ where $a_i<b_i$. Suppose $A_i+A_j=A_k+A_l$, then we have $a_i+a_j=a_k+a_l$ because $a_i+a_j$ is the smallest element in $A_i+A_j$ and $a_k+a_l$ is the smallest element in $A_k+A_l$, similarly $b_i+b_j=b_k+b_l$. If $a_i+b_j=a_k+b_l$, we're good, or otherwise we switch $k,l$. This means we must have $a_k-a_i=a_l-a_j$ and $b_i-a_i=b_k-a_k$, $b_j-a_j=b_l-a_l$. Armed with this observation, we let $d_i$ be the set of pairs $(A_j)$s such that $b_j-a_j=i$. We let $D_i=\{ |a_j-a_i|, (a_j,a_j+k),(a_i,a_i+k)\in d_k\}$ be a multiset. It's clear $\sum_{i=1}^{m-1} |D_i|\le m-1$ because there are $m-1$ possible values for $|a_j-a_i|$, and a repetition, say $x\in D_i,D_j$ ( i not necessarily unequal to j), then taking the corresponding pairs would have equal sum. Also, $|D_i|=\binom{d_i}{2}$ because it's a multiset, and taking two pairs of pairs, even if they contain the same pair, is allowed. Moreover, $|d_{m-1}|\le 1$. By convexity, we can have $|d_i|=2$ for all $1\le i\le m-2$, so the answer is $2(m-2)+1=2m-3$ For construction, I have $ (1,i), 2\le i\le m \cup (i, 2018) 2\le i\le m-1 $