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]

Let $A$ be a set of $n$ points in the space. From the family of all segments with endpoints in $A$, $q$ segments have been selected and colored yellow. Suppose that all yellow segments are of different length. Prove that there exists a polygonal line composed of $m$ yellow segments, where $m \geq \frac{2q}{n}$, arranged in order of increasing length.

There are $2024$ cities in a country, some pairs of which are connected by bidirectional flights. For any distinct cities $A, B, C, X, Y, Z$, it is possible to fly directly from some of the cities $A, B, C$ to some of the cities $X, Y, Z$. Prove that it is possible to plan a route $T_1\to T_2 \to \ldots \to T_{2022}$ that passes through $2022$ distinct cities. [i]Proposed by Lior Shayn[/i]

There are $24$ participants attended a meeting. Each two of them shook hands once or not. A total of $216$ handshakes occured in the meeting. For any two participants who have shaken hands, at most $10$ among the rest $22$ participants have shaken hands with exactly one of these two persons. Define a [i]friend circle[/i] to be a group of $3$ participants in which each person has shaken hands with the other two. Find the minimum possible value of friend circles.

Find all pairs of positive integers $(m, n)$, such that in a $m \times n$ table (with $m+1$ horizontal lines and $n+1$ vertical lines), a diagonal can be drawn in some unit squares (some unit squares may have no diagonals drawn, but two diagonals cannot be both drawn in a unit square), so that the obtained graph has an Eulerian cycle.

In a simple graph, there are two disjoint set of vertices $A$ and $B$ where $A$ has $k$ and $B$ has $2016$ vertices. Four numbers are written to each vertex using the colors red, green, blue and black. There is no any edge at the beginning. For each vertex in $A$, we first choose a color and then draw all edges from this vertex to the vertices in $B$ having a larger number with the chosen color. It is known that for each vertex in $B$, the set of vertices in $A$ connected to this vertex are different. Find the minimal possible value of $k$.

Let $ G$ be a $ 2$-connected nonbipartite graph on $ 2n$ vertices. Show that the vertex set of $ G$ can be split into two classes of $ n$ elements such that the edges joining the two classes form a connected, spanning subgraph. [i]L. Lovasz[/i]

What is the greatest possible number of edges in a planar graph with $12$ vertices? A planar graph is one that can be drawn in a plane with none of the edges crossing (they intersect only at vertices).

The edges of a graph with $2n$ vertices ($n \ge 4$) are colored in blue and red such that there is no blue triangle and there is no red complete subgraph with $n$ vertices. Find the least possible number of blue edges.

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 $m = 30030$ and let $M$ be the set of its positive divisors which have exactly $2$ prime factors. Determine the smallest positive integer $n$ with the following property: for any choice of $n$ numbers from $M$, there exist 3 numbers $a$, $b$, $c$ among them satisfying $abc=m$.

An $m \times n$ chessboard with $m,n \ge 2$ is given. Some dominoes are placed on the chessboard so that the following conditions are satisfied: (i) Each domino occupies two adjacent squares of the chessboard, (ii) It is not possible to put another domino onto the chessboard without overlapping, (iii) It is not possible to slide a domino horizontally or vertically without overlapping. Prove that the number of squares that are not covered by a domino is less than $\frac15 mn$.

We are given $k$ colors and we have to assign a single color to every vertex. An edge is [u][b]satisfied[/b][/u] if the vertices on that edge, are of different colors. [list] [*]Prove that you can always find an algorithm which assigns colors to vertices so that at least $\frac{k - 1}{k}|E|$ edges are satisfied where \(|E|\) is the cardinality of the edges in the graph.[/*] [*]Prove that there is a poly time deterministic algorithm for this [/*] [/list]

Alice and Bob are playing a game on a graph with $n\ge3$ vertices. At each moment, Alice needs to choose two vertices so that the graph is connected even if one of them (along with the edges incident to it) is removed. Each turn, Bob removes one edge in the graph, and upon the removal, Alice needs to re-select the two vertices if necessary. However, Bob has to guarantee that after each removal, any two vertices in the graph are still connected via at most $k$ intermediate vertices. Here $0\le k\le n-2$ is some given integer. Suppose that Bob always knows which two vertices Alice chooses, and that initially, the graph is a complete graph. Alice's objective is to change her choice of the two vertices as few times as possible, and Bob's objective is to make Alive re-select as many times as possible. If both Alice and Bob are sufficiently smart, how many times will Alice change her choice of the two vertices? (usjl)

Alex is trying to open a lock whose code is a sequence that is three letters long, with each of the letters being one of $\text A$, $\text B$ or $\text C$, possibly repeated. The lock has three buttons, labeled $\text A$, $\text B$ and $\text C$. When the most recent $3$ button-presses form the code, the lock opens. What is the minimum number of total button presses Alex needs to guarantee opening the lock?

The edges of a graph with $2n$ vertices ($n \ge 4$) are colored in blue and red such that there is no blue triangle and there is no red complete subgraph with $n$ vertices. Find the least possible number of blue edges.

Let $ n \geq 3$ and consider a set $ E$ of $ 2n \minus{} 1$ distinct points on a circle. Suppose that exactly $ k$ of these points are to be colored black. Such a coloring is [b]good[/b] if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly $ n$ points from $ E$. Find the smallest value of $ k$ so that every such coloring of $ k$ points of $ E$ is good.

Show that the length of a cycle that contains every edge of a connected graph is at most the sum between the vertices and nodes of the graph, minus $ 1. $

Some cities in country are connected by road, and from every city goes $\geq 2008$ roads. Every road is colored in one of two colors. Prove, that exists cycle without self-intersections ,where $\geq 504$ roads and all roads are same color.

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

There are 15 people at a party; each person has 10 friends. To greet each other each person hugs all their friends. How many hugs are exchanged at this party?

[list=1] [*] Let $G$ be a $(4, 4)$ unoriented graph, 2-regulate, containing a cycle with the length 3. Find the characteristic polynomial $P_G (\lambda)$ , its spectrum $Spec (G)$ and draw the graph $G$. [*] Let $G'$ be another 2-regulate graph, having its characteristic polynomial $P_{G'} (\lambda) = \lambda^4 - 4\lambda^2 + \alpha, \alpha \in \mathbb{R}$. Find the spectrum $Spec(G')$ and draw the graph $G'$. [*] Are the graphs $G$ and $G'$ cospectral or isomorphic? [/list]

[b](i)[/b] Determine the smallest number of edges which a graph of $ n$ nodes may have given that adding an arbitrary new edge would give rise to a 3-clique (3 nodes joined pairwise by edges). [b](ii)[/b] Determine the smallest number of edges which a graph of $ n$ nodes may have given that adding an arbitrary new edge would give rise to a 4-clique (4 nodes joined pairwise by edges).

There are $n \geq 3$ islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route. After each year, the ferry company will close a ferry route between some two islands $X$ and $Y$. At the same time, in order to maintain its service, the company will open new routes according to the following rule: for any island which is connected to a ferry route to exactly one of $X$ and $Y$, a new route between this island and the other of $X$ and $Y$ is added. Suppose at any moment, if we partition all islands into two nonempty groups in any way, then it is known that the ferry company will close a certain route connecting two islands from the two groups after some years. Prove that after some years there will be an island which is connected to all other islands by ferry routes.

Prove that for any finite graph G there is a constant c(G)>0 such that for every n-point graph that does not have an induced subgraph isomorphic to G, there are two disjoint sets of vertices, each with at least $n^{c(G)}$ elements, between which either all edges are connected, or none of the edges are.