Olympiad problems

2010 Kyrgyzstan National Olympiad, 3

At the meeting, each person is familiar with 22 people. If two persons $A$ and $B$ know each with one another, among the remaining people they do not have a common friend. For each pair individuals $A$ and $B$ are not familiar with each other, there are among the remaining six common acquaintances. How many people were at the meeting?

1966 IMO Longlists, 24

Tags: graph theory , vertex degree , combinatorics

There are $n\geq 2$ people at a meeting. Show that there exist two people at the meeting who have the same number of friends among the persons at the meeting. (It is assumed that if $A$ is a friend of $B,$ then $B$ is a friend of $A;$ moreover, nobody is his own friend.)

1985 Austrian-Polish Competition, 2

Tags: graph theory , vertex degree , combinatorics

Suppose that $n\ge 8$ persons $P_1,P_2,\dots,P_n$ meet at a party. Assume that $P_k$ knows $k+3$ persons for $k=1,2,\dots,n-6$. Further assume that each of $P_{n-5},P_{n-4},P_{n-3}$ knows $n-2$ persons, and each of $P_{n-2},P_{n-1},P_n$ knows $n-1$ persons. Find all integers $n\ge 8$ for which this is possible. (It is understood that "to know" is a symmetric nonreflexive relation: if $P_i$ knows $P_j$ then $P_j$ knows $P_i$; to say that $P_i$ knows $p$ persons means: knows $p$ persons other than herself/himself.)

EGMO 2017, 4

Tags: graph theory , vertex degree , combinatorics

Let $n\geq1$ be an integer and let $t_1<t_2<\dots<t_n$ be positive integers. In a group of $t_n+1$ people, some games of chess are played. Two people can play each other at most once. Prove that it is possible for the following two conditions to hold at the same time: (i) The number of games played by each person is one of $t_1,t_2,\dots,t_n$. (ii) For every $i$ with $1\leq i\leq n$, there is someone who has played exactly $t_i$ games of chess.

2010 Contests, 3

Tags: graph theory , combinatorics , vertex degree

At the meeting, each person is familiar with 22 people. If two persons $A$ and $B$ know each with one another, among the remaining people they do not have a common friend. For each pair individuals $A$ and $B$ are not familiar with each other, there are among the remaining six common acquaintances. How many people were at the meeting?

1990 IMO Longlists, 11

Tags: extremal graph theory , graph theory , extremal combinatorics , vertex degree , combinatorics

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.

1966 IMO Shortlist, 24

Tags: graph theory , vertex degree , combinatorics

There are $n\geq 2$ people at a meeting. Show that there exist two people at the meeting who have the same number of friends among the persons at the meeting. (It is assumed that if $A$ is a friend of $B,$ then $B$ is a friend of $A;$ moreover, nobody is his own friend.)

2017 EGMO, 3

Tags: combinatorics , graph theory , vertex degree

Let $n\geq1$ be an integer and let $t_1<t_2<\dots<t_n$ be positive integers. In a group of $t_n+1$ people, some games of chess are played. Two people can play each other at most once. Prove that it is possible for the following two conditions to hold at the same time: (i) The number of games played by each person is one of $t_1,t_2,\dots,t_n$. (ii) For every $i$ with $1\leq i\leq n$, there is someone who has played exactly $t_i$ games of chess.

2022 Iran MO (3rd Round), 1

Tags: combinatorics , graph theory , tournament , vertex degree

For each natural number $k$ find the least number $n$ such that in every tournament with $n$ vertices, there exists a vertex with in-degree and out-degree at least $k$. (Tournament is directed complete graph.)

2010 IMO Shortlist, 5

Tags: graph theory , combinatorics , tournament graphs , vertex degree

$n \geq 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players $bad$ if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_i$ and $l_i$ be respectively the number of wins and losses of the $i$-th player. Prove that \[\sum^n_{i=1} \left(w_i - l_i\right)^3 \geq 0.\] [i]Proposed by Sung Yun Kim, South Korea[/i]