Olympiad problems

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.

1992 IMO Longlists, 20

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

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

1978 IMO Shortlist, 10

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

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.

1978 IMO, 3

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

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.

2023 Serbia Team Selection Test, P1

Tags: extremal graph theory , ad hoc , 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?

1990 IMO Longlists, 17

Tags: combinatorics , graph theory , extremal graph theory , clique number

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.