What is the largest number of distinct elements from set $\{1,2,3,4, \cdots, 1000\}$ that you can choose from such that no three of them are the side lengths of a triangle?
This was once in a high school junior maths competition so I would prefer a solution that does not involve complicated set notation..etc.
What I know is for a set of three elements to NOT be a triangle, then
$$ \begin{align} a+b \le c \\ a+c \le b \\ b+c \le a \\ \end{align} $$
By the way, does anybody know what sort of question this is specifically categorised as?
Let $S$ be the required set. Any three elements from $S$ can form the triple $(a,b,c)$, where we assume without loss of generality, $a<b<c$ (since each of them is distinct).
Let us instead consider when a triangle can be drawn: $$a+b - k=c$$ where $k$ is any positive integer (since the given set contains integers). Now, if $k$ is a non-positive integer (as it implies $c\ge a+b$), then a triangle cannot be drawn. So, if one wants to maximise $n(S)$, we need to make $k$ as small as possible, so that $c-b$ is as least as possible (or to minimise the difference between two consecutive elements when they are arranged in increasing order), meaning $S$ contains maximum elements. So, let $k = 0$.
We get: $$a+b = c$$ Suppose we have $n$ elements of $S$ with us. Then, one can find the two largest largest elements $m$ and $n$ of this set and the $n+1$ the element of $S$ will be $m+n$, provided $m+n\le 1000$.
Now, one can start with 1 and 2 (Starting with the smallest possible numbers would maximise $n(S)$. So, the next element is 3, then 5. One can observe that this is a Fibonacci Series (except that it starts from the second term). The Fibonacci series is of the form : $$F_0 = 1$$$$F_1 = 1$$$$F_n = F_{n-1}+F_{n-2}$$ where $n\ge2$. But our series starts from $F_1$.
Now, the Fibonacci series can be computed easily by computers or even manually. After calculating, you should get: $$S = {1,2,3,5,8,13,21,34,55,89,144,233,377,610,987}$$ $$n(S) = 15$$
Thus, one can choose no more than 15 distinct terms from ${1,2,3,4,5...1000}$, such that no three elements form a triangle.