Initially $A$ selects a graph with \( 2221 \) vertices such that each vertex is incident to at least one edge. Then $B$ deletes some of the edges (possibly none) from the chosen graph. Finally, $A$ pays $B$ one lev for each vertex that is incident to an odd number of edges. What is the maximum amount that $B$ can guarantee to earn?

Let $k\leq n$ be two positive integers. IMO-nation has $n$ villages, some of which are connected by a road. For any two villages, the distance between them is the minimum number of toads that one needs to travel from one of the villages to the other, if the traveling is impossible, then the distance is set as infinite. Alice, who just arrived IMO-nation, is doing her quarantine in some place, so she does not know the configuration of roads, but she knows $n$ and $k$. She wants to know whether the furthest two villages have finite distance. To do so, for every phone call she dials to the IMO office, she can choose two villages, and ask the office whether the distance between them is larger than, equal to, or smaller than $k$. The office answers faithfully (infinite distance is larger than $k$). Prove that Alice can know whether the furthest two villages have finite distance between them in at most $2n^2/k$ calls. [i]Proposed by usjl and Cheng-Ying Chang[/i]

In a graph with $2n-1$ vertices throwing out any vertex the remaining graph has a complete subgraph with $n$ vertices. Prove that the initial graph has a complete subgraph with $n+1$ vertices.

Given $n$ sets $A_i$, with $| A_i | = n$, prove they may be indexed $A_i = \{a_{i,j} \mid j=1,2,\ldots,n \}$, in such way that the sets $B_j = \{a_{i,j} \mid i=1,2,\ldots,n \}$, $1\leq j\leq n$, also have $| B_j | = n$. (Anonymous)

Let be a structure formed by $ n\ge 4 $ points in space, four by four noncoplanar, and two by two connected by a wire. If we cut the $ n-1 $ wires that connect a point to the others, the remaining point is said to be [i]isolated.[/i] The structure is said to be [i]disconnected[/i] if there are at least two points for which there isn´t a chain of wires connecting them. So, initially, it´s not disconnected. $ \text{(1)} $ Prove that, by cutting a number smaller or equal with $ n-2, $ the structure won´t become disconnected. $ \text{(2)} $ Determine the minimum number of wires that needs to be cut so that the remaining structure is disconnected, yet every point, not isloated.

A tree $T$ is given. Starting with the complete graph on $n$ vertices, subgraphs isomorphic to $T$ are erased at random until no such subgraph remains. For what trees does there exist a positive constant $c$ such that the expected number of edges remaining is at least $cn^2$ for all positive integers $n$? [i]David Yang.[/i]

In a country, there are towns, some of which are connected by roads. There is a route (not necessarily direct) between every two towns. The Minister of Education has ensured that every town without a school is connected via a direct road to a town that has a school. The Minister of State Optimization wants to ensure that there is a unique path between any two towns (without repeating traveled segments), which may require removing some roads. Is it always possible to achieve this without constructing additional schools while preserving what the Minister of Education has accomplished?

Six cities $A, B, C, D, E$, and $F$ are located on the vertices of a regular hexagon in that order. $G$ is the center of the hexagon. The sides of the hexagon are the roads connecting these cities. Further more, there are roads connecting cities $B, C, E, F$ and $G$, respectively. Because of raining, one or more roads maybe destroyed. The probability of the road keeping undestroyed between two consecutive cities is $p$. Determine the probability of the road between cities $A$ and $D$ is undestroyed.

In a group of $2n$ students, each student has exactly $3$ friends within the group. The friendships are mutual and for each two students $A$ and $B$ which are not friends, there is a sequence $C_1, C_2, ..., C_r$ of students such that $A$ is a friend of $C_1$, $C_1$ is a friend of $C_2$, et cetera, and $C_r$ is a friend of $B$. Every student was asked to assess each of his three friendships with: "acquaintance", "friend" and "BFF". It turned out that each student either gave the same assessment to all of his friends or gave every assessment exactly once. We say that a pair of students is in conflict if they gave each other different assessments. Let $D$ be the set of all possible values of the total number of conflicts. Prove that $|D| \geq 3n$ with equality if and only if the group can be partitioned into two subsets such that each student is separated from all of his friends.

Let $G$ be an arbitrarily chosen finite simple graph. We write non-negative integers on the vertices of the graph such that for each vertex $v$ in $G,$ the number written on $v$ is equal to the number of vertices adjacent to $v$ where an even number is written. Prove that the number of ways to achieve this is a power of $2$.

A social network has $2019$ users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time: [list] [*] Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged. [/list] Initially, $1010$ users have $1009$ friends each, and $1009$ users have $1010$ friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user. [i]Proposed by Adrian Beker, Croatia[/i]

The plane is divided into regions by $ n \ge 3$ lines, no two of which are parallel, and no three of which are concurrent. Some regions are coloured , in such a way that no two coloured regions share a common segment or half-line of their borders. Prove that the number of coloured regions is at most $ \frac{n(n\plus{}1)}{3}$

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$

Let $M$ be a positive integer. At a party with 120 people, 30 wear red hats, 40 wear blue hats, and 50 wear green hats. Before the party begins, $M$ pairs of people are friends. (Friendship is mutual.) Suppose also that no two friends wear the same colored hat to the party. During the party, $X$ and $Y$ can become friends if and only if the following two conditions hold: [list] [*] There exists a person $Z$ such that $X$ and $Y$ are both friends with $Z$. (The friendship(s) between $Z,X$ and $Z,Y$ could have been formed during the party.) [*] $X$ and $Y$ are not wearing the same colored hat. [/list] Suppose the party lasts long enough so that all possible friendships are formed. Let $M_1$ be the largest value of $M$ such that regardless of which $M$ pairs of people are friends before the party, there will always be at least one pair of people $X$ and $Y$ with different colored hats who are not friends after the party. Let $M_2$ be the smallest value of $M$ such that regardless of which $M$ pairs of people are friends before the party, every pair of people $X$ and $Y$ with different colored hats are friends after the party. Find $M_1+M_2$. [hide="Clarifications"] [list] [*] The definition of $M_2$ should read, ``Let $M_2$ be the [i]smallest[/i] value of $M$ such that...''. An earlier version of the test read ``largest value of $M$''.[/list][/hide] [i]Victor Wang[/i]

Consider a computer network consisting of servers and bi-directional communication channels among them. Unfortunately, not all channels operate. Each direction of each channel fails with probability $p$ and operates otherwise. (All of these stochastic events are mutually independent, and $0 \le p \le 1$.) There is a root serve, denoted by $r$. We call the network [i]operational[/i], if all serves can reach $r$ using only operating channels. Note that we do not require $r$ to be able to reach any servers. Show that the probability of the network to be operational does not depend on the choice of $r$. (In other words, for any two distinct root servers $r_1$ and $r_2$, the operational probability is the same.)

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 if a person a has infinitely many descendants (children, their children, etc.), then a has an infinite sequence $a_0, a_1, \ldots$ of descendants (i.e., $a = a_0$ and for all $n \geq 1, a_{n+1}$ is always a child of $a_n$). It is assumed that no-one can have infinitely many children. [i]Variant 1[/i]. Prove that if $a$ has infinitely many ancestors, then $a$ has an infinite descending sequence of ancestors (i.e., $a_0, a_1, \ldots$ where $a = a_0$ and $a_n$ is always a child of $a_{n+1}$). [i]Variant 2.[/i] Prove that if someone has infinitely many ancestors, then all people cannot descend from $A(dam)$ and $E(ve)$.

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.

A Magician and a Detective play a game. The Magician lays down cards numbered from $1$ to $52$ face-down on a table. On each move, the Detective can point to two cards and inquire if the numbers on them are consecutive. The Magician replies truthfully. After a finite number of moves, the Detective points to two cards. She wins if the numbers on these two cards are consecutive, and loses otherwise. Prove that the Detective can guarantee a win if and only if she is allowed to ask at least $50$ questions. [i]Proposed by Anant Mudgal[/i]

Consider $9$ points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of $\,n\,$ such that whenever exactly $\,n\,$ edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

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.

For a positive integer \( n \geq 6 \), find the smallest integer \( S(n) \) such that any graph with \( n \) vertices and at least \( S(n) \) edges must contain at least two disjoint cycles (cycles with no common vertices).

Let T be a finite tree graph that has more than one vertex. Let s be the largest number of vertices of a subtree $X \subset T$ for which every vertex of X has a neighbor other than X. Let t be the smallest positive integer for which each edge of T is contained in exactly t stars, and each vertex of T is contained in at most 2t - 1 stars. (That is, the stars can be represented by multiplicity.) Prove that s = t. Note: a star of T is a vertex with degree $\geq$ 3 , including its neighouring edges and vertices.

Let $G = (S, T; E)$ be a finite bipartite graph with a perfect matching. Prove that there exists an injective edge weighting $w: E \to \mathbb{R}$ satisfying the following: 1. If $e_s$ is the edge with the smallest weight among the edges incident to $s$ for all $s \in S$, then $\{ e_s \mid s \in S \}$ forms a perfect matching in $G$. 2. If $e_t$ is the edge with the largest weight among the edges incident to $t$ for all $t \in T$, then $\{ e_t \mid t \in T \}$ forms a perfect matching in $G$.

$S=\{1,2,...,N\}$. $A_1,A_2,A_3,A_4\subseteq S$, each having cardinality $500$. $\forall x,y\in S$, $\exists i\in\{1,2,3,4\}$, $x,y\in A_i$. Determine the maximal value of $N$.