Consider the set $M=\{1,2,3,...,2020\}.$ Find the smallest positive integer $k$ such that for any subset $A$ of $M$ with $k$ elements, there exist $3$ distinct numbers $a,b,c$ from $M$ such that $a+b, b+c$ and $c+a$ are all in $A.$
Problem
Source:
Tags: combinatorics, Sets, romania, Romanian TST, TST
13.06.2021 10:27
The problem basically says that we need $x,y,z \in A$ satisfying triangle inequality and $x+y+z$ is even $1011$ will work because u can pick all odd numbers and $2$ So now, suppose $|M| \ge 1012$. Then, we must have 2 consecutive pairs of numbers, call them $a < a+1 < b < b+1$ . Then $(a,b,b+1)$ and $(a+1,b,b+1)$ form triangle. One of them will have even sum and so this is the required triple.
13.06.2021 11:46
It's possible that $a=1$, so your proof doesn't work. Also note that $A=\{ 1,2,3,4,6 \}$ works fine for $M=\{ 1,2,3,4,5,6 \}$, so any solution without bounding is flawed. One possible approach is to prove by induction, begin with $n=4$. You'll need to do messy casework for the base case, but the induction is pretty easy.
13.06.2021 11:56
Besides being easy, this is just copy paste of China 2012. Would have wished for the problems to be more original in this test!