Olympiad problems

2008 Hong Kong TST, 2

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.

2001 IMO Shortlist, 3

Tags: combinatorics , graph theory , Clique number , IMO Shortlist

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: algorithm , graph theory , IMO , combinatorics , IMO 2007 , Clique number , IMO Shortlist

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: combinatorics , graph theory , 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$.

2007 IMO Shortlist, 6

Tags: algorithm , graph theory , IMO , combinatorics , IMO 2007 , Clique number , IMO Shortlist

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]

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.