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.

The Queen of Hearts rules a kingdom with $n$ (distinguishable) cities. Each pair of cities is either connected with a bridge or not connected with a bridge. Each day, the Queen of Hearts visits $2021$ cities. For every pair of cities, if she sees a bridge she gets angry and destroys it; otherwise she feels nice and constructs a bridge between them. We call two configurations of bridges [i]equivalent[/i] if one can be reached from the other after a finite number of days. Show that there is some integer $M$ such that if $n>M$, two configurations are equivalent if both of the following conditions hold: [list] [*] The parity of the total number of bridges is the same in both configurations [*] For every city, the parity of the number of bridges going out of that city is the same in both configurations. [/list]

Let $G = (V, E)$ be a finite simple graph on $n$ vertices. An edge $e$ of $G$ is called a [i]bottleneck[/i] if one can partition $V$ into two disjoint sets $A$ and $B$ such that [list] [*] at most $100$ edges of $G$ have one endpoint in $A$ and one endpoint in $B$; and [*] the edge $e$ is one such edge (meaning the edge $e$ also has one endpoint in $A$ and one endpoint in $B$). [/list] Prove that at most $100n$ edges of $G$ are bottlenecks. [i]Proposed by Yang Liu[/i]

In a mathematical competition, in which $6$ problems were posed to the participants, every two of these problems were solved by more than $\frac 25$ of the contestants. Moreover, no contestant solved all the $6$ problems. Show that there are at least $2$ contestants who solved exactly $5$ problems each. [i]Radu Gologan and Dan Schwartz[/i]

On a $16 \times 16$ torus as shown all $512$ edges are colored red or blue. A coloring is [i]good [/i]if every vertex is an endpoint of an even number of red edges. A move consists of switching the color of each of the $4$ edges of an arbitrary cell. What is the largest number of good colorings so that none of them can be converted to another by a sequence of moves?

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.

Consider a finite undirected graph in which each edge belongs to at most three cycles. Prove that its vertices can be colored with three colors so that any two vertices connected by an edge have different colors. [i](A cycle in a graph is a sequence of distinct vertices \( v_1, v_2, \ldots, v_k \), \( k \geq 3 \), such that \( v_i v_{i+1} \) is an edge for each \( i = 1, 2, \ldots, k \); we consider \( v_{k+1} = v_1 \). The edges \( v_i v_{i+1} \) belong to the cycle.)[/i]

An $ n \times n, n \geq 2$ chessboard is numbered by the numbers $ 1, 2, \ldots, n^2$ (and every number occurs). Prove that there exist two neighbouring (with common edge) squares such that their numbers differ by at least $ n.$

In a school there are $n$ classes and $n$ students. The students are enrolled in classes, such that no two of them have exactly the same classes. Prove that we can close a class in a such way that there still are no two of them which have exactly the same classes.

155 birds $ P_1, \ldots, P_{155}$ are sitting down on the boundary of a circle $ C.$ Two birds $ P_i, P_j$ are mutually visible if the angle at centre $ m(\cdot)$ of their positions $ m(P_iP_j) \leq 10^{\circ}.$ Find the smallest number of mutually visible pairs of birds, i.e. minimal set of pairs $ \{x,y\}$ of mutually visible pairs of birds with $ x,y \in \{P_1, \ldots, P_{155}\}.$ One assumes that a position (point) on $ C$ can be occupied simultaneously by several birds, e.g. all possible birds.

On a connected graph $G$, one may perform the following operations: [list] [*]choose a vertice $v$, and add a vertice $v'$ such that $v'$ is connected to $v$ and all of its neighbours [*] choose a vertice $v$ with odd degree and delete it [/list] Show that for any connected graph $G$, we may perform a finite number of operations such that the resulting graph is a clique. Proposed by [i]idonthaveanaopsaccount[/i]

Determine all graphs $G$ with the following two properties: $\bullet$ G contains at least one Hamilton path. $\bullet$ For any pair of vertices, $u, v \in G$, if there is a Hamilton path from $u$ to $v$ then the edge $uv$ is in the graph $G$

There are $ n ( \ge 4 ) $ people and some people shaked hands each other. Two people can shake hands at most 1 time. For arbitrary four people $ A, B, C, D$ such that $ (A,B), (B,C), (C,D) $ shaked hands, then one of $ (A,C), (A,D), (B,D) $ shaked hand each other. Prove the following statements. (a) Prove that $ n $ people can be divided into two groups, $ X, Y ( \ne \emptyset )$ , such that for all $ (x,y) $ where $ x \in X $ and $ y \in Y $, $ x $ and $ y $ shaked hands or $ x $ and $ y $ didn't shake hands. (b) There exist two people $ A , B $ such that the set of people who are not $ A $ and $ B $ that shaked hands with $ A $ is same wiith the set of people who are not $ A $ and $ B $ that shaked hands with $ B $.

There are $n$ students in a class, and some pairs of these students are friends. Among any six students, there are two of them that are not friends, and for any pair of students that are not friends there is a student among the remaining four that is friends with both of them. Find the maximum value of $n$.

Let $S = \{1, \dots, n\}$. Given a bijection $f : S \to S$ an [i]orbit[/i] of $f$ is a set of the form $\{x, f(x), f(f(x)), \dots \}$ for some $x \in S$. We denote by $c(f)$ the number of distinct orbits of $f$. For example, if $n=3$ and $f(1)=2$, $f(2)=1$, $f(3)=3$, the two orbits are $\{1,2\}$ and $\{3\}$, hence $c(f)=2$. Given $k$ bijections $f_1$, $\ldots$, $f_k$ from $S$ to itself, prove that \[ c(f_1) + \dots + c(f_k) \le n(k-1) + c(f) \] where $f : S \to S$ is the composed function $f_1 \circ \dots \circ f_k$. [i]Proposed by Maria Monks Gillespie[/i]

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]

At this year's Olympiad, some of the students are friends (friendship is symmetric), however there are also students which are not friends. No matter how the students are partitioned in two contest halls, there are always two friends in different halls. Let $A$ be a fixed student. Show that there exist students $B$ and $C$ such that there are exactly two friendships in the group $\{ A,B,C \}$. [i]Authored by Mirko Petrushevski[/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.

Assume that a face of a convex polyhedron $ P$ has a common edge with every other face. Show that there exists a simple closed polygon that consists of edges of $ P$ and passes through all vertices. [i]L .Lovasz[/i]

Let $n$ points be given arbitrarily in the plane, no three of them collinear. Let us draw segments between pairs of these points. What is the minimum number of segments that can be colored red in such a way that among any four points, three of them are connected by segments that form a red triangle?

We call a matrix $\textsl{binary matrix}$ if all its entries equal to $0$ or $1$. A binary matrix is $\textsl{Good}$ if it simultaneously satisfies the following two conditions: (1) All the entries above the main diagonal (from left to right), not including the main diagonal, are equal. (2) All the entries below the main diagonal (from left to right), not including the main diagonal, are equal. Given positive integer $m$, prove that there exists a positive integer $M$, such that for any positive integer $n>M$ and a given $n \times n$ binary matrix $A_n$, we can select integers $1 \leq i_1 <i_2< \cdots < i_{n-m} \leq n$ and delete the $i_i$-th, $i_2$-th,$\cdots$, $i_{n-m}$-th rows and $i_i$-th, $i_2$-th,$\cdots$, $i_{n-m}$-th columns of $A_n$, then the resulting binary matrix $B_m$ is $\textsl{Good}$.

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

We have a complete graph with $n$ vertices. We have to color the vertices and the edges in a way such that: no two edges pointing to the same vertice are of the same color; a vertice and an edge pointing him are coloured in a different way. What is the minimum number of colors we need?

Consider lattice points of a $6*7$ grid.We start with two points $A,B$.We say two points $X,Y$ connected if one can reflect several times WRT points $A,B$ and reach from $X$ to $Y$.Over all choices of $A,B$ what is the minimum number of connected components?

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.