Found problems: 31
1992 IMO Longlists, 20
Let $X$ and $Y$ be two sets of points in the plane and $M$ be a set of segments connecting points from $X$ and $Y$ . Let $k$ be a natural number. Prove that the segments from $M$ can be painted using $k$ colors in such a way that for any point $x \in X \cup Y$ and two colors $\alpha$ and $\beta$ $(\alpha \neq \beta)$, the difference between the number of $\alpha$-colored segments and the number of $\beta$-colored segments originating in $X$ is less than or equal to $1$.
1987 IMO Longlists, 66
At a party attended by $n$ married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques $C_1, C_2, \cdots, C_k$ with the following property: no couple are members of the same clique, but for every other pair of persons there is exactly one clique to which both members belong. Prove that if $n \geq 4$, then $k \geq 2n$.
[i]Proposed by USA.[/i]
1990 IMO Shortlist, 22
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.
1988 IMO Longlists, 6
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.$
1992 IMO Longlists, 80
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.$
1991 IMO Shortlist, 9
In the plane we are given a set $ E$ of 1991 points, and certain pairs of these points are joined with a path. We suppose that for every point of $ E,$ there exist at least 1593 other points of $ E$ to which it is joined by a path. Show that there exist six points of $ E$ every pair of which are joined by a path.
[i]Alternative version:[/i] Is it possible to find a set $ E$ of 1991 points in the plane and paths joining certain pairs of the points in $ E$ such that every point of $ E$ is joined with a path to at least 1592 other points of $ E,$ and in every subset of six points of $ E$ there exist at least two points that are not joined?
1979 IMO Longlists, 15
Let $n \geq 2$ be an integer. Find the maximal cardinality of a set $M$ of pairs $(j, k)$ of integers, $1 \leq j < k \leq n$, with the following property: If $(j, k) \in M$, then $(k,m) \not \in M$ for any $m.$
1983 IMO Longlists, 1
The localities $P_1, P_2, \dots, P_{1983}$ are served by ten international airlines $A_1,A_2, \dots , A_{10}$. It is noticed that there is direct service (without stops) between any two of these localities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.
2018 USA Team Selection Test, 3
At a university dinner, there are 2017 mathematicians who each order two distinct entrées, with no two mathematicians ordering the same pair of entrées. The cost of each entrée is equal to the number of mathematicians who ordered it, and the university pays for each mathematician's less expensive entrée (ties broken arbitrarily). Over all possible sets of orders, what is the maximum total amount the university could have paid?
[i]Proposed by Evan Chen[/i]
1990 IMO Longlists, 17
1990 mathematicians attend a meeting, every mathematician has at least 1327 friends (the relation of friend is reciprocal). Prove that there exist four mathematicians among them such that any two of them are friends.
1987 IMO Shortlist, 2
At a party attended by $n$ married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques $C_1, C_2, \cdots, C_k$ with the following property: no couple are members of the same clique, but for every other pair of persons there is exactly one clique to which both members belong. Prove that if $n \geq 4$, then $k \geq 2n$.
[i]Proposed by USA.[/i]
1989 IMO Shortlist, 29
155 birds $ P_1, \ldots, P_{155}$ are sitting down on the boundary of a circle $ C.$ Two birds $ P_i, P_j$ are mutually visible if the angle at centre $ m(\cdot)$ of their positions $ m(P_iP_j) \leq 10^{\circ}.$ Find the smallest number of mutually visible pairs of birds, i.e. minimal set of pairs $ \{x,y\}$ of mutually visible pairs of birds with $ x,y \in \{P_1, \ldots, P_{155}\}.$ One assumes that a position (point) on $ C$ can be occupied simultaneously by several birds, e.g. all possible birds.
2019 Polish MO Finals, 3
$n\ge 3$ guests met at a party. Some of them know each other but there is no quartet of different guests $a, b, c, d$ such that in pairs $\lbrace a, b \rbrace, \lbrace b, c \rbrace, \lbrace c, d \rbrace, \lbrace d, a \rbrace$ guests know each other but in pairs $\lbrace a, c \rbrace, \lbrace b, d \rbrace$ guests don't know each other. We say a nonempty set of guests $X$ is an [i]ingroup[/i], when guests from $X$ know each other pairwise and there are no guests not from $X$ knowing all guests from $X$. Prove that there are at most $\frac{n(n-1)}{2}$ different ingroups at that party.
1990 IMO Longlists, 11
In a group of mathematicians, every mathematician has some friends (the relation of friend is reciprocal). Prove that there exists a mathematician, such that the average of the number of friends of all his friends is no less than the average of the number of friends of all these mathematicians.
1978 IMO, 3
An international society has its members from six different countries. The list of members contain $1978$ names, numbered $1, 2, \dots, 1978$. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.
1986 IMO Shortlist, 8
From a collection of $n$ persons $q$ distinct two-member teams are selected and ranked $1, \cdots, q$ (no ties). Let $m$ be the least integer larger than or equal to $2q/n$. Show that there are $m$ distinct teams that may be listed so that :
[b](i)[/b] each pair of consecutive teams on the list have one member in common and
[b](ii)[/b] the chain of teams on the list are in rank order.
[i]Alternative formulation.[/i]
Given a graph with $n$ vertices and $q$ edges numbered $1, \cdots , q$, show that there exists a chain of $m$ edges, $m \geq \frac{2q}{n}$ , each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.
1986 IMO Longlists, 74
From a collection of $n$ persons $q$ distinct two-member teams are selected and ranked $1, \cdots, q$ (no ties). Let $m$ be the least integer larger than or equal to $2q/n$. Show that there are $m$ distinct teams that may be listed so that :
[b](i)[/b] each pair of consecutive teams on the list have one member in common and
[b](ii)[/b] the chain of teams on the list are in rank order.
[i]Alternative formulation.[/i]
Given a graph with $n$ vertices and $q$ edges numbered $1, \cdots , q$, show that there exists a chain of $m$ edges, $m \geq \frac{2q}{n}$ , each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.
1978 IMO Longlists, 30
An international society has its members from six different countries. The list of members contain $1978$ names, numbered $1, 2, \dots, 1978$. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.
1989 IMO Longlists, 59
Given seven points in the plane, some of them are connected by segments such that:
[b](i)[/b] among any three of the given points, two are connected by a segment;
[b](ii)[/b] the number of segments is minimal.
How many segments does a figure satisfying [b](i)[/b] and [b](ii)[/b] have? Give an example of such a figure.
1989 IMO Shortlist, 17
Given seven points in the plane, some of them are connected by segments such that:
[b](i)[/b] among any three of the given points, two are connected by a segment;
[b](ii)[/b] the number of segments is minimal.
How many segments does a figure satisfying [b](i)[/b] and [b](ii)[/b] have? Give an example of such a figure.
1985 IMO Shortlist, 8
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.
2002 IMO Shortlist, 7
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 ?
1978 IMO Shortlist, 10
An international society has its members from six different countries. The list of members contain $1978$ names, numbered $1, 2, \dots, 1978$. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.
1979 IMO Shortlist, 5
Let $n \geq 2$ be an integer. Find the maximal cardinality of a set $M$ of pairs $(j, k)$ of integers, $1 \leq j < k \leq n$, with the following property: If $(j, k) \in M$, then $(k,m) \not \in M$ for any $m.$
2025 Bulgarian Winter Tournament, 12.4
Prove that a graph containing a copy of each possible tree on $n$ vertices as a subgraph has at least $n(\ln n - 2)$ edges.