Natural numbers from $1$ to $400$ are divided in $100$ disjoint sets. Prove that one of the sets contains three numbers which are lengths of a non-degenerate triangle's sides.
Problem
Source: Latvia TST for Baltic Way 2020 P7
Tags: combinatorics
Givemebooksorgivemedeath
22.10.2020 16:42
if you need to know what a non-degenerate triangle is, here is the answer
A non-degenerate triangle is a triangle that is, having a positive area. If a,b and c are sides of the triangle, and if the following 3 conditions are true, then it is a non-degenerate triangle. a+b>c. a+c>b. b+c>a. got it from quora
Givemebooksorgivemedeath
22.10.2020 16:44
for the disjoint sets, it is just 4 numbers that don't intersect with each other, like 1,2,3,4 and 5,6,7,8. 1,2,3,4 and 3,4,5,6 would not be a disjoint set.
eduD_looC
22.10.2020 16:44
I'm a complete beginner, but this kinda looks like pigeon hole (though I don't know how to use it)
Blastoor
22.10.2020 17:03
Givemebooksorgivemedeath wrote: for the disjoint sets, it is just 4 numbers that don't intersect with each other, like 1,2,3,4 and 5,6,7,8. 1,2,3,4 and 3,4,5,6 would not be a disjoint set. While your understanding of disjoint sets is correct, I would like to point out that all the sets don't have to be of an equal size.
Kimchiks926
22.10.2020 19:05
Consider numbers between $200$ and $400$ inclusive. There are in total $201$ numbers. By Pigeonhole there will be $3$ numbers in the same set, say $a,b,c$. They form desired triangle since:
$$ a +b > 400 \ge c $$Thus we are done.
mathleticguyyy
23.10.2020 07:35
Consider one such disjoint set with $a,b$ being its least and second smallest elements, respectively. Then, the third element has to be greater than or equal to $a+b$ for it to not form a degenerate triangle with $a,b$ and similarly the fourth element has to be at least $a+2b$. Now, consider the greatest value of $b$ over all 100 sets. It has to be at least 200 since it has all 99 other b's (and as a result, all 100 b's) below it; this would bring $a+2b$ to be $>400$ as $a$ is positive which is impossible.