Let $n(\ge 2)$ be an integer. $2n^2$ contestants participate in a Chinese chess competition, where any two contestant play exactly once. There may be draws. It is known that (1)If A wins B and B wins C, then A wins C. (2)there are at most $\frac{n^3}{16}$ draws. Proof that it is possible to choose $n^2$ contestants and label them $P_{ij}(1\le i,j\le n)$, so that for any $i,j,i',j'\in \{1,2,...,n\}$, if $i<i'$, then $P_{ij}$ wins $P_{i'j'}$.

Prove that the edges of a simple planar graph can always be oriented such that the outdegree of all vertices is at most three. [i]UK Competition Problem[/i]

Santa Claus has at least $n$ gifts for $n$ children. For $i\in\{1,2, ... , n\}$, the $i$-th child considers $x_i > 0$ of these items to be desirable. Assume that \[\dfrac{1}{x_1}+\cdots+\dfrac{1}{x_n}\le1.\] Prove that Santa Claus can give each child a gift that this child likes.

The organizers of a mathematical congress found that if they accomodate any participant in a room the rest can be accomodated in double rooms so that 2 persons living in each room know each other. Prove that every participant can organize a round table on graph theory for himself and an even number of other people so that each participant of the round table knows both his neigbours. [i]Proposed by S. Berlov, S. Ivanov[/i]

Some cities in country are connected with oneway road. It is known that every closed cyclic route, that don`t break traffic laws, consists of even roads. Prove that king of city can place military bases in some cities such that there are not roads between these cities, but for every city without base we can go from city with base by no more than $1$ road. [hide=PS]I think it should be one more condition, like there is cycle that connect all cities [/hide]

Let $G$ be a simple $k$ edge-connected graph on $n$ vertices and let $u$ and $v$ be different vertices of $G$. Prove that there are $k$ edge-disjoint paths from $u$ to $v$ each having at most $\frac{20n}{k}$ edges.

The complete graph with 6 points and 15 edges has each edge colored red or blue. Show that we can find 3 points such that the 3 edges joining them are the same color.

Given a graph with $99$ vertices and degrees in $\{81,82,\dots,90\}$, prove that there exist $10$ vertices of this graph with equal degrees and a common neighbour. [i]Proposed by Alireza Alipour[/i]

A game is played by $n$ girls ($n \geq 2$), everybody having a ball. Each of the $\binom{n}{2}$ pairs of players, is an arbitrary order, exchange the balls they have at the moment. The game is called nice [b]nice[/b] if at the end nobody has her own ball and it is called [b]tiresome[/b] if at the end everybody has her initial ball. Determine the values of $n$ for which there exists a nice game and those for which there exists a tiresome game.

A crazy physicist discovered a new kind of particle wich he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time. (i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it. (ii) At any moment, he may double the whole family of imons in the lab by creating a copy $I'$ of each imon $I$. During this procedure, the two copies $I'$ and $J'$ become entangled if and only if the original imons $I$ and $J$ are entangled, and each copy $I'$ becomes entangled with its original imon $I$; no other entanglements occur or disappear at this moment. Prove that the physicist may apply a sequence of such operations resulting in a family of imons, no two of which are entangled.

a.) There are $2n+1$ ($n>2$) batteries. We don't know which batteries are good and which are bad but we know that the number of good batteries is greater by $1$ than the number of bad batteries. A lamp uses two batteries, and it works only if both of them are good. What is the least number of attempts sufficient to make the lamp work? b.) The same problem but the total number of batteries is $2n$ ($n>2$) and the numbers of good and bad batteries are equal. [i]Proposed by Alexander Shapovalov[/i]

Consider the figure below, composed of 16 segments. Prove that there is no curve intersecting each segment exactly once. (The curve may be not closed, may intersect itself, but it is not allowed to touch the segments or to pass through the vertices.) [asy] draw((0,0)--(6,0)--(6,3)--(0,3)--(0,0)); draw((0,3/2)--(6,3/2)); draw((2,0)--(2,3/2)); draw((4,0)--(4,3/2)); draw((3,3/2)--(3,3)); [/asy]

One country has $n$ cities and every two of them are linked by a railroad. A railway worker should travel by train exactly once through the entire railroad system (reaching each city exactly once). If it is impossible for worker to travel by train between two cities, he can travel by plane. What is the minimal number of flights that the worker will have to use?

In a school class with $ 3n$ children, any two children make a common present to exactly one other child. Prove that for all odd $ n$ it is possible that the following holds: For any three children $ A$, $ B$ and $ C$ in the class, if $ A$ and $ B$ make a present to $ C$ then $ A$ and $ C$ make a present to $ B$.

Given a simple, connected graph with $n$ vertices and $m$ edges. Prove that one can find at least $m$ ways separating the set of vertices into two parts, such that the induced subgraphs on both parts are connected.

In a simple graph $G$, an operation is defined as taking two neighbor vertices $u,v$ which have a common neighbor, deleting the edge between $u,v$ and adding a new vertex $w$ whose neighbors are exactly the common neighbors of $u$ and $v$. Starting with the complete graph $G=K_n$ where $n\ge 3$ is a positive integer, find the maximum number of operations that can be applied. Proposed by[i] Deniz Can Karaçelebi[/i]

For a positive integer $n$, there are two countries $A$ and $B$ with $n$ airports each and $n^2-2n+ 2$ airlines operating between the two countries. Each airline operates at least one flight. Exactly one flight by one of the airlines operates between each airport in $A$ and each airport in $B$, and that flight operates in both directions. Also, there are no flights between two airports in the same country. For two different airports $P$ and $Q$, denote by "[i]$(P, Q)$-travel route[/i]" the list of airports $T_0, T_1, \ldots, T_s$ satisfying the following conditions. [list] [*] $T_0=P,\ T_s=Q$ [*] $T_0, T_1, \ldots, T_s$ are all distinct. [*] There exists an airline that operates between the airports $T_i$ and $T_{i+1}$ for all $i = 0, 1, \ldots, s-1$. [/list] Prove that there exist two airports $P, Q$ such that there is no or exactly one [i]$(P, Q)$-travel route[/i]. [hide=Graph Wording]Consider a complete bipartite graph $G(A, B)$ with $\vert A \vert = \vert B \vert = n$. Suppose there are $n^2-2n+2$ colors and each edge is colored by one of these colors. Define $(P, Q)-path$ a path from $P$ to $Q$ such that all of the edges in the path are colored the same. Prove that there exist two vertices $P$ and $Q$ such that there is no or only one $(P, Q)-path$. [/hide]

The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer ${n\ge 4}$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices are joined by an edge). [i]Proposed by Norman Do, Australia[/i]

Given $n(\geq 3)$ distinct points in the plane, no three of which are on the same straight line, prove that there exists a simple closed polygon with these points as vertices.

In a company of 7 sousliks each souslik has 4 friends. Is it always possible to find in this company two non-intersecting groups of 3 sousliks each such that in both groups all sousliks are friends?

Adithya and Bill are playing a game on a connected graph with $n > 2$ vertices, two of which are labeled $A$ and $B$, so that $A$ and $B$ are distinct and non-adjacent and known to both players. Adithya starts on vertex $A$ and Bill starts on $B$. Each turn, both players move simultaneously: Bill moves to an adjacent vertex, while Adithya may either move to an adjacent vertex or stay at his current vertex. Adithya loses if he is on the same vertex as Bill, and wins if he reaches $B$ alone. Adithya cannot see where Bill is, but Bill can see where Adithya is. Given that Adithya has a winning strategy, what is the maximum possible number of edges the graph may have? (Your answer may be in terms of $n$.) [i]Proposed by Steven Liu[/i]

The $\underline{\text{path number}}$ of a graph is the minimum number of paths we need to partition the vertices of a graph. Given a connected graph with the independence number $k > 1$, what is the maximum possible value for the path number in this graph? Find the answer in terms of $k$. The independence number of a graph $\textbf{G}$ is the maximum possible number $k$, such that there exist $k$ pairwise non-adjacent vertices in $\textbf{G}$.

Let $n$ be an integer with $n\geq 3$ and assume that $2n$ vertices of a regular $(4n + 1)-$gon are coloured. Show that there must exist three of the coloured vertices forming an isosceles triangle.

Define a boomerang as a quadrilateral whose opposite sides do not intersect and one of whose internal angles is greater than $180^{\circ}$. Let $C$ be a convex polygon with $s$ sides. The interior region of $C$ is the union of $q$ quadrilaterals, none of whose interiors overlap each other. $b$ of these quadrilaterals are boomerangs. Show that $q\ge b+\frac{s-2}{2}$.

G is a complete geometric graph such that for any 4-coloring of its edges, we can find n edges which are pairwise disjoint and have the same color. Prove that the minimum number of vertices of G is 6n-4. [hide=idea]a graph with 6n-4 vertices has 2n-1 pairwise disjoint edges with 1 of 2 colors. by PP, there exist n pairwise disjoint edges of the same color. [/hide]