[300iq contest 4] Forbidden Triple

Difficulty Ratings

Idea Creativity: 3/5
Techniques Used: 3/5
Implementation : 1/5
This is the Q9 of "Few randomization problems series"
Dude I spent 10 hours on this problem with no progress...

Statement (not simplified)

You are given a set $A$ of $n$ different integers.
You need to find a subset $S$ of $A$ such that $|S| \geq \frac{n}{3}$ and there are no triple $a,b,c$ such that $a \in S, b \in S, c \in S$ and $a+b=c$.
It can be proved that it is always possible.

Solution

Pick a random real number r in $[0..1]$. For all integers $x$ in $A$, pick $x$ if and only if $x \times r$ has a decimal part in $[\frac{1}{3},\frac{2}{3})$. Repeat until $S$ is large enough. Because the expected size of $S$ each iteration is $\frac{n}{3}$, you only need a small number of iterations......

What a troll problem... This method is called probabilistic method/alteration. Check This KMO p6 for applications of this skill in Mathematics Olympiad