There are $n>1$ cities in the country, some pairs of cities linked two-way through straight flight. For every pair of cities there is exactly one aviaroute (can have interchanges). Major of every city X counted amount of such numberings of all cities from $1$ to $n$ , such that on every aviaroute with the beginning in X, numbers of cities are in ascending order. Every major, except one, noticed that results of counting are multiple of $2016$. Prove, that result of last major is multiple of $2016$ too.

A simple graph has $N{}$ vertices and less than $3(N-1)/2$ edges. Prove that its vertices can be divided into two non-empty groups so that each vertex has at most one neighbor in the group it doesn't belong to.

consider $n\geq 6$ points $x_1,x_2,\dots,x_n$ on the plane such that no three of them are colinear. We call graph with vertices $x_1,x_2,\dots,x_n$ a "road network" if it is connected, each edge is a line segment, and no two edges intersect each other at points other than the vertices. Prove that there are three road networks $G_1,G_2,G_3$ such that $G_i$ and $G_j$ don't have a common edge for $1\leq i,j\leq 3$. Proposed by Morteza Saghafian

The vertices of a connected graph cannot be coloured with less than $n+1$ colours (so that adjacent vertices have different colours). Prove that $\dfrac{n(n-1)}{2}$ edges can be removed from the graph so that it remains connected. [i]V. Dolnikov[/i] [b]EDIT.[/b] It is confirmed by the official solution that the graph is tacitly assumed to be [b]finite[/b].

There were finitely many persons at a party among whom some were friends. Among any $4$ of them there were either $3$ who were all friends among each other or $3$ who weren't friend with each other. Prove that you can separate all the people at the party in two groups in such a way that in the first group everyone is friends with each other and that all the people in the second group are not friends to anyone else in second group. (Friendship is a mutual relation).

Let $n\geq 2$ be a positive integer. We call a [i]vertex[/i] every point in the coordinate plane, whose $x$ and $y$ coordinates both are from the set $\{1,2,3,...,n\}$. We call a segment between two vertices an [i]edge[/i], if its length if $1$. We've colored some edges red, such that between any two vertices, there is a unique path of red edges (a path may contain each edge at most once). The red edge $f$ is [i]vital[/i] for an edge $e$, if the path of red edges connecting the two endpoints of $e$ contain $f$. Prove that there is a red edge, such that it is vital for at least $n$ edges.

In the nation of Onewaynia, certain pairs of cities are connected by one-way roads. Every road connects exactly two cities (roads are allowed to cross each other, e.g., via bridges), and each pair of cities has at most one road between them. Moreover, every city has exactly two roads leaving it and exactly two roads entering it. We wish to close half the roads of Onewaynia in such a way that every city has exactly one road leaving it and exactly one road entering it. Show that the number of ways to do so is a power of $2$ greater than $1$ (i.e.\ of the form $2^n$ for some integer $n \ge 1$). [i]Victor Wang[/i]

Given seven points on a plane, with no three points collinear. Prove that it is always possible to divide these points into the vertices of a triangle and a convex quadrilateral, with no shared parts between the two shapes.

On the parliament of Sikinia, for any two deputies, there is third deputy, which knows exactly one of the two. Every deputy belongs to one of the two ruling parties. Every day, he president tells a certain group of deputies to change the party that they belong, and all the deputies which which know at least one of the deputies of the group has to change their party too. Prove that, the president can reach any configuration of deputies between two parties.(The president himself isn't a member of the parliament of Sikinia). [I]Proposed by S. Berlov[/i]

Given an integer $n\ge2$, the graph $G$ is defined by: - Vertices of $G$ are represented by binary strings of length $n$ - Two vertices $a,b$ are connected by an edge if and only if they differ in exactly $2$ places Let $S$ be a subset of the vertices of $G$, and let $S'$ be the set of edges between vertices in $S$ and vertices not in $S$. Show that if $|S|$ (the size of $S$) $\le2^{n-2}$, then $|S'|\ge|S|$.

The kingdom of Anisotropy consists of $n$ cities. For every two cities there exists exactly one direct one-way road between them. We say that a [i]path from $X$ to $Y$[/i] is a sequence of roads such that one can move from $X$ to $Y$ along this sequence without returning to an already visited city. A collection of paths is called [i]diverse[/i] if no road belongs to two or more paths in the collection. Let $A$ and $B$ be two distinct cities in Anisotropy. Let $N_{AB}$ denote the maximal number of paths in a diverse collection of paths from $A$ to $B$. Similarly, let $N_{BA}$ denote the maximal number of paths in a diverse collection of paths from $B$ to $A$. Prove that the equality $N_{AB} = N_{BA}$ holds if and only if the number of roads going out from $A$ is the same as the number of roads going out from $B$. [i]Proposed by Warut Suksompong, Thailand[/i]

Let $P$ be a set of people. For two people $A$ and $B$, if $A$ knows $B$, $B$ also knows $A$. Each person in $P$ knows $2$ or less people in the set. $S$, a subset of $P$ with $k$ people, is called [i][b]k-independent set[/b][/i] of $P$ if any two people in $S$ don’t know each other. $X_1, X_2, …, X_{4041}$ are [i][b]2021-independent set[/b][/i]s of $P$ (not necessarily distinct). Show that there exists a [i][b]2021-independent set[/b][/i] of $P$, $\{v_1, v_2, …, v_{2021}\}$, which satisfies the following condition: [center] For some integer $1 \le i_1 < i_2 < \cdots < i_{2021} \leq 4041$, $v_1 \in X_{i_1}, v_2 \in X_{i_2}, \ldots, v_{2021} \in X_{i_{2021}}$ [/center] [hide=Graph Wording] Thanks to Evan Chen, here's a graph wording of the problem :) Let $G$ be a finite simple graph with maximum degree at most $2$. Let $X_1, X_2, \ldots, X_{4041}$ be independent sets of size $2021$ [i](not necessarily distinct)[/i]. Prove that there exists another independent set $\{v_1, v_2, \ldots, v_{2021}\}$ of size $2021$ and indices $1 \le t_1 < t_2 < \cdots < t_{2021} \le 4041$ such that $v_i \in X_{t_i}$ for all $i$. [/hide]

There are $5$ vertices labelled $1,2,3,4,5$. For any two pairs of vertices $u, v$, the edge $uv$ is drawn with probability $1/2$. If the probability that the resulting graph is a tree is given by $\dfrac{p}{q}$ where $p, q$ are coprime, then find the value of $q^{1/10} + p$.

An infinite number of participants gathered for the Olympiad, who were registered under the numbers $1, 2,\ldots$. It turns out that for every $n = 1, 2,\ldots$ a participant with number $n{}$ has at least $n{}$ friends among the remaining participants (note: friendship is mutual). There is a hotel with an infinite number of double rooms. Prove that the participants can be accommodated in double rooms so that there is a couple of friends in each room. [i]Proposed by V. Bragin, P. Kozhevnikov[/i]

It is given a graph whose vertices are positive integers and an edge between numbers $a$ and $b$ exists if and only if $a + b + 1 | a^2 + b^2 + 1$. Is this graph connected?

On fields of $n \times n$ chessboard $n^2$ different integers have been arranged, one in each field. In each column, field with biggest number was colored in red. Set of $n$ fields of chessboard name [i]admissible[/i], if no two of that fields aren't in the same row and aren't in the same column. From all admissible sets, set with biggest sum of numbers in it's fields has been chosen. Prove that red field is in this set.

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).

Alice and Bob play a game on a connected graph with $2n$ vertices, where $n\in \mathbb{N}$ and $n>1$.. Alice and Bob have tokens named A and B respectively. They alternate their turns with Alice going first. Alice gets to decide the starting positions of A and B. Every move, the player with the turn moves their token to an adjacent vertex. Bob's goal is to catch Alice, and Alice's goal is to prevent this. Note that positions of A, B are visible to both Alice and Bob at every moment. Provided they both play optimally, what is the maximum possible number of edges in the graph if Alice is able to evade Bob indefinitely? [i]Proposed by Shashank Ingalagavi and Vighnesh Sangle[/i]

There are $2^n$ words of length $n$ over the alphabet $\{0, 1\}$. Prove that the following algorithm generates the sequence $w_0, w_1, \ldots, w_{2^n-1}$ of all these words such that any two consecutive words differ in exactly one digit. (1) $w_0 = 00 \ldots 0$ ($n$ zeros). (2) Suppose $w_{m-1} = a_1a_2 \ldots a_n,\quad a_i \in \{0, 1\}$. Let $e(m)$ be the exponent of $2$ in the representation of $n$ as a product of primes, and let $j = 1 + e(m)$. Replace the digit $a_j$ in the word $w_{m-1}$ by $1 - a_j$. The obtained word is $w_m$.

Let $m$ and $n$ be positive integers. In Philand, the Kingdom of Olymphics, with $m$ cities, and the Kingdom of Mathematicians for Fun, with $n$ cities, fight a battle in rounds. Some cities in the country are connected by roads, so that it is possible to travel through all the cities via the roads. In each round of the battle, if all cities neighboring, that is, connected directly by a road, a city in one of the kingdoms are from the other kingdom, that city is conquered in the next round and switches to the other kingdom. Knowing that between the first and second round, at least one city is not conquered, show that at some point the battle must end, i.e., no city can be captured by another kingdom.

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.

In a sports tournament involving $N$ teams, each team plays every other team exactly one. At the end of every match, the winning team gets $1$ point and losing team gets $0$ points. At the end of the tournament, the total points received by the individual teams are arranged in decreasing order as follows: \[x_1 \ge x_2 \ge \cdots \ge x_N . \] Prove that for any $1\le k \le N$, \[\frac{N - k}{2} \le x_k \le N - \frac{k+1}{2}\]

Let \( G \) be a graph colored using \( k \) colors. We say that a vertex is [b]forced[/b] if it has neighbors in all the other \( k - 1 \) colors. Prove that for any \( 2024 \)-regular graph \( G \) that contains no triangles or quadrilaterals, there exists a coloring using \( 2025 \) colors such that at least \( 1013 \) of the colors have a forced vertex of that color. Note: The graph coloring must be valid, this means no \( 2 \) vertices of the same color may be adjacent.

Given a finite tree $ T$ and isomorphism $ f: T\rightarrow T$. Prove that either there exist a vertex $ a$ such that $ f(a)\equal{}a$ or there exist two neighbor vertices $ a$, $ b$ such that $ f(a)\equal{}b$, $ f(b)\equal{}a$.

There are $n > 2022$ cities in the country. Some pairs of cities are connected with straight two-ways airlines. Call the set of the cities {\it unlucky}, if it is impossible to color the airlines between them in two colors without monochromatic triangle (i.e. three cities $A$, $B$, $C$ with the airlines $AB$, $AC$ and $BC$ of the same color). The set containing all the cities is unlucky. Is there always an unlucky set containing exactly 2022 cities?