Some people know each other in a group of people, where "knowing" is a symmetric relation. For a person, we say that it is $social$ if it knows at least $20$ other persons and at least $2$ of those $20$ know each other. For a person, we say that it is $shy$ if it doesn't know at least $20$ other persons and at least $2$ of those $20$ don't know each other. Find the maximal number of people in that group, if we know that group doesn't have any $social$ nor $shy$ persons.
Problem
Source: JBMO TST Bosnia and Herzegovina 2022
Tags: JBMO TST, combinatorics, national olympiad
06.04.2023 07:21
Bumping! Any hints on this one? I am not too familiar with graph theory…
12.09.2023 15:46
Answer: $40$. Example: $A:A_1,A_2,...,A_{20}$ and $B:B_1,...,B_{20}$ $A_i$ are friend with all $B_i$ and $B_i$ are friend with all $A_i$. Assume that there are more than $40$ people. Let $A$ be the person who has the most friend. $n$ is the number of friends of $A$.Let $S$ be the graph which includes $A$ and its friends. $i)$If $n \geq 20$ $v_1,v_2,...v_n$ are the friends of $A$. There is no edge between any $v_i,v_j$ because $A$ is not social. If $n \geq 21$, then $(v_2,...,v_{21})$ are not friend with $v_1$ and they are not friend with each other. So $v_1$ is shy. Contradiction $\implies n=20$ Let $F$ be the graph which includes the vertices which are not in $S$.$F$ has atleast $20$ vertices. $A$ has no friend in $F$ but $A$ is not shy. So $F$ is a complete graph. Let $B_1,B_2,...,B_{20}$ be the people who are in $F$. Lemma: Each $B_i$ has atleast $2$ friends who are $v_i$. Proof: Assume that $B_1$ is not friend with $(v_1,...,v_{19})$. Then $B_1$ is not friend with $(A,v_1,...,v_{19})$ also $v_1$ and $v_2$ are not friends so $B_1$ is shy. Contradiction so the lemma is true. $B_1$ is friend with $B_2,...,B_{20}$ and some $v_i,v_j$ so $B$ has atleast $21$ friends which gives a contradiction. $ii)$If $n \leq 19$ There are atleast $21$ people who are not in $S$. Let these people be $k_1,k_2,...,k_m$.We have $m \geq 21$. $A$ is not friend with any $k_i$ but $A$ is not shy which means $(k_1,k_2,...,k_m)$ is a complete graph which gives us a contradiction.