Let $ G$ be an infinite graph such that for any countably infinite vertex set $ A$ there is a vertex $ p$, not in $A$, joined to infinitely many elements of $ A$. Show that $ G$ has a countably infinite vertex set $ A$ such that $ G$ contains uncountably infinitely many vertices $ p$ joined to infinitely many elements of $ A$. [i]P. Erdos, A. Hajnal[/i]

Define a [i]domino[/i] to be an ordered pair of [i]distinct[/i] positive integers. A [i]proper sequence[/i] of dominoes is a list of distinct dominoes in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i, j)$ and $(j, i)$ do not [i]both[/i] appear for any $i$ and $j$. Let $D_n$ be the set of all dominoes whose coordinates are no larger than $n$. Find the length of the longest proper sequence of dominoes that can be formed using the dominoes of $D_n$.

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.

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

Ten localities are served by two international airlines such that there exists a direct service (without stops) between any two of these localities and all airline schedules offer round-trip service between the cities they serve. Prove that at least one of the airlines can offer two disjoint round trips each containing an odd number of landings.

Can the set of lattice points $\{(x, y) \mid x, y \in \mathbb{Z}, 1 \le x, y \le 252, x \neq y\}$ be colored using 10 distinct colors such that for all $a \neq b$, $b \neq c$, the colors of $(a, b)$ and $(b, c)$ are distinct?

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.

Given distinct positive integers \( g \) and \( h \), let all integer points on the number line \( OX \) be vertices. Define a directed graph \( G \) as follows: for any integer point \( x \), \( x \rightarrow x + g \), \( x \rightarrow x - h \). For integers \( k, l (k < l) \), let \( G[k, l] \) denote the subgraph of \( G \) with vertices limited to the interval \([k, l]\). Find the largest positive integer \( \alpha \) such that for any integer \( r \), the subgraph \( G[r, r + \alpha - 1] \) of \( G \) is acyclic. Clarify the structure of subgraphs \( G[r, r + \alpha - 1] \) and \( G[r, r + \alpha] \) (i.e., how many connected components and what each component is like).

Consider a round-robin tournament with $2n+1$ teams, where each team plays each other team exactly one. We say that three teams $X,Y$ and $Z$, form a [i]cycle triplet [/i] if $X$ beats $Y$, $Y$ beats $Z$ and $Z$ beats $X$. There are no ties. a)Determine the minimum number of cycle triplets possible. b)Determine the maximum number of cycle triplets possible.

In a company of $6$ sousliks each souslik has $4$ friends. Is it always possible to divide this company into two groups of $3$ sousliks such that in both groups all sousliks are friends?

Consider a natural number $n\geqslant 3$ and a graph $G{}$ with a chromatic number $\chi(G)=n$ which has more than $n{}$ vertices. Prove that there exist two vertex-disjoint subgraphs $G_1{}$ and $G_2{}$ of $G{}$ such that $\chi(G_1)+\chi(G_2)\geqslant n+1.$ [i]Proposed by V. Dolnikov[/i]

Juty and Azgor plays the following game on a \((2n+1) \times (2n+1)\) board with Juty moving first. Initially all cells are colored white. On Juty's turn, she colors a white cell green and on Azgor's turn, he colors a white cell red. The game ends after they color all the cells of the board. Juty wins if all the green cells are connected, i.e. given any two green cells, there is at least one chain of neighbouring green cells connecting them (we call two cells [i]neighboring[/i] if they share at least one corner), otherwise Azgor wins. Determine which player has a winning strategy. [i]Proposed by Atonu Roy Chowdhury[/i]

Let $A$ be a subset of the edges of an $n\times n $ table. Let $V(A)$ be the set of vertices from the table which are connected to at least on edge from $A$ and $j(A)$ be the number of the connected components of graph $G$ which it's vertices are the set $V(A)$ and it's edges are the set $A$. Prove that for every natural number $l$: $$\frac{l}{2}\leq min_{|A|\geq l}(|V(A)|-j(A)) \leq \frac{l}{2}+\sqrt{\frac{l}{2}}+1$$

Six points are connected in pairs by lines, each of which is either red or blue. Every pair of points is joined. Determine whether there must be a closed path having four sides all of the same colour. (A path is closed if it begins and ends at the same point.)

Let $n(\ge 2)$ be an integer. $2n^2$ contestants participate in a Chinese chess competition, where any two contestant play exactly once. There may be draws. It is known that (1)If A wins B and B wins C, then A wins C. (2)there are at most $\frac{n^3}{16}$ draws. Proof that it is possible to choose $n^2$ contestants and label them $P_{ij}(1\le i,j\le n)$, so that for any $i,j,i',j'\in \{1,2,...,n\}$, if $i<i'$, then $P_{ij}$ wins $P_{i'j'}$.

Consider any graph with $50$ vertices and $225$ edges. We say that a triplet of its (mutually distinct) vertices is [i]connected[/i] if the three vertices determine at least two edges. Determine the smallest and the largest possible number of connected triples. [i](Jan Mazak, Josef Tkadlec)[/i]

In a group of kids there are $2022$ boys and $2023$ girls. Every girl is a friend with exactly $2021$ boys. Friendship is a symmetric relation: if A is a friend of B, then B is also a friend of A. Prove that it is not possible that all boys have the same number of girl friends. [i]Proposed by the JMMO Problem Selection Committee[/i]

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.

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

The Imomi archipelago consists of $n\geq 2$ islands. Between each pair of distinct islands is a unique ferry line that runs in both directions, and each ferry line is operated by one of $k$ companies. It is known that if any one of the $k$ companies closes all its ferry lines, then it becomes impossible for a traveller, no matter where the traveller starts at, to visit all the islands exactly once (in particular, not returning to the island the traveller started at). Determine the maximal possible value of $k$ in terms of $n$. [i]Anton Trygub, Ukraine[/i]

There are $3\leq n\leq 25$ passengers in a bus some of which are friends. Every passenger has exactly $k$ friends among the passengers, no two friends have a common friend and every two people, who are not friends have a common friend. Find $n$.

In a country every two towns are connected by exactly one one-way road. Each road is intended either for cars or for cyclists. The roads cross only in towns, otherwise interchanges are used as road junctions. Show that there is a town from which you can go to any other town without changing the means of transport.

Let \(L_3 = \{3\}\), \(L_n = \{3, 4, \ldots, h\}\) (where \(h > 3\)). For any given integer \(n \geq 3\), consider a graph \(G\) with \(n\) vertices that contains a Hamiltonian cycle \(C\) and has more than \(\frac{n^2}{4}\) edges. For which lengths \(l \in L_n\) must the graph \(G\) necessarily contain a cycle of length \(l\)?

Given a graph with $n$ vertices and a positive integer $m$ that is less than $ n$, prove that the graph contains a set of $m+1$ vertices in which the difference between the largest degree of any vertex in the set and the smallest degree of any vertex in the set is at most $m-1.$

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