Given two positive integers $m$ and $n$, find the smallest positive integer $k$ such that among any $k$ people, either there are $2m$ of them who form $m$ pairs of mutually acquainted people or there are $2n$ of them forming $n$ pairs of mutually unacquainted people.

$n$ players ($n \ge 4$) took part in the tournament. Each player played exactly one match with every other player, there were no draws. There was no four players $(A, B, C, D)$, such that $A$ won with $B$, $B$ won with $C$, $C$ won with $D$ and $D$ won with $A$. Determine, depending on $n$, maximum number of trios of players $(A, B, C)$, such that $A$ won with $B$, $B$ won with $C$ and $C$ won with $A$. (Attention: Trios $(A, B, C)$, $(B, C, A)$ and $(C, A, B)$ are the same trio.)

Consider the graph $G$ with $100$ vertices, and the minimum odd cycle goes through $13$ vertices. Prove that the vertices of the graph can be colored in $6$ colors in a way that no two adjacent vertices have the same color.

Two positive integers $a$ and $b$ are prime-related if $a = pb$ or $b = pa$ for some prime $p$. Find all positive integers $n$, such that $n$ has at least three divisors, and all the divisors can be arranged without repetition in a circle so that any two adjacent divisors are prime-related. Note that $1$ and $n$ are included as divisors.

Let $n\geq 3$ be a fixed integer. Each side and each diagonal of a regular $n$-gon is labelled with a number from the set $\left\{1;\;2;\;...;\;r\right\}$ in a way such that the following two conditions are fulfilled: [b]1.[/b] Each number from the set $\left\{1;\;2;\;...;\;r\right\}$ occurs at least once as a label. [b]2.[/b] In each triangle formed by three vertices of the $n$-gon, two of the sides are labelled with the same number, and this number is greater than the label of the third side. [b](a)[/b] Find the maximal $r$ for which such a labelling is possible. [b](b)[/b] [i]Harder version (IMO Shortlist 2005):[/i] For this maximal value of $r$, how many such labellings are there? [hide="Easier version (5th German TST 2006) - contains answer to the harder version"] [i]Easier version (5th German TST 2006):[/i] Show that, for this maximal value of $r$, there are exactly $\frac{n!\left(n-1\right)!}{2^{n-1}}$ possible labellings.[/hide] [i]Proposed by Federico Ardila, Colombia[/i]

Juty and Azgor plays the following game on a \((2n+1) \times (2n+1)\) board with Juty moving first. Initially all cells are colored white. On Juty's turn, she colors a white cell green and on Azgor's turn, he colors a white cell red. The game ends after they color all the cells of the board. Juty wins if all the green cells are connected, i.e. given any two green cells, there is at least one chain of neighbouring green cells connecting them (we call two cells [i]neighboring[/i] if they share at least one corner), otherwise Azgor wins. Determine which player has a winning strategy. [i]Proposed by Atonu Roy Chowdhury[/i]

In a school there are $n$ classes and $k$ student. We know that in this school every two students have attended exactly in one common class. Also due to smallness of school each class has less than $k$ students. If $k-1$ is not a perfect square, prove that there exist a student that has attended in at least $\sqrt k$ classes. [i]Proposed by Mohammad Moshtaghi Far, Kian Shamsaie[/i] [b]Rated 4[/b]

In a group of kids there are $2022$ boys and $2023$ girls. Every girl is a friend with exactly $2021$ boys. Friendship is a symmetric relation: if A is a friend of B, then B is also a friend of A. Prove that it is not possible that all boys have the same number of girl friends. [i]Proposed by the JMMO Problem Selection Committee[/i]

The shores of the Tvertsy River are two parallel straight lines. There are point-like villages on the shores in some order: 20 villages on the left shore and 15 villages on the right shore. We want to build a system of non-intersecting bridges, that is, segments connecting a couple of villages from different shores, so that from any village you can get to any other village only by bridges (you can't walk along the shore). In how many ways can such a bridge system be built?

An $ (n, k) \minus{}$ tournament is a contest with $ n$ players held in $ k$ rounds such that: $ (i)$ Each player plays in each round, and every two players meet at most once. $ (ii)$ If player $ A$ meets player $ B$ in round $ i$, player $ C$ meets player $ D$ in round $ i$, and player $ A$ meets player $ C$ in round $ j$, then player $ B$ meets player $ D$ in round $ j$. Determine all pairs $ (n, k)$ for which there exists an $ (n, k) \minus{}$ tournament. [i]Proposed by Carlos di Fiore, Argentina[/i]

The map of a country is in the form of a convex polygon with $n (n\geq5)$ sides, such as any 3 diagonals do not concur inside the polygon. Some of the diagonals are roads, which allow movement in both directions and the other diagonals are not roads. There are cities on the intersection points of any two diagonals inside the polygon and at least one of the two diagonals is a road. Prove that you can move from any city to any other city using at most 3 roads.

In a school, there are 2021 students, each having exactly $k$ friends. There aren't three students such that all three are friends with each other. What is the maximum possible value of $k$?

One hundred million cities lie on Planet MO. Initially, there are no air routes between any two cities. Now an airline company comes. It plans to establish $5050$ two-way routes, each route connects two different cities, and no two routes connect the same two cities. The "degree" of a city is defined to be the number of routes departing from that city. The "benefit" of a route is the product of the "degrees" of the two cities it connects. Find the maximum possible value of the sum of the benefits of these $5050$ routes.

In the simple and connected graph $G$ let $x_i$ be the number of vertices with degree $i$. Let $d>3$ be the biggest degree in the graph $G$. Prove that if : $$x_d \ge x_{d-1} + 2x_{d-2}+... +(d-1)x_1$$ Then there exists a vertex with degree $d$ such that after removing that vertex the graph $G$ is still connected. Proposed by [i]Ali Mirzaie[/i]

$3n$ ($n \ge 2, n \in N$) people attend a gathering, in which any two acquaintances have exactly $n$ common acquaintances, and any two unknown people have exactly $2n$ common acquaintances. If three people know each other, it is called a [i]Taoyuan Group[/i]. (1) Find the number of all Taoyuan groups; (2) Prove that these $3n$ people can be divided into three groups, with $n$ people in each group, and the three people obtained by randomly selecting one person from each group constitute a Taoyuan group. Note: Acquaintance means that two people know each other, otherwise they are not acquaintances. Two people who know each other are called acquaintances.

Let $X$ and $Y$ be two sets of points in the plane and $M$ be a set of segments connecting points from $X$ and $Y$ . Let $k$ be a natural number. Prove that the segments from $M$ can be painted using $k$ colors in such a way that for any point $x \in X \cup Y$ and two colors $\alpha$ and $\beta$ $(\alpha \neq \beta)$, the difference between the number of $\alpha$-colored segments and the number of $\beta$-colored segments originating in $X$ is less than or equal to $1$.

The towns in one country are connected with bidirectional airlines, which are paid in at least one of the two directions. In a trip from town A to town B there are exactly 22 routes that are free. Find the least possible number of towns in the country.

At the meeting, each person is familiar with 22 people. If two persons $A$ and $B$ know each with one another, among the remaining people they do not have a common friend. For each pair individuals $A$ and $B$ are not familiar with each other, there are among the remaining six common acquaintances. How many people were at the meeting?

Let $G$ be a simple graph with 100 vertices such that for each vertice $u$, there exists a vertice $v \in N \left ( u \right )$ and $ N \left ( u \right ) \cap N \left ( v \right ) = \o $. Try to find the maximal possible number of edges in $G$. The $ N \left ( . \right )$ refers to the neighborhood.

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 graph $G$ with $n$ vertex is called [i]good [/i] if every vertex could be labelled with distinct positive integers which are less than or equal $\lfloor \frac{n^2}{4} \rfloor$ such that there exists a set of nonnegative integers $D$ with the following property: there exists an edge between $2$ vertices if and only if the difference of their labels is in $D$. Show that there exists a positive integer $N$ such that for every $n \ge N$, there exist a not-good graph with $n$ vertices.

Let [n] be the set {1, 2,. . . , n}. For any $a, b \in N$, denote $G (a, b)$ by a graph (not directed) defined by the following rule: the vertices have the form (i, f), where $i \in [a]$, and $f: [a] \to [b]$. A vertex (i, f) and a vertex (j, g) are connected if $i \neq j$, and $f (k) \neq g (k)$ holds exactly for k strictly between i and j. Prove that for any $c \in N$ there is $a, b \in N$ such that the vertices of G (a, b) cannot be well-colored with $c$ colors.

In a group of $m$ girls and $n$ boys, any two persons either know each other or do not know each other. For any two boys and any two girls, there are at least one boy and one girl among them,who do not know each other. Prove that the number of unordered pairs of (boy, girl) who know each other does not exceed $m+\frac{n(n-1)}{2}$.

Let $n$ be an even positive integer, and let $G$ be an $n$-vertex graph with exactly $\tfrac{n^2}{4}$ edges, where there are no loops or multiple edges (each unordered pair of distinct vertices is joined by either 0 or 1 edge). An unordered pair of distinct vertices $\{x,y\}$ is said to be [i]amicable[/i] if they have a common neighbor (there is a vertex $z$ such that $xz$ and $yz$ are both edges). Prove that $G$ has at least $2\textstyle\binom{n/2}{2}$ pairs of vertices which are amicable. [i]Zoltán Füredi (suggested by Po-Shen Loh)[/i]

$2017$ engineers attend a conference. Any two engineers if they converse, converse with each other in either Chinese or English. No two engineers converse with each other more than once. It is known that within any four engineers, there was an even number of conversations and furthermore within this even number of conversations: i) At least one conversation is in Chinese. ii) Either no conversations are in English or the number of English conversations is at least that of Chinese conversations. Show that there exists $673$ engineers such that any two of them conversed with each other in Chinese.