Olympiad problems

1983 IMO Shortlist, 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.

2023 Serbia Team Selection Test, P1

Tags: combinatorics , extremal graph theory , ad hoc , graph theory

In a simple graph with 300 vertices no two vertices of the same degree are adjacent (boo hoo hoo). What is the maximal possible number of edges in such a graph?

1990 IMO Longlists, 78

Tags: graph theory , combinatorics , extremal combinatorics , extremal graph theory

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.

1989 IMO Longlists, 89

Tags: combinatorics , graph theory , extremal graph theory , extremal combinatorics

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.

1985 IMO Longlists, 84

Tags: combinatorial geometry , combinatorics , graph theory , extremal combinatorics , extremal graph theory

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.

1988 IMO Shortlist, 4

Tags: combinatorics , extremal graph theory , graph theory , permutation

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