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. Note. If $A$ is friend of $B$ then $B$ is a friend of $A$.
Problem
Source: 2021 Centroamerican and Caribbean Mathematical Olympiad, P4
Tags: combinatorics, graph theory, clique, Clique number
13.08.2021 05:08
Simple one Call the person with no friends $A$ and call the person with only one friend $B$, and supposed their only friend is $C$. Then if we select $A$, $B$ and two other people at the meeting, neither of which are $C$, then the last two people we select must be friends as all the other possible connections of the four people involve at least one of $A$ or $B$, which do not have any friends besides $C$ which we excluded. The two remaining people can be any pair among the $2018$ remaining people who are not $A$, $B$, or $C$, thus those $2018$ people are all friends with each other $\blacksquare$
13.08.2021 05:18
Very easy, even for a P4. Just notice that if we ignore the first person, then among the remaining $2020$ people, any triangle of vertices must have at least one edges. Furthermore, if we pick the person who has only one friend, then any two people in the remaining group of $2018$ people have to be friends with each other, so we are done.
24.08.2021 05:13
Let's look at the graph, if two people know each other, connect the corresponding ends to them. So there will be 2021 ends in the graph, and let's say there are A and B, which are exactly 1 and 0, respectively. Let A be one edge of one-third, and let C be. So there are 2018 people other than A, B, C, let's take the Optional X and Y people. Conditionally there are at least 2 friends between people A, B, X, Y so X and Y must be friends.So 2018 has a complete graph. Let's look at the graph, if two people know each other, connect the corresponding ends to them. So there will be 2021 ends in the graph, and let's say there are A and B, which are exactly 1 and 0, respectively. Let A be one edge of one-third, and let C be. So there are 2018 people other than A, B, C, let's take the Optional X and Y people. Conditionally there are at least 2 friends between people A, B, X, Y so X and Y must be friends.So 2018 has a complete graph.
12.10.2021 20:03
This problem was interesting but easy. I was able to solve it during the competition. 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. Note. If $A$ is friend of $B$ then $B$ is a friend of $A$. Let the $2021$ people be $p_i \forall i\in \mathbb{Z}^+, i\leq 2021$. Without loss of generality, let $p_1$ be the person with no friends and $p_2$ the person with only one friend, and let that friend be $p_3$. If we have $p_1,p_2,p_i,p_j$ we know that $\forall i,j\in \mathbb{Z}^+, 4\leq i,j\leq 2021, i\neq j$ $\implies$ $p_i$ and $p_j$ are friends $\implies$ we know that all $p_i$ are friends except for $p_1,p_2,p_3 \implies$ there are 2018 $p_i$ that are friends (2021-3=2018). Q.E.D.
12.10.2021 20:50
Call $A$ the person that has no friends, $B$ the person which has only one friend and $C$ $B$'s friend: If $X$ and $Y$ are at the meeting and $X,Y \neq A,B,C$, picking the group $A,B,X,Y$, we must have that there're two person that are friends, but since $A$ doesn't have friends and $B$'s only friend is $C$, we have that $X$ and $Y$ are friends $\forall X,Y$. So there're $2021-3=2018$ people at the meeting that are all friends with each other.$\blacksquare$