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$ be an integer with $n\geq 3$ and assume that $2n$ vertices of a regular $(4n + 1)-$gon are coloured. Show that there must exist three of the coloured vertices forming an isosceles triangle.

At an IMOTC party, all people have pairwise distinct ages. Some pairs of people are friends and friendship is mutual. Call a person [i]junior[/i] if they are younger than all their friends, and [i]senior[/i] if they are older than all their friends. A person with no friends is both [i]junior[/i] and [i]senior[/i]. A sequence of pairwise distinct people $A_1, \dots, A_m$ is called [i]photogenic[/i] if: 1. $A_1$ is [i]junior[/i], 2. $A_m$ is [i]senior[/i], and 3. $A_i$ and $A_{i+1}$ are friends, and $A_{i+1}$ is older than $A_i$ for all $1 \leq i \leq m-1$. Let $k$ be a positive integer such that for every [i]photogenic[/i] sequence $A_1, \dots, A_m$, $m$ is not divisible by $k$. Prove that the people at the party can be partitioned into $k$ groups so that no two people in the same group are friends. [i]Proposed by Shantanu Nene[/i]

We are given $n$ intervals $[l_1,r_1],[l_2,r_2],[l_3,r_3],\dots, [l_n,r_n]$ in the number line. We can divide the intervals into two sets such that no two intervals in the same set have overlaps. Prove that there are at most $n-1$ pairs of overlapping intervals.

In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is defined to be the least possible numbers of flights required to go from one of them to the other. It is known that for any city there are at most $100$ cities at distance exactly three from it. Prove that there is no city such that more than $2550$ other cities have distance exactly four from it.

A weighted complete graph with distinct positive wights is given such that in every triangle is [i]degenerate [/i] that is wight of an edge is equal to sum of two other. Prove that one can assign values to the vertexes of this graph such that the wight of each edge is the difference between two assigned values of the endpoints. [i]Proposed by Morteza Saghafian [/i]

At a company, there are several workers, some of which are enemies. They go to their job with 100 buses, in such a way that there aren't any enemies in either bus. Having arrived at the job, their chief wants to assign them to brigades of at least two people, without assigning two enemies to the same brigade. Prove that the chief can split the workers in at most 100 brigades, or he cannot split them at all in any number of brigades.

33 friends are collecting stickers for a 2011-sticker album. A distribution of stickers among the 33 friends is incomplete when there is a sticker that no friend has. Determine the least $m$ with the following property: every distribution of stickers among the 33 friends such that, for any two friends, there are at least $m$ stickers both don't have, is incomplete.

Define a class of graphs $G_k$ for each positive integer k as follows. A graph G = ( V , E ) is an element of $G_k$ if and only if there exists an edge coloring $\psi: E\to [ k ] = \{1,2, ..., k\}$ such that for all vertex coloring $\phi: V\to [ k ]$ there exist an edge e = { x , y } such that $\phi ( x ) = \phi( y ) = \psi( e )$. Prove that there exist $c_1< c_2$ positive constants with the following two properties: (i) each graph in $G_k$ has at least $c_1 k^2$ vertices; (ii) there is a graph in $G_k$ which has at most $c_2 k^2$ vertices.

Numbers 1 and −1 are written in the cells of a board 2000×2000. It is known that the sum of all the numbers in the board is positive. Show that one can select 1000 rows and 1000 columns such that the sum of numbers written in their intersection cells is at least 1000. [i]D. Karpov[/i]

Let $m$ and $n$ be positive integers. Some squares of an $m \times n$ board are coloured red. A sequence $a_1, a_2, \ldots , a_{2r}$ of $2r \ge 4$ pairwise distinct red squares is called a [i]bishop circuit[/i] if for every $k \in \{1, \ldots , 2r \}$, the squares $a_k$ and $a_{k+1}$ lie on a diagonal, but the squares $a_k$ and $a_{k+2}$ do not lie on a diagonal (here $a_{2r+1}=a_1$ and $a_{2r+2}=a_2$). In terms of $m$ and $n$, determine the maximum possible number of red squares on an $m \times n$ board without a bishop circuit. ([i]Remark.[/i] Two squares lie on a diagonal if the line passing through their centres intersects the sides of the board at an angle of $45^\circ$.)

A school has three classes. Some pairs of children from different classes are enemies (there are no enemies in a class). It is known that every child from the first class has as many enemies in the second class as in the third; the same is true for other classes. Prove that the number of pairs of children from classes having a common enemy is not less than the number of pairs of children being enemies.

Gourmet Jan compared $n$ restaurants ($n$ is a positive integer). Each pair of restaurants was compared in two categories: tastiness of food and quality of service. For some pairs Jan couldn't tell which restaurant was better in one category, but never in two categories. Moreover, if Jan thought restaurant $A$ was better than restaurant $B$ in one category and restaurant $B$ was better than restaurant $C$ in the same category, then $A$ is also better than $C$ in that category. Prove there exists a restaurant $R$ such that every other restaurant is worse than $R$ in at least one category.

Let $n$ and $k$ be two positive integers. Consider a group of $k$ people such that, for each group of $n$ people, there is a $(n+1)$-th person that knows them all (if $A$ knows $B$ then $B$ knows $A$). 1) If $k=2n+1$, prove that there exists a person who knows all others. 2) If $k=2n+2$, give an example of such a group in which no-one knows all others.

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.

Let $ m,n$ be two integers such that $ \varphi(m) \equal{}\varphi(n) \equal{} c$. Prove that there exist natural numbers $ b_{1},b_{2},\dots,b_{c}$ such that $ \{b_{1},b_{2},\dots,b_{c}\}$ is a reduced residue system with both $ m$ and $ n$.

Is it possible to place the numbers $0,1,2,\dots,9$ on a circle so that the sum of any three consecutive numbers is a) 13, b) 14, c) 15?

Let $G$ be a finite graph. Prove that one can partition $G$ into two graphs $A \cup B=G$ such that if we erase all edges conecting a vertex from $A$ to a vertex from $B$, each vertex of the new graph has even degree.

Let $n \geq 2$ be a given integer $a)$ Prove that one can arrange all the subsets of the set $\{1,2... ,n\}$ as a sequence of subsets $A_{1}, A_{2},\cdots , A_{2^{n}}$, such that $|A_{i+1}| = |A_{i}| + 1$ or $|A_{i}| - 1$ where $i = 1,2,3,\cdots , 2^{n}$ and $A_{2^{n} + 1} = A_{1}$ $b)$ Determine all possible values of the sum $\sum \limits_{i = 1}^{2^n} (-1)^{i}S(A_{i})$ where $S(A_{i})$ denotes the sum of all elements in $A_{i}$ and $S(\emptyset) = 0$, for any subset sequence $A_{1},A_{2},\cdots ,A_{2^n}$ satisfying the condition in $a)$

Let $n$ be an even positive integer, and let $G$ be an $n$-vertex graph with exactly $\tfrac{n^2}{4}$ edges, where there are no loops or multiple edges (each unordered pair of distinct vertices is joined by either 0 or 1 edge). An unordered pair of distinct vertices $\{x,y\}$ is said to be [i]amicable[/i] if they have a common neighbor (there is a vertex $z$ such that $xz$ and $yz$ are both edges). Prove that $G$ has at least $2\textstyle\binom{n/2}{2}$ pairs of vertices which are amicable. [i]Zoltán Füredi (suggested by Po-Shen Loh)[/i]

There are $n$ $(n \ge 3)$ players in a table tennis tournament, in which any two players have a match. Player $A$ is called not out-performed by player $B$, if at least one of player $A$'s losers is not a $B$'s loser. Determine, with proof, all possible values of $n$, such that the following case could happen: after finishing all the matches, every player is not out-performed by any other player.

In country there are some cities, some pairs of cities are connected with roads.From every city go out exactly $100$ roads. We call $10$ roads, that go out from same city, as bunch. Prove, that we can split all roads in several bunches.

A sequence of vertices $v_1,v_2,\ldots,v_k$ in a graph, where $v_i=v_j$ only if $i=j$ and $k$ can be any positive integer, is called a $\textit{cycle}$ if $v_1$ is attached by an edge to $v_2$, $v_2$ to $v_3$, and so on to $v_k$ connected to $v_1$. Rotations and reflections are distinct: $A,B,C$ is distinct from $A,C,B$ and $B,C,A$. Supposed a simple graph $G$ has $2013$ vertices and $3013$ edges. What is the minimal number of cycles possible in $G$?

Fix a positive integer $n$ and a finite graph with at least one edge; the endpoints of each edge are distinct, and any two vertices are joined by at most one edge. Vertices and edges are assigned (not necessarily distinct) numbers in the range from $0$ to $n-1$, one number each. A vertex assignment and an edge assignment are [i]compatible[/i] if the following condition is satisfied at each vertex $v$: The number assigned to $v$ is congruent modulo $n$ to the sum of the numbers assigned to the edges incident to $v$. Fix a vertex assignment and let $N$ be the total number of compatible edge assignments; compatibility refers, of course, to the fixed vertex assignment. Prove that, if $N \neq 0$, then the prime divisors of $N$ are all at most $n$.

In Wonderland, the towns are connected by roads, and whenever there is a direct road between two towns there is also a route between these two towns that does not use that road. (There is at most one direct road between any two towns.) The Queen of Hearts ordered the Spades to provide a list of all ”even” subsystems of the system of roads, that is, systems formed by subsets of the set of roads, where each town is connected to an even number of roads (possibly none). For each such subsystem they should list its roads. If there are totally $n$ roads in Wonderland and $x$ subsystems on the Spades’ list, what is the number of roads on their list when each road is counted as many times as it is listed?