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]

Consider a pyramid with a regular $n$-gon as its base. We colour all the segments connecting two of the vertices of the pyramid except for the sides of the base either red or blue. Show that if $n=9$ then for each such colouring there are three vertices of the pyramid connecting by three segments of the same colour, and that this is not necessarily the case if $n=8$.

In a country consisting of $2015$ cities, between any two cities there is exactly one direct round flight operated by some air company. Find the minimal possible number of air companies if direct flights between any three cities are operated by three different air companies.

All edges of a polyhedron are painted with red or yellow. For an angle of a facet, if the edges determining it are of different colors, then the angle is called [i]excentric[/i]. The[i] excentricity [/i]of a vertex $A$, namely $S_A$, is defined as the number of excentric angles it has. Prove that there exist two vertices $B$ and $C$ such that $S_B + S_C \leq 4$.

Let $n$ be an even positive integer. Show that there is a permutation $\left(x_{1},x_{2},\ldots,x_{n}\right)$ of $\left(1,\,2,\,\ldots,n\right)$ such that for every $i\in\left\{1,\ 2,\ ...,\ n\right\}$, the number $x_{i+1}$ is one of the numbers $2x_{i}$, $2x_{i}-1$, $2x_{i}-n$, $2x_{i}-n-1$. Hereby, we use the cyclic subscript convention, so that $x_{n+1}$ means $x_{1}$.

Let $T$ be a tree. Prove that there is a constant $c>0$ (independent of $n$) such that every graph with $n$ vertices that does not contain a subgraph isomorphic to $T$ has at most $cn$ edges. [i]David Yang.[/i]

Let $n$ be a positive integer and let $S$ be a set of $2^n+1$ elements. Let $f$ be a function from the set of two-element subsets of $S$ to $\{0, \dots, 2^{n-1}-1\}$. Assume that for any elements $x, y, z$ of $S$, one of $f(\{x,y\}), f(\{y,z\}), f(\{z, x\})$ is equal to the sum of the other two. Show that there exist $a, b, c$ in $S$ such that $f(\{a,b\}), f(\{b,c\}), f(\{c,a\})$ are all equal to 0.

$m,n$ are given integer numbers such that $m+n$ is an odd number. Edges of a complete bipartie graph $K_{m,n}$ are labeled by ${-1,1}$ such that the sum of all labels is $0$. Prove that there exists a spanning tree such that the sum of the labels of its edges is equal to $0$.

求最小的 $n,$ 使得对任意有 ${1000}$ 个顶点且每个顶点度均为 ${4}$ 的简单图 $G,$ 都一定可以从中取掉 ${n}$ 条边$,$ 使 ${G}$ 变为二部图$.$

There are $n\geq 2$ people at a meeting. Show that there exist two people at the meeting who have the same number of friends among the persons at the meeting. (It is assumed that if $A$ is a friend of $B,$ then $B$ is a friend of $A;$ moreover, nobody is his own friend.)

Cynthia loves Pokemon and she wants to catch them all. In Victory Road, there are a total of $80$ Pokemon. Cynthia wants to catch as many of them as possible. However, she cannot catch any two Pokemon that are enemies with each other. After exploring around for a while, she makes the following two observations: 1. Every Pokemon in Victory Road is enemies with exactly two other Pokemon. 2. Due to her inability to catch Pokemon that are enemies with one another, the maximum number of the Pokemon she can catch is equal to $n$. What is the sum of all possible values of $n$?

The localities $P_1, P_2, \dots, P_{1983}$ are served by ten international airlines $A_1,A_2, \dots , A_{10}$. It is noticed that there is direct service (without stops) between any two of these localities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.

A [i]labyrinth[/i] is a system of $2024$ caves and $2023$ non-intersecting (bidirectional) corridors, each of which connects exactly two caves, where each pair of caves is connected through some sequence of corridors. Initially, Erik is standing in a corridor connecting some two caves. In a move, he can walk through one of the caves to another corridor that connects that cave to a third cave. However, when doing so, the corridor he was just in will magically disappear and get replaced by a new one connecting the end of his new corridor to the beginning of his old one (i.e., if Erik was in a corridor connecting caves $a$ and $b$ and he walked through cave $b$ into a corridor that connects caves $b$ and $c$, then the corridor between caves $a$ and $b$ will disappear and a new corridor between caves $a$ and $c$ will appear). Since Erik likes designing labyrinths and has a specific layout in mind for his next one, he is wondering whether he can transform the labyrinth into that layout using these moves. Prove that this is in fact possible, regardless of the original layout and his starting position there.

In a group of $n$ people, each one knows exactly three others. They are seated around a table. We say that the seating is $perfect$ if everyone knows the two sitting by their sides. Show that, if there is a perfect seating $S$ for the group, then there is always another perfect seating which cannot be obtained from $S$ by rotation or reflection.

Many people use the social network "BWM". It is known that: By choosing any four people of that network there always is one that is a friend of the other three. Is it then true that by choosing any four people there always is one that is a friend of everyone in "BWM"? [b]Note:[/b] If member $A$ is a friend of member $B$, then member $B$ also is a friend of member $A$.

Given $ n$ countries with three representatives each, $ m$ committees $ A(1),A(2), \ldots, A(m)$ are called a cycle if [i](i)[/i] each committee has $ n$ members, one from each country; [i](ii)[/i] no two committees have the same membership; [i](iii)[/i] for $ i \equal{} 1, 2, \ldots,m$, committee $ A(i)$ and committee $ A(i \plus{} 1)$ have no member in common, where $ A(m \plus{} 1)$ denotes $ A(1);$ [i](iv)[/i] if $ 1 < |i \minus{} j| < m \minus{} 1,$ then committees $ A(i)$ and $ A(j)$ have at least one member in common. Is it possible to have a cycle of 1990 committees with 11 countries?

At a university dinner, there are 2017 mathematicians who each order two distinct entrées, with no two mathematicians ordering the same pair of entrées. The cost of each entrée is equal to the number of mathematicians who ordered it, and the university pays for each mathematician's less expensive entrée (ties broken arbitrarily). Over all possible sets of orders, what is the maximum total amount the university could have paid? [i]Proposed by Evan Chen[/i]

Given $5$ points in a plane, no three of them being collinear. Each two of these $5$ points are joined with a segment, and every of these segments is painted either red or blue; assume that there is no triangle whose sides are segments of equal color. [b]a.)[/b] Show that: [i](1)[/i] Among the four segments originating at any of the $5$ points, two are red and two are blue. [i](2)[/i] The red segments form a closed way passing through all $5$ given points. (Similarly for the blue segments.) [b]b.)[/b] Give a plan how to paint the segments either red or blue in order to have the condition (no triangle with equally colored sides) satisfied.

In the plane we have $n$ rectangles with parallel sides. The sides of distinct rectangles lie on distinct lines. The boundaries of the rectangles cut the plane into connected regions. A region is [i]nice[/i] if it has at least one of the vertices of the $n$ rectangles on the boundary. Prove that the sum of the numbers of the vertices of all nice regions is less than $40n$. (There can be nonconvex regions as well as regions with more than one boundary curve.)

Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$.

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]

Given a graph with $n$ ($n\ge 4$) vertices . It is known that for any two vertices $A$ and $B$ there exists a vertex which is connected by edges both with $A$ and $B$. Find the smallest possible numbers of edges in the graph. E. Barabanov

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.

The city of Neverreturn has $N$ bus stops numbered $1, 2, \cdots , N.$ Each bus route is one-way and has only two stops, the beginning and the end. The route network is such that departing from any stop one cannot return to it using city buses. When the mayor notices a route going from a stop with a greater number to a stop with a lesser number, he orders to exchange the number plates of its beginning and its end. Can the plate changing go on infinitely? [i](K. Ivanov )[/i]

Let $G$ be a simple graph on $n$ vertices with at least one edge, and let us consider those $S:V(G)\to\mathbb R^{\ge 0}$ weighings of the vertices of the graph for which $\sum_{v\in V(G)} S(v)=1$. Furthermore define \[f(G)=\max_S\min_{(v,w)\in E(G)}S(v)S(w),\] where $S$ runs through all possible weighings. Prove that $f(G)=\frac1{n^2}$ if and only if the vertices of $G$ can be covered with a disjoint union of edges and odd cycles. ($V(G)$ denotes the vertices of graph $G$, $E(G)$ denotes the edges of graph $G$.)