Olympiad problems

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.

2001 IMO Shortlist, 3

Tags: clique number , graph theory , combinatorics

Define a $ k$-[i]clique[/i] to be a set of $ k$ people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

2007 IMO, 3

Tags: graph theory , algorithm , clique number , combinatorics

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a [i]clique[/i] if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its [i]size[/i]. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room. [i]Author: Vasily Astakhov, Russia[/i]

2021 Centroamerican and Caribbean Math Olympiad, 4

Tags: graph theory , combinatorics , clique , clique number

There are $2021$ people at a meeting. It is known that one person at the meeting doesn't have any friends there and another person has only one friend there. In addition, it is true that, given any $4$ people, at least $2$ of them are friends. Show that there are $2018$ people at the meeting that are all friends with each other. [i]Note. [/i]If $A$ is friend of $B$ then $B$ is a friend of $A$.

2008 Hong Kong TST, 2

Tags: graph theory , clique number , combinatorics

Define a $ k$-[i]clique[/i] to be a set of $ k$ people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

2007 IMO Shortlist, 6

Tags: graph theory , algorithm , clique number , combinatorics

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a [i]clique[/i] if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its [i]size[/i]. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room. [i]Author: Vasily Astakhov, Russia[/i]