Olympiad problems

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]

1989 IMO Shortlist, 29

Tags: combinatorics , graph theory , Extremal Graph Theory , Extremal combinatorics , IMO Shortlist

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.

2025 Bulgarian Winter Tournament, 12.4

Tags: graph theory , Trees , Extremal Graph Theory , algorithm , combinatorics

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.

2023 Serbia Team Selection Test, P1

Tags: Extremal Graph Theory , ad hoc , Serbia , TST , graph theory , combinatorics

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?

1978 IMO Longlists, 30

Tags: graph theory , Ramsey Theory , combinatorics , Extremal Graph Theory , Extremal combinatorics , IMO , IMO 1978

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.

1990 IMO Longlists, 17

Tags: combinatorics , graph theory , Extremal Graph Theory , Clique number , IMO Shortlist , IMO Longlist

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.