Suppose that the statement doesn't hold. For a vertex $v$, let $\mathrm{deg}_{+}{v}$ be its outdegree. The number of pairs $ \left ( X, (A,B,C,D) \right )$ such that $A,B,C,D$ have edges oriented from $X$ to them is $\displaystyle\sum\limits_{v\in V} \binom{\mathrm{deg}_{+}{v}}{4}$ which by Jensen is greater than $60 \displaystyle\binom{\frac{\sum\limits_{v\in V} \mathrm{deg}_{+}{v}}{60}}{4}=60\displaystyle\binom{\frac{59}{2}}{4}$. On the other hand, every quadruplet $(A,B,C,D)$ appears in at most $3$ aforementioned pairs by assumption, hence their number is less than $3\binom{60}{4}$.

than $3\binom{60}{4}$, which yields a contradiction.

Aiscrim wrote: On the other hand, every quadruplet $(A,B,C,D)$ appears in at most $3$ aforementioned pairs by assumption, hence their number is less than $3\binom{60}{4}$. Can you explain why can not $(A,B,C,D)$ quadruple appear 4 times in the pairs?

zaurimeshveliani wrote: Aiscrim wrote: On the other hand, every quadruplet $(A,B,C,D)$ appears in at most $3$ aforementioned pairs by assumption, hence their number is less than $3\binom{60}{4}$. Can you explain why can not $(A,B,C,D)$ quadruple appear 4 times in the pairs? If it appears 4 times with, say, points E, F, G ,H, then color these red and A, B, C, D green, and you are done.

We can annihilate this problem by Probability method (Evan Chen's handout). I will use some notation of graph theory: In a Graph $G$ consist of $60$ vertices, select $X=\{A,B,C,D\}$ randomly and we call a vertex $v_i$ score member if and only if $v_i$ has a directed way to each of $A,B,C,D$. Define \[X_i=\begin{cases} 1 \quad \text{if $v_i$ is the score member}\\ 0 \quad \text{otherwise} \end{cases}\] Randomly pick four vertices and compute the expected value of the number of score member \[\mathbb{E}\left[X=\{A,B,C,D\}\right]=\mathbb{E}\left[X_1\right]+\cdots+\mathbb{E}\left[X_{60}\right].\]WLOG arrange the index such that $v_1=A,v_2=B,v_3=C,v_4=D$. Clearly $\mathbb{E}\left[X_1\right]=\mathbb{E}\left[X_2\right]=\mathbb{E}\left[X_3\right]=\mathbb{E}\left[X_4\right]=0$. And for $i=5,\cdots, 60$, we have $\mathbb{E}\left[X_i\right]=\mathbb{P}(X_i=1)=\tfrac{1}{2^4}=\tfrac{1}{16}$. Hence \[\mathbb{E}\left[X=\{A,B,C,D\}\right]=56\cdot \frac{1}{16}=3.5.\]Since $\mathbb{E}\left[X\right]$ is integer, we conclude that there exist four vertices $A,B,C,D$ such that the number of score member is greater than $3$. Sorry for my bad English.

Dear Complex2Liu, I admit that I do not understand your solution. What is the exact variable of which you find the expectation? Complex2Liu wrote: \[\mathbb{E}\left[X=\{A,B,C,D\}\right]=\mathbb{E}\left[X_1\right]+\cdots+\mathbb{E}\left[X_{60}\right].\]WLOG arrange the index such that $v_1=A,v_2=B,v_3=C,v_4=D$. Clearly $\mathbb{E}\left[X_1\right]=\mathbb{E}\left[X_2\right]=\mathbb{E}\left[X_3\right]=\mathbb{E}\left[X_4\right]=0$. And for $i=5,\cdots, 60$, we have $\mathbb{E}\left[X_i\right]=\mathbb{P}(X_i=1)=\tfrac{1}{2^4}=\tfrac{1}{16}$. Why $\mathbb{P}(X_i=1)=\tfrac{1}{2^4}$? It seems strange, too, that probabilistic method gives a better estimate than the direct computation (your solution remains the same for 53 vertices, direct computation needs 58).

I pick $4$ red towns randomly and estimate the expected value of the incident green towns. I will use $v_1\longrightarrow v_2$ to denote $v_1$ has a directed way to $v_2$. And for each of the remain $56$ towns, it can be colored green if and only if both of the $4$ red town has a directed way to it, hence the probability is $\frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}\times\frac{1}{2}=\frac{1}{16}$. If you notice any error, please let me know! Thanks

It's not that I noticed any error, I just do not understand. If you choose four random vertices $A$, $B$, $C$, $D$ in a FIXED graph (which is indeed what you want) and a random vertex $E$ then why the probability that all edges between $E$ and $A$, $B$, $C$, $D$ are directed from $E$ is $1\over 16$? This should mean that exactly one sixteenth part of quintuples $(A, B, C, D, E)$ in the graph satisfies this condition, which is obviously untrue. Basically, the problem is that the directions of edges are not independent.

The method is the exact same as for some Iranian problem which asked for a directed $K_{7,7}$. My solution is identical to that of the other posters - just pick $4$ random vertices, and compute the expectation of the size of their out-neighborhood. Jensen gives it is bigger than $3$ and you are done. I'm surprised that this is problem 3 from IZhO, given how well known this technique is.

Complex2Liu wrote: We can annihilate this problem by Probability method (Evan Chen's handout). I will use some notation of graph theory: In a Graph $G$ consist of $60$ vertices, select $X=\{A,B,C,D\}$ randomly and we call a vertex $v_i$ score member if and only if $v_i$ has a directed way to each of $A,B,C,D$. Define \[X_i=\begin{cases} 1 \quad \text{if $v_i$ is the score member}\\ 0 \quad \text{otherwise} \end{cases}\] Randomly pick four vertices and compute the expected value of the number of score member \[\mathbb{E}\left[X=\{A,B,C,D\}\right]=\mathbb{E}\left[X_1\right]+\cdots+\mathbb{E}\left[X_{60}\right].\]WLOG arrange the index such that $v_1=A,v_2=B,v_3=C,v_4=D$. Clearly $\mathbb{E}\left[X_1\right]=\mathbb{E}\left[X_2\right]=\mathbb{E}\left[X_3\right]=\mathbb{E}\left[X_4\right]=0$. And for $i=5,\cdots, 60$, we have $\mathbb{E}\left[X_i\right]=\mathbb{P}(X_i=1)=\tfrac{1}{2^4}=\tfrac{1}{16}$. Hence \[\mathbb{E}\left[X=\{A,B,C,D\}\right]=56\cdot \frac{1}{16}=3.5.\]Since $\mathbb{E}\left[X\right]$ is integer, we conclude that there exist four vertices $A,B,C,D$ such that the number of score member is greater than $3$. Sorry for my bad English. I'm sorry, but I think that's wrong. You have only shown that there exist such a coloring, but not the problem statement. And in general, I don't think that probabilistic works here, that's a typical mistake you've made, for more information visit: http://math.bme.hu/~gabor/oktatas/SztoM/AlonSpencer.ProbMethod3ed.pdf

Juraev wrote: There are $60$ towns in $Graphland$ every two countries of which are connected by only a directed way. Prove that we can color four towns to red and four towns to green such that every way between green and red towns are directed from red to green Assume the contrary.We count the tuples of the form $T=(X,(A,B,C,D))$ where $X$ has an edge going from itself to $ A,B,C,D$.Fixing $X$ gives $T=\sum \binom{d_x}{4}$.Now fixing $A,B,C,D$ we have atmost $3$ other $X$ satisfying the conditions.Thus $T\leq 3\binom{60}{4}$. Now note that $\binom{x}{4}$ is convex for $x\geq 3$ as $f"(x)=\dfrac{(x^2-3x)}{2}$.Thus since for $x<3 \binom{x}{4}=0$ so we can assume this as convex . Now \[3\binom{60}{4}\geq T=\sum \binom{d_v}{4}\geq 60\binom{\tfrac{59}{2}}{4} \implies 2832\geq 2915\]a contradiction so we are done.$\blacksquare$

Can college students participate in the IZhO? The website is not clear because some of the schools have "university" in their titles.

From what I know they cannot. If you are about the Lyceum of BSU, then it's just the name of a high school.