Why is the graph tricolored(the only thing important is edge red or not )???? Suppose opposite. However,here is an outline:First,if $V$ has less than $2000$ elements,than $G/V$ will have at least $16$ elements and for any pair such that both of his elements are in $G/V$ $L(u,v)$ where $u,v$ are in $G/V$ will have a difirent value(cause every $u,v$ can only contain vertices from $V$),so then we trivialy have $120$ distinct pairs,so assume $V$ has more or equal $2000$ elements.Now,consider a vertex $u$.If it has more than $119$ non-red edges,than we have at least $120$ values(cause every $L(u,v)$ where $uv$ is a non-red edge will contain all $w$ $uw$ is red),so suppose every vertex has less than $120$ edges.Now,consider $V$ independently.By our assumption,it has at least $d=2000*1999/2-60*2000$ red edges and from our assumption at least $d/119$ pairs have the same value.Now,if the value contains at least $241$ elements then we pick some red edge $uv$ for which we obtain this value and for every $w$ in this set exactly one of the edges $uw$ and $vw$ will be non red,so by pigenhole we have a vertex which has at least $120$ non red edges which is a contradiction.So assume this value has at most $240$ elements and $d/119$ edges for which we have this value.Now,we have that $d/119>240^2/4+1$,so by Turan's theorem we get that the value has a triangle,but this is an obvious contradiction.

Just a typo,I assume that value has $d/119$ edges(I can't edit on phone).

I'm a bit confused on this "$120$ distinct values" part. Are the "values" the sets $\{u, v\} \cup \{w \mid w \in V \ni \triangle uvw \; \text{has exactly 2 red sides}\}$? And if this is the case, are we then supposed to show that there are at least $120$ distinct sets that can be obtained by choosing the initial two vertices, or what does "distinct values" mean?

dibyo_99 wrote: Prove that, for any choice of $V$, there exist at least $120$ distinct values of $L(u,v)$. It says for any choice of $V$,so it is more logic that you fix $V$ and go throug all pairs $u,v$. Also,if we fix $u,v$ then color one edge red and other edges arbritaly blue or white.It is obvious that we don't have a triangle $uvw$ which has $2$ red edges,so for fixed $u,v$ for any choice of $V$ $L(u,v)$ will be $(u,v)$.

Sorry for the bad translation folks. Yes, I believe it does mean $120$ distinct sets. Also, I don't know why 3 colors are used. These are just crude Google translations of the questions.

The original problem is 2 colors used.

I'll assume we're looking for 120 distinct sets $L(u, v).$ First note that every set $L(u, v)$ where $u, v \notin V$ is distinct from one another so if $|V| < 2000$ then the number of distinct sets $L(u, v)$ is at least $\binom{2015 - |V|}{2} \ge \binom{16}{2} = 120,$ so assume that $|V| \ge 2000.$ Now consider a vertex $v \in G$ and the vertices $v_1, v_2, \dots v_m$ that are connected to it by a non-red edge. It is clear that $L(v, v_i)$ are distinct for all $i \in \{1, 2, \dots, m\}$ (since $L(v, v_i)$ doesn't contain $v_j$ for all suitable $i \ne j$). Therefore we can assume that every vertex in $G$ has less than $120$ non-red edges. Considering the complete subgraph formed by the vertices in $V,$ we must have that it contains at least $\binom{2000 - 119}{2}$ red edges. Let $E$ be the set of these red edges and define $L(e)$ to be equivalent to $L(u, v)$ for any edge $e \in E$ that is incident to the vertices $u$ and $v.$ Now, assume for the sake of contradiction that there are less than $120$ distinct values of $L(u, v).$ Then by the pigeonhole principal there are edges $e_1, e_2, \dots, e_r \in E$ such that $L(e_1) = L(e_2) = \dots = L(e_r)$ where $r \ge \frac{\binom{2000 - 119}{2}}{119} > 120^2 + 1.$ Therefore the number of red edges between vertices in $L(e_1)$ is at least $120^2 + 1.$ Note that for every $w \in L(e_1) - \{u_1, v_1\}$ (where $u_1, v_1 \in V$ and $e_1 = u_1v_1$) we have that one of the edges $u_1w$ and $v_1w$ is non-red so by the pigeonhole principle, If $|L(e_1)| > 240$ then one of the vertices that $v_1$ or $w_1$ is incident to at least $120$ non-red edges, which by an earlier result means we are done. Therefore assume that $|L(e_1)| \le 240.$ Since the number of red edges between vertices in $L(e_1)$ is greater than $120^2 + 1$ we have by Turan's Theorem that there it contains a red triangle, contradiction. Therefore we are done.

Why are we all using Turan's theorem here? Here's a very very silly solution using nothing remotely high tech. First, if $|V| < 2000,$ then this is done similar as above: $\binom{2015-|V|}{2} \ge \binom{16}{2} = 120.$ (The $\binom{16}{2}$ comes from choosing any pair of vertices not in $|V|$.) So assume that $|V| \ge 2000$. Let $v_1, v_2, \dots, v_{2000}$ be vertices in $V$. Consider the sets $L(v_1, v_2), L(v_1, v_3), L(v_1, v_4), \dots, L(v_1, v_{2000})$, so $1999$ sets. Assume that they determine less than $120$ distinct ones. Therefore, at least $\lceil 1999/119 \rceil = 17$ of the sets are the same. WLOG that $L(v_1, v_2), L(v_1, v_3), \dots, L(v_1, v_{18})$ are all the same. In particular, any triangle of the form $v_1v_iv_j$ for $2 \le i, j \le 18$ must have exactly 2 red sides. In particular, at most one of the edges $v_1v_i$ for $2 \le i \le 18$ is white. (If you have $2$ white edges, then the triangle with those two edges has at most 1 red edge) So you have $16$ red edges. Since every triangle has 2 red sides, the points with the red edges to them form a $K_{16}$ of white edges. But of course any pair of vertices in this $K_{16}$ determines a unique set $L(u, v)$, and $\binom{16}{2} = 120$ again, so we're done. Note: In fact I don't believe that I even need $|V| \ge 2000$ for this to work, as in my proof never really has to use that $v_1, v_2, \dots, v_{2000}$ are indeed in $V$. But since I did find that, I'll just leave it here.

During the test, the genius Jiyang Gao (高继扬, IMO 2014&2015 Gold Medalist) pointed out that 120 can be improved to 1007.

JG666 wrote: During the test, the genius Jiyang Gao (高继扬, IMO 2014&2015 Gold Medalist) pointed out that 120 can be improved to 1007. How did he do that?