Show that it is possible to color the edges of $K_n$ with at most $3 \sqrt n$ colors so that there are no monochromatic triangles.
(This was previous question and I get an explanation in the comments: Does this problem make a sense? I would expect at least, not at most. Where is my thinking wrong?)
Here is a solution: Actually, the problem is trivial. Proceed inductively.
Just split $K_n$ in to two parts with ${n\over 2}$ elements in both if $n$ is even or ${n-1\over 2}$ and ${n+1\over 2}$ elements if $n$ is odd. Color all edges between this parts with one color. In one part we will not use more than $3\sqrt{n+1\over 2}$ colors. So we have used $$3\sqrt{n+1\over 2} +1$$ colors and all we have to check if $$3\sqrt{n+1\over 2} +1\leq 3\sqrt{n}$$ which is true.
Since I found this here, problem 41 I wonder how to solve it with a probabilistic method?
Fix $3\sqrt{n}$ colors. For each edge, choose one of those $3\sqrt{n}$ colors uniformly at random to color it with, with the random choice being independent for each edge.
The probability a given three vertices form a monochromatic triangle is $(\frac{1}{3\sqrt{n}})^2 = \frac{1}{9n}$.
The number of triangles whose three edge colorings are not independent of a given triangle is $3n-8$ (the triangle itself and the at most $n-3$ triangles sharing a given edge of the given triangle).
It holds that $e\frac{1}{9n}(3n-7) \le 1$, so by Lemma II, there is a nonzero probability that there are no monochromatic triangles, as wanted.