In a country with $2015$ cities there is exactly one two-way flight between each city. The three flights made between three cities belong to at most two different airline companies. No matter how the flights are shared between some number of companies, if there is always a city in which $k$ flights belong to the same airline, what is the maximum 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.

A [i]cactus[/i] is a finite simple connected graph where no two cycles share an edge. Show that in a nonempty cactus, there must exist a vertex which is part of at most one cycle. [i]Kevin Yang[/i]

There are $6$ computers(power off) and $3$ printers. Between a printer and a computer, they are connected with a wire or not. Printer can be only activated if and only if at least one of the connected computer's power is on. Your goal is to connect wires in such a way that, no matter how you choose three computers to turn on among the six, you can activate all $3$ printers. What is the minimum number of wires required to make this possible?

Let $n\ge 2$ be a positive integer. $S$ is a set of $2n$ airports. For two arbitrary airports $A,B$, if there is an airway from $A$ to $B$, then there is an airway from $B$ to $A$. Suppose that $S$ has only one independent set of $n$ airports. Let the independent set $X$. Prove that there exists an airport $P\in S\setminus X$ which satisfies following condition. [b]Condition[/b] : For two arbitrary distinct airports $A,B\in S\setminus \{P\}$, if there exists a path connecting $A$ and $B$, then there exists a path connecting $A$ and $B$ which does not pass $P$.

We label every edge of a simple graph with the difference of the degrees of its endpoints. If the number of vertices is $N$, what can be the largest value of the sum of the labels on the edges? [i]Proposed by Dániel Lenger and Gábor Szűcs, Budapest[/i]

In connection with the formation of a stable government, the President invited all $240$ Members of Parliament to three separate consultations, where each member participated in exactly one consultation, and at each consultation there has been at least one member present. Discussions between pairs of members are to take place to discuss the consultations. Is it possible for these discussions to occur in such a way that there exists a non-negative integer $k$, such that for every two members who participated in different consultations, there are exactly $k$ members who participated in the remaining consultation, with whom each of the two members has a conversation, and exactly $k$ members who participated in the remaining consultation, with whom neither of the two has a conversation? If yes, then find all possible values of $k$.

In a group of nine persons it is not possible to choose four persons such that every one knows the three others. Prove that this group of nine persons can be partitioned into four groups such that nobody knows anyone from his or her group.

Let $n$ and $\ell$ be integers such that $n \ge 3$ and $1 < \ell < n$. A country has $n$ cities. Between any two cities $A$ and $B$, either there is no flight from $A$ to $B$ and also none from $B$ to $A$, or there is a unique [i]two-way trip[/i] between them. A [i]two-way trip[/i] is a flight from $A$ to $B$ and a flight from $B$ to $A$. There exist two cities such that the least possible number of flights required to travel from one of them to the other is $\ell$. Find the maximum number of two-way trips among the $n$ cities.

There is an integer $n > 1$. There are $n^2$ stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, $A$ and $B$, operates $k$ cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The $k$ cable cars of $A$ have $k$ different starting points and $k$ different finishing points, and a cable car which starts higher also finishes higher. The same conditions hold for $B$. We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed). Determine the smallest positive integer $k$ for which one can guarantee that there are two stations that are linked by both companies. [i]Proposed by Tejaswi Navilarekallu, India[/i]

Let $n$ be a natural number. The graph $G$ has $10n$ vertices. They are separated into $10$ groups with $n$ vertices and we know that there is an edge between two of them if and only if they belong to two different groups. What’s the greatest number of edges a subgraph of $G$ can have, so that there are no 4-cliques in it?

Given a graph with $99$ vertices and degrees in $\{81,82,\dots,90\}$, prove that there exist $10$ vertices of this graph with equal degrees and a common neighbour. [i]Proposed by Alireza Alipour[/i]

There are $n\geq 3$ cities in a country and between any two cities $A$ and $B$, there is either a one way road from $A$ to $B$, or a one way road from $B$ to $A$ (but never both). Assume the roads are built such that it is possible to get from any city to any other city through these roads, and define $d(A,B)$ to be the minimum number of roads you must go through to go from city $A$ to $B$. Consider all possible ways to build the roads. Find the minimum possible average value of $d(A,B)$ over all possible ordered pairs of distinct cities in the country.

A 2-player game is played on $n\geq 3$ points, where no 3 points are collinear. Each move consists of selecting 2 of the points and drawing a new line segment connecting them. The first player to draw a line segment that creates an odd cycle loses. (An odd cycle must have all its vertices among the $n$ points from the start, so the vertices of the cycle cannot be the intersections of the lines drawn.) Find all $n$ such that the player to move first wins.

Among a group of 120 people, some pairs are friends. A [i]weak quartet[/i] is a set of four people containing exactly one pair of friends. What is the maximum possible number of weak quartets ?

The columns and the row of a $3n \times 3n$ square board are numbered $1,2,\ldots ,3n$. Every square $(x,y)$ with $1 \leq x,y \leq 3n$ is colored asparagus, byzantium or citrine according as the modulo $3$ remainder of $x+y$ is $0,1$ or $2$ respectively. One token colored asparagus, byzantium or citrine is placed on each square, so that there are $3n^2$ tokens of each color. Suppose that one can permute the tokens so that each token is moved to a distance of at most $d$ from its original position, each asparagus token replaces a byzantium token, each byzantium token replaces a citrine token, and each citrine token replaces an asparagus token. Prove that it is possible to permute the tokens so that each token is moved to a distance of at most $d+2$ from its original position, and each square contains a token with the same color as the square.

Given positive integers $d \ge 3$, $r>2$ and $l$, with $2d \le l <rd$. Every vertice of the graph $G(V,E)$ is assigned to a positive integer in $\{1,2,\cdots,l\}$, such that for any two consecutive vertices in the graph, the integers they are assigned to, respectively, have difference no less than $d$, and no more than $l-d$. A proper coloring of the graph is a coloring of the vertices, such that any two consecutive vertices are not the same color. It's given that there exist a proper subset $A$ of $V$, such that for $G$'s any proper coloring with $r-1$ colors, and for an arbitrary color $C$, either all numbers in color $C$ appear in $A$, or none of the numbers in color $C$ appear in $A$. Show that $G$ has a proper coloring within $r-1$ colors.

Simple graph $G$ has $19998$ vertices. For any subgraph $\bar G$ of $G$ with $9999$ vertices, $\bar G$ has at least $9999$ edges. Find the minimum number of edges in $G$

Some of $100$ towns of a kingdom are connected by roads.It is known that for each two towns $A$ and $B$ connected by a road there is a town $C$ which is not connected by a road with at least one of the towns $A$ and $B$. Determine the maximum possible number of roads in the kingdom.

We call a pair of distinct numbers $(a, b)$ a [i]binary pair[/i] if $ab+1$ is a power of two. Given a set $S$ of $n$ positive integers, what is the maximum possible numbers of binary pairs in S?

A regular $2004$-sided polygon is given, with all of its diagonals drawn. After some sides and diagonals are removed, every vertex has at most five segments coming out of it. Prove that one can color the vertices with two colors such that at least $\frac{3}{5}$ of the remaining segments have ends with different colors.

On every card of a deck of cards a regular 17-gon is displayed with all sides and diagonals, and the vertices are numbered from 1 through 17. On every card all edges (sides and diagonals) are colored with a color 1,2,...,105 such that the following property holds: for every 15 vertices of the 17-gon the 105 edges connecting these vertices are colored with different colors on at least one of the cards. What is the minimum number of cards in the deck?

Let $T$ be a tree with$ n$ vertices. Choose a positive integer $k$ where $1 \le k \le n$ such that $S_k$ is a subset with $k$ elements from the vertices in $T$. For all $S \in S_k$, define $c(S)$ to be the number of component of graph from $S$ if we erase all vertices and edges in $T$, except all vertices and edges in $S$. Determine $\sum_{S\in S_k} c(S)$, expressed in terms of $n$ and $k$.

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 are $k$ cities in Belarus and $k$ cities in Armenia, between some cities there are non-directed flights. From any Belarusian city there are exactly $n$ flights to Armenian cities, and for every pair of Armenian cities exactly two Belarusian cities have flights to both of the Armenian cities. a) Prove that from every Armenian city there are exactly $n$ flights to Belarusian cities. b) Prove that there exists a flight route in which every city is visited at most once and that consists of at least $\lfloor \frac{(n+1)^2}{4} \rfloor$ cities in each of the countries. [i]D. Gorovoy[/i]