A directed graph has each vertex with outdegree 2. Prove that it is possible to split the vertices into 3 sets so that for each vertex $v$, $v$ is not simultaneously in the same set with both of the vertices that it points to. [i]David Yang.[/i] [hide="Stronger Version"]See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=492100]here[/url].[/hide]

A tournament is a directed graph for which every (unordered) pair of vertices has a single directed edge from one vertex to the other. Let us define a proper directed-edge-coloring to be an assignment of a color to every (directed) edge, so that for every pair of directed edges $\overrightarrow{uv}$ and $\overrightarrow{vw}$, those two edges are in different colors. Note that it is permissible for $\overrightarrow{uv}$ and $\overrightarrow{uw}$ to be the same color. The directed-edge-chromatic-number of a tournament is defined to be the minimum total number of colors that can be used in order to create a proper directed-edge-coloring. For each $n$, determine the minimum directed-edge-chromatic-number over all tournaments on $n$ vertices. [i]Proposed by Po-Shen Loh[/i]

There are $n$ $(n \ge 3)$ players in a table tennis tournament, in which any two players have a match. Player $A$ is called not out-performed by player $B$, if at least one of player $A$'s losers is not a $B$'s loser. Determine, with proof, all possible values of $n$, such that the following case could happen: after finishing all the matches, every player is not out-performed by any other player.

In a country, there are ${}N{}$ cities and $N(N-1)$ one-way roads: one road from $X{}$ to $Y{}$ for each ordered pair of cities $X \neq Y$. Every road has a maintenance cost. For each $k = 1,\ldots, N$ let's consider all the ways to select $k{}$ cities and $N - k{}$ roads so that from each city it is possible to get to some selected city, using only selected roads. We call such a system of cities and roads with the lowest total maintenance cost $k{}$[i]-optimal[/i]. Prove that cities can be numbered from $1{}$ to $N{}$ so that for each $k = 1,\ldots, N$ there is a $k{}$-optimal system of roads with the selected cities numbered $1,\ldots, k$. [i]Proposed by V. Buslov[/i]

At a party, $25$ elves give each other presents. No elf gives a present to herself. Each elf gives a present to at least one other elf, but no elf gives a present to all other elves. Show that it is possible to choose a group of three elves including at least two elves who give a present to exactly one of the other two elves in the group.

A directed graph has each vertex with outdegree 2. Prove that it is possible to split the vertices into 3 sets so that for each vertex $v$, $v$ is not simultaneously in the same set with both of the vertices that it points to. [i]David Yang.[/i] [hide="Stronger Version"]See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=492100]here[/url].[/hide]

There are $n(n\ge 8)$ airports, some of which have one-way direct routes between them. For any two airports $a$ and $b$, there is at most one one-way direct route from $a$ to $b$ (there may be both one-way direct routes from $a$ to $b$ and from $b$ to $a$). For any set $A$ composed of airports $(1\le | A| \le n-1)$, there are at least $4\cdot \min \{|A|,n-|A| \}$ one-way direct routes from the airport in $A$ to the airport not in $A$. Prove that: For any airport $x$, we can start from $x$ and return to the airport by no more than $\sqrt{2n}$ one-way direct routes.

In an election, there are $1395$ candidates and some voters. Each voter, arranges all the candidates by the priority order. We form a directed graph with $1395$ vertices, an arrow is directed from $U$ to $V$ when the candidate $U$ is at a higher level of priority than $V$ in more than half of the votes. (otherwise, there's no edge between $U,V$) Is it possible to generate all complete directed graphs with $1395$ vertices?

Let $G$ be a complete directed graph with $2024$ vertices and let $k \leq 10^5$ be a positive integer. Angel and Boris play the following game: Angel colors $k$ of the edges in red and puts a pawn in one of the vertices. After that in each move, first Angel moves the pawn to a neighboring vertex and then Boris has to flip one of the non-colored edges. Boris wins if at some point Angel can't make a move. Find, depending on $G$ and $k$, whether or not Boris has a winning strategy.

There are $24$ robots on the plane. Each robot has a $70^{\circ}$ field of view. What is the maximum number of observing relations? (Observing is a one-sided relation)

A group of mathematicians is attending a conference. We say that a mathematician is $k-$[i]content[/i] if he is in a room with at least $k$ people he admires or if he is admired by at least $k$ other people in the room. It is known that when all participants are in a same room then they are all at least $3k + 1$-content. Prove that you can assign everyone into one of $2$ rooms in a way that everyone is at least $k$-content in his room and neither room is empty. [i]Admiration is not necessarily mutual and no one admires himself.[/i] [i]Matija Bucić[/i]

Let $p$ be a prime number. We construct a directed graph of $p$ vertices, labeled with integers from $0$ to $p-1$. There is an edge from vertex $x$ to vertex $y$ if and only if $x^2+1\equiv y \pmod{p}$. Let $f(p)$ denotes the length of the longest directed cycle in this graph. Prove that $f(p)$ can attain arbitrarily large values.

There are $n(n\ge 8)$ airports, some of which have one-way direct routes between them. For any two airports $a$ and $b$, there is at most one one-way direct route from $a$ to $b$ (there may be both one-way direct routes from $a$ to $b$ and from $b$ to $a$). For any set $A$ composed of airports $(1\le | A| \le n-1)$, there are at least $4\cdot \min \{|A|,n-|A| \}$ one-way direct routes from the airport in $A$ to the airport not in $A$. Prove that: For any airport $x$, we can start from $x$ and return to the airport by no more than $\sqrt{2n}$ one-way direct routes.

The road infrastructure in a country consists of an even number of direct roads, each of which is bidirectional. Moreover, for any two cities $X$ and $Y$, there is at most one direct road between the two of them and there exists a sequence $X = X_0, X_1, ..., X_{n - 1}, X_n = Y$ of cities such that for any $i = 0, ..., n - 1$, there exists a direct road between $X_i$ and $X_{i + 1}$. Prove that all direct roads in this country can be oriented (i.e. each road can become a one-way road) such that each city $X$ is the starting point for an even number of direct roads. Proposed by [i]Mirko Petrushevski[/i]

An arrow is assigned to each edge of a polyhedron such that for each vertex, there is an arrow pointing towards that vertex and an arrow pointing away from that vertex. Prove that there exist at least two faces such that the arrows on their boundaries form a cycle.