Suppose that $n\ge 8$ persons $P_1,P_2,\dots,P_n$ meet at a party. Assume that $P_k$ knows $k+3$ persons for $k=1,2,\dots,n-6$. Further assume that each of $P_{n-5},P_{n-4},P_{n-3}$ knows $n-2$ persons, and each of $P_{n-2},P_{n-1},P_n$ knows $n-1$ persons. Find all integers $n\ge 8$ for which this is possible. (It is understood that "to know" is a symmetric nonreflexive relation: if $P_i$ knows $P_j$ then $P_j$ knows $P_i$; to say that $P_i$ knows $p$ persons means: knows $p$ persons other than herself/himself.)

Let $G$ be a simple graph on the infinite vertex set $V=\{v_1, v_2, v_3,\ldots\}$. Suppose every subgraph of $G$ on a finite vertex subset is $10$-colorable, Prove that $G$ itself is $10$-colorable.

Let the vertex set \( V \) of a graph be partitioned into \( h \) parts \( (V = V_1 \cup V_2 \cup \cdots \cup V_h) \), with \(|V_1| = n_1, |V_2| = n_2, \ldots, |V_h| = n_h \). If there is an edge between any two vertices only when they belong to different parts, the graph is called a complete \( h \)-partite graph, denoted as \( k(n_1, n_2, \ldots, n_h) \). Let \( n \) and \( r \) be positive integers, \( n \geq 6 \), \( r \leq \frac{2}{3}n \). Consider the complete \( r + 1 \)-partite graph \( k\left(\underbrace{1, 1, \ldots, 1}_{r}, n - r\right) \). Answer the following questions: 1. Find the maximum number of disjoint circles (i.e., circles with no common vertices) in this complete \( r + 1 \)-partite graph. 2. Given \( n \), for all \( r \leq \frac{2}{3}n \), find the maximum number of edges in a complete \( r + 1 \)-partite graph \( k(1, 1, \ldots, 1, n - r) \) where no more than one circle is disjoint.

Show that the edges of a connected simple (no loops and no multiple edges) finite graph can be oriented so that the number of edges leaving each vertex is even if and only if the total number of edges is even

There is a complete graph $G$ with $4027$ vertices drawn on the whiteboard. Ivan paints all the edges by red or blue colour. Find all ordered pairs $(r, b)$ such that Ivan can paint the edges so that every vertex is connected to exactly $r$ red edges and $b$ blue edges.

1990 mathematicians attend a meeting, every mathematician has at least 1327 friends (the relation of friend is reciprocal). Prove that there exist four mathematicians among them such that any two of them are friends.

Let $ n$ be a nonzero positive integer. Find $ n$ such that there exists a permutation $ \sigma \in S_{n}$ such that \[ \left| \{ |\sigma(k) \minus{} k| \ : \ k \in \overline{1, n} \}\right | = n.\]

Seventeen people correspond by mail with one another-each one with all the rest. In their letters only three different topics are discussed. each pair of correspondents deals with only one of these topics. Prove that there are at least three people who write to each other about the same topic.

In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is defined to be the least possible numbers of flights required to go from one of them to the other. It is known that for any city there are at most $100$ cities at distance exactly three from it. Prove that there is no city such that more than $2550$ other cities have distance exactly four from it.

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]

$99$ identical balls lie on a table. $50$ balls are made of copper, and $49$ balls are made of zinc. The assistant numbered the balls. Once spectrometer test is applied to $2$ balls and allows to determine whether they are made of the same metal or not. However, the results of the test can be obtained only the next day. What minimum number of tests is required to determine the material of each ball if all the tests should be performed today? [i]Proposed by N. Vlasova, S. Berlov[/i]

$n$ players took part in badminton tournament, where $n$ is positive and odd integer. Each two players played two matches with each other. There were no draws. Each player has won as many matches as he has lost. Prove that you can cancel half of the matches s.t. each player still has won as many matches as he has lost.

The graph $G$ with 2014 vertices doesn’t contain any 3-cliques. If the set of the degrees of the vertices of $G$ is $\{1,2,...,k\}$, find the greatest possible value of $k$.

Let $n\geqslant 2$ be a positive integer. Paul has a $1\times n^2$ rectangular strip consisting of $n^2$ unit squares, where the $i^{\text{th}}$ square is labelled with $i$ for all $1\leqslant i\leqslant n^2$. He wishes to cut the strip into several pieces, where each piece consists of a number of consecutive unit squares, and then [i]translate[/i] (without rotating or flipping) the pieces to obtain an $n\times n$ square satisfying the following property: if the unit square in the $i^{\text{th}}$ row and $j^{\text{th}}$ column is labelled with $a_{ij}$, then $a_{ij}-(i+j-1)$ is divisible by $n$. Determine the smallest number of pieces Paul needs to make in order to accomplish this.

Let $(v_1, ..., v_{2^n})$ be the vertices of an $n$-dimensional hypercube. Label each vertex $v_i$ with a real number $x_i$. Label each edge of the hypercube with the product of labels of the two vertices it connects. Let $S$ be the sum of the labels of all the edges. Over all possible labelings, find the minimum possible value of $\frac{S}{x^2_1+ x^2_2+ ...+ x^2_n}$ in terms of $ n$. Note: an $n$ dimensional hypercube is a graph on $2^n$ vertices labeled labeled with the binary strings of length $n$, where two vertices have an edge between them if and only if their labels differ in exactly one place. For instance, the vertices $100$ and $101$ on the $3$ dimensional hypercube are connected, but the vertices $100$ and $111$ are not.

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.

33 friends are collecting stickers for a 2011-sticker album. A distribution of stickers among the 33 friends is incomplete when there is a sticker that no friend has. Determine the least $m$ with the following property: every distribution of stickers among the 33 friends such that, for any two friends, there are at least $m$ stickers both don't have, is incomplete.

There are $n$ cities on each side of Hung river, with two-way ferry routes between some pairs of cities across the river. A city is “convenient” if and only if the city has ferry routes to all cities on the other side. The river is “clear” if we can find $n$ different routes so that the end points of all these routes include all $2n$ cities. It is known that Hung river is currently unclear, but if we add any new route, then the river becomes clear. Determine all possible values for the number of convenient cities. [i] Proposed by usjl[/i]

In some foreign country's government, there are 12 ministers. Each minister has 5 friends and 6 enemies in the government (friendship/enemyship is a symmetric relation). A triplet of ministers is called [b]uniform[/b] if all three of them are friends with each other, or all three of them are enemies. How many uniform triplets are there?

Let $n$ and $d$ be positive integers satisfying $d<\dfrac{n}{2}$. There are $n$ boys and $n$ girls in a school. Each boy has at most $d$ girlfriends and each girl has at most $d$ boyfriends. Prove that one can introduce some of them to make each boy have exactly $2d$ girlfriends and each girl have exactly $2d$ boyfriends. (I think we assume if a girl has a boyfriend, she is his girlfriend as well and vice versa) (proposed by B. Batbaysgalan, folklore).

Let $ n \geq 3$ and consider a set $ E$ of $ 2n \minus{} 1$ distinct points on a circle. Suppose that exactly $ k$ of these points are to be colored black. Such a coloring is [b]good[/b] if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly $ n$ points from $ E$. Find the smallest value of $ k$ so that every such coloring of $ k$ points of $ E$ is good.

There are $1000$ students in a school. Every student has exactly $4$ friends. A group of three students $ \left \{A,B,C \right \}$ is said to be a [i]friendly triplet[/i] if any two students in the group are friends. Determine the maximal possible number of friendly triplets. [i]Proposed by Nikola Velov[/i]

A graph $G=(V,E)$ is given. If at least $n$ colors are required to paints its vertices so that between any two same colored vertices no edge is connected, then call this graph ''$n-$colored''. Prove that for any $n \in \mathbb{N}$, there is a $n-$colored graph without triangles.

In the City of Islands there are $2021$ islands connected by bridges. For any given pair of islands $A$ and $B$, one can go from island $A$ to island $B$ using the bridges. Moreover, for any four islands $A_1, A_2, A_3$ and $A_4$: if there is a bridge from $A_i$ to $A_{i+1}$ for each $i \in \left \{ 1,2,3 \right \}$, then there is a bridge between $A_{j}$ and $A_{k}$ for some $j,k \in \left \{ 1,2,3,4 \right \}$ with $|j-k|=2$. Show that there is at least one island which is connected to any other island by a bridge.

Consider some graph $G$ with $2019$ nodes. Let's define [i]inverting[/i] a vertex $v$ the following process: for every other vertex $u$, if there was an edge between $v$ and $u$, it is deleted, and if there wasn't, it is added. We want to minimize the number of edges in the graph by several [i]invertings[/i] (we are allowed to invert the same vertex several times). Find the smallest number $M$ such that we can always make the number of edges in the graph not larger than $M$, for any initial choice of $G$. [i]Proposed by Arsenii Nikolaev, Anton Trygub (Ukraine)[/i]