For a tournament with $8$ vertices, if from any vertex it is impossible to follow a route to return to itself, we call the graph a [i]good[/i] graph. Otherwise, we call it a [i]bad[/i] graph. Prove that $(1)$ there exists a tournament with $8$ vertices such that after changing the orientation of any at most $7$ edges of the tournament, the graph is always a[i]bad[/i] graph; $(2)$ for any tournament with $8$ vertices, one can change the orientation of at most $8$ edges of the tournament to get a [i]good[/i] graph. (A tournament is a complete graph with directed edges.)

Let $m$ be a positive integer, and $A_1, A_2, \ldots, A_m$ (not necessarily different) be $m$ subsets of a finite set $A$. It is known that for any nonempty subset $I$ of $\{1, 2 \ldots, m \}$, \[ \Big| \bigcup_{i \in I} A_i \Big| \ge |I|+1. \] Show that the elements of $A$ can be colored black and white, so that each of $A_1,A_2,\ldots,A_m$ contains both black and white elements.

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

Suppose $ \,G\,$ is a connected graph with $ \,k\,$ edges. Prove that it is possible to label the edges $ 1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1. [b]Note: Graph-Definition[/b]. A [b]graph[/b] consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $ \,u,v\,$ belongs to at most one edge. The graph $ G$ is connected if for each pair of distinct vertices $ \,x,y\,$ there is some sequence of vertices $ \,x \equal{} v_{0},v_{1},v_{2},\cdots ,v_{m} \equal{} y\,$ such that each pair $ \,v_{i},v_{i \plus{} 1}\;(0\leq i < m)\,$ is joined by an edge of $ \,G$.

Some cities of a country consisting of $n$ cities are connected by round trip flights so that there are at least $k$ flights from any city and any city is reachable from any city. Prove that for any such flight organization these flights can be distributed among $n-k$ air companies so that one can reach any city from any city by using of at most one flight of each air company.

Eight football teams play matches against each other in such a way that no two teams meet twice and no three teams play all of the three possible matches. What is the largest possible number of matches?

A spider built a web on the unit circle. The web is a planar graph with straight edges inside the circle, bounded by the circumference of the circle. Each vertex of the graph lying on the circle belongs to a unique edge, which goes perpendicularly inward to the circle. For each vertex of the graph inside the circle, the sum of the unit outgoing vectors along the edges of the graph is zero. Prove that the total length of the web is equal to the number of its vertices on the circle.

There are infinitely many people registered on the social network Mugbook. Some pairs of (different) users are registered as friends, but each person has only finitely many friends. Every user has at least one friend. (Friendship is symmetric; that is, if $A$ is a friend of $B$, then $B$ is a friend of $A$.) Each person is required to designate one of their friends as their best friend. If $A$ designates $B$ as her best friend, then (unfortunately) it does not follow that $B$ necessarily designates $A$ as her best friend. Someone designated as a best friend is called a $1$-best friend. More generally, if $n> 1$ is a positive integer, then a user is an $n$-best friend provided that they have been designated the best friend of someone who is an $(n-1)$-best friend. Someone who is a $k$-best friend for every positive integer $k$ is called popular. (a) Prove that every popular person is the best friend of a popular person. (b) Show that if people can have infinitely many friends, then it is possible that a popular person is not the best friend of a popular person. [i]Romania (Dan Schwarz)[/i]

Let $X$ be a set of $n + 1$ elements, $n\geq 2$. Ordered $n$-tuples $(a_1,\ldots,a_n)$ and $(b_1,\ldots,b_n)$ formed from distinct elements of $X$ are called[i] disjoint [/i]if there exist distinct indices $1\leq i \neq j\leq n$ such that $a_i = b_j$. Find the maximal number of pairwise disjoint $n$-tuples.

On some planet, there are $2^N$ countries $(N \geq 4).$ Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1,$ each field being either yellow or blue. No two countries have the same flag. We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set. [i]Proposed by Tonći Kokan, Croatia[/i]

Consider the graph on $1000$ vertices $v_1, v_2, ...v_{1000}$ such that for all $1 \le i < j \le 1000$, $v_i$ is connected to $v_j$ if and only if $i$ divides $j$. Determine the minimum number of colors that must be used to color the vertices of this graph such that no two vertices sharing an edge are the same color.

Let $n$ be an integer greater than $1$, and let $p$ be a prime divisor of $n$. A confederation consists of $p$ states, each of which has exactly $n$ airports. There are $p$ air companies operating interstate flights only such that every two airports in different states are joined by a direct (two-way) flight operated by one of these companies. Determine the maximal integer $N$ satisfying the following condition: In every such confederation it is possible to choose one of the $p$ air companies and $N$ of the $np$ airports such that one may travel (not necessarily directly) from any one of the $N$ chosen airports to any other such only by flights operated by the chosen air company.

A graph $G(V,E)$ is triangle-free, but adding any edges to the graph will form a triangle. It's given that $|V|=2019$, $|E|>2018$, find the minimum of $|E|$ .

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?

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a [i]clique[/i] if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its [i]size[/i]. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room. [i]Author: Vasily Astakhov, Russia[/i]

The graph $G$ is not $3$-coloured. Prove that $G$ can be divided into two graphs $M$ and $N$ such that $M$ is not $2$-coloured and $N$ is not $1$-coloured. [i]V. Dolnikov[/i]

Given a (simple) graph $G$ with $n \geq 2$ vertices $v_1, v_2, \dots, v_n$ and $m \geq 1$ edges, Joël and Robert play the following game with $m$ coins: [list=i] [*]Joël first assigns to each vertex $v_i$ a non-negative integer $w_i$ such that $w_1+\cdots+w_n=m$. [*]Robert then chooses a (possibly empty) subset of edges, and for each edge chosen he places a coin on exactly one of its two endpoints, and then removes that edge from the graph. When he is done, the amount of coins on each vertex $v_i$ should not be greater than $w_i$. [*]Joël then does the same for all the remaining edges. [*]Joël wins if the number of coins on each vertex $v_i$ is equal to $w_i$. [/list] Determine all graphs $G$ for which Joël has a winning strategy.

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?

We call a graph with n vertices $k-flowing-chromatic$ if: 1. we can place a chess on each vertex and any two neighboring (connected by an edge) chesses have different colors. 2. we can choose a hamilton cycle $v_1,v_2,\cdots , v_n$, and move the chess on $v_i$ to $v_{i+1}$ with $i=1,2,\cdots ,n$ and $v_{n+1}=v_1$, such that any two neighboring chess also have different colors. 3. after some action of step 2 we can make all the chess reach each of the n vertices. Let T(G) denote the least number k such that G is k-flowing-chromatic. If such k does not exist, denote T(G)=0. denote $\chi (G)$ the chromatic number of G. Find all the positive number m such that there is a graph G with $\chi (G)\le m$ and $T(G)\ge 2^m$ without a cycle of length small than 2017.

In a sports league, each team uses a set of at most $t$ signature colors. A set $S$ of teams is[i] color-identifiable[/i] if one can assign each team in $S$ one of their signature colors, such that no team in $S$ is assigned any signature color of a different team in $S$. For all positive integers $n$ and $t$, determine the maximum integer $g(n, t)$ such that: In any sports league with exactly $n$ distinct colors present over all teams, one can always find a color-identifiable set of size at least $g(n, t)$.

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.

There is a graph with 30 vertices. If any of 26 of its vertices with their outgoiing edges are deleted, then the remained graph is a connected graph with 4 vertices. What is the smallest number of the edges in the initial graph with 30 vertices?

Consider a $m\times n$ rectangular board consisting of $mn$ unit squares. Two of its unit squares are called [i]adjacent[/i] if they have a common edge, and a [i]path[/i] is a sequence of unit squares in which any two consecutive squares are adjacent. Two parths are called [i]non-intersecting[/i] if they don't share any common squares. Each unit square of the rectangular board can be colored black or white. We speak of a [i]coloring[/i] of the board if all its $mn$ unit squares are colored. Let $N$ be the number of colorings of the board such that there exists at least one black path from the left edge of the board to its right edge. Let $M$ be the number of colorings of the board for which there exist at least two non-intersecting black paths from the left edge of the board to its right edge. Prove that $N^{2}\geq M\cdot 2^{mn}$.

Let $S$ be a finite set of points on a plane, where no three points are collinear, and the convex hull of $S$, $\Omega$, is a $2016-$gon $A_1A_2\ldots A_{2016}$. Every point on $S$ is labelled one of the four numbers $\pm 1,\pm 2$, such that for $i=1,2,\ldots , 1008,$ the numbers labelled on points $A_i$ and $A_{i+1008}$ are the negative of each other. Draw triangles whose vertices are in $S$, such that any two triangles do not have any common interior points, and the union of these triangles is $\Omega$. Prove that there must exist a triangle, where the numbers labelled on some two of its vertices are the negative of each other.

We are given a finite, simple, non-directed graph. Ann writes positive real numbers on each edge of the graph such that for all vertices the following is true: the sum of the numbers written on the edges incident to a given vertex is less than one. Bob wants to write non-negative real numbers on the vertices in the following way: if the number written at vertex $v$ is $v_0$, and Ann's numbers on the edges incident to $v$ are $e_1,e_2,\ldots,e_k$, and the numbers on the other endpoints of these edges are $v_1,v_2,\ldots,v_k$, then $v_0=\sum_{i=1}^k e_iv_i+2022$. Prove that Bob can always number the vertices in this way regardless of the graph and the numbers chosen by Ann. Proposed by [i]Boldizsár Varga[/i], Verőce