Let $A$ and $B$ be two sets of non-negative integers, define $A+B$ as the set of the values obtained when we sum any (one) element of the set $A$ with any (one) element of the set $B$. For instance, if $A=\{2,3\}$ and $B=\{0,1,2,5\}$ so $A+B=\{2,3,4,5,7,8\}$. Determine the least integer $k$ such that there is a pair of sets $A$ and $B$ of non-negative integers with $k$ and $2k$ elements, respectively, and $A+B=\{0,1,2,\dots, 2019,2020\}$
Problem
Source: Peru EGMO TST 2020 #1
Tags: combinatorics
12.03.2021 00:21
$|A+B|<=2k^2$ so $k>31$ . For $k=32$ take the sets: $A={0,1,2,....,31}$ and $B={0,32,64,96,....,2016}$
14.03.2021 13:35
P2nisic wrote: $|A+B|<=2k^2$ so $k>31$ . For $k=32$ take the sets: $A={0,1,2,....,31}$ and $B={0,32,64,96,....,2016}$ but at that time, $A+B=\{0,1,2,\dots, 2047\}$, not $\{0,1,2,\dots, 2019,2020\}$ so we can change B into $B={0,32,64,96,....,1984, 1989}$
14.03.2021 19:19
Another example : A={0,1,...,31} B={0,32,32+31×1,...32+31×27,901,901+32×1,....,901+32×34}
21.09.2021 20:02
mathisreal wrote: Let $A$ and $B$ be two sets of non-negative integers, define $A+B$ as the set of the values obtained when we sum any (one) element of the set $A$ with any (one) element of the set $B$. For instance, if $A=\{2,3\}$ and $B=\{0,1,2,5\}$ so $A+B=\{2,3,4,5,7,8\}$. Determine the least integer $k$ such that there is a pair of sets $A$ and $B$ of non-negative integers with $k$ and $2k$ elements, respectively, and $A+B=\{0,1,2,\dots, 2019,2020\}$ The largest value of | A + B | occurs when all the sums 2 to 2 of the elements of A and B are disjoint, which would be k (2k), then: $$ \Rightarrow 2021\leq 2k ^ 2 $$$$ \Rightarrow 32\leq k $$below an example: $ A = {0,1,2, ...., 31} $ $ B = {0,32,64,96, ...., 1984, 1989} $
15.04.2022 18:11
$2021=|A+B|\leq |A|\cdot |B|=2k^2 \implies k\geq 32$ and here is the construction for $k=32:$ $A=\{0,1,2,...,31\},B=\{0,32,32\cdot 2,...,32\cdot 62,1989\}$. So the answer is $32$.