noobatron3000 wrote: A, B and C are three persons among a set P of n (n>3) persons. It is known that A, B and C are friends of one another, and that every one of the three persons has already made friends with more than half the total number of people in P. Given that every three persons who are friends of one another form a friendly group, what is the minimum number of friendly groups that may exist in P? 19th Hong Kong (China) Mathematical Olympiad(3 December, 2016) ，Q1

$Case$ $1$ $n=2k$ Each of $A,B,C$ has more that $k-2$ friends that are not $A$ or $B$ or $C$ $WLOG$ we will say that each of them has exactly $k-2$ friends By pigeonhole principe there is at least $k-3$ persons that are friend with two of them And this minimum is reached if $A$ and $B$ have $k-3$ common friend and $1$ distincts So it leave us $2k-3-k+3-2= k-2$ friends for $C$ So the minimum number of friendly groups is $k-2$ ( because $(A,B,C)$ is also a friendly groupe) $Case$ $2$ $n=2k+1$ Similary we will found that there is $k$ friendly$ groupes.

@above In case 1 it should be $k-1$.

I got this solution: When n is odd (n=2k+1) there are k groups, when n is even (n=2k) and n≥6 there are k+1 groups, and when n=4 there are 4 groups. Starting with the odd case: Case 1: n=2k+1 Each of A, B, C must have at least k+1 friends. To minimise the groups, let them each have exactly k+1 friends. So each of A, B, C has exactly (k+1)-2=k-1 friends that are not in A, B, C. Summing all the friendships between A, B, C and “not A, B, C” gives 3(k-1)=3k-3. Allocating these friendships among the n-3=2k-2 people not in A, B, C, gives at least (3k-3)-(2k-2)=k-1 people not in A, B, C that are friends with 2 of A, B, C (pigeonhole principle). The minimum friendly groups occurs when there are exactly k-1 people not in A, B, C that are friends with 2 of A, B, C. (To get the minimum friendly groups, we want to avoid any person being friends with all of A, B, C, as this would create more groups) Each of the k-1 people not in A, B, C that are friends with 2 of A, B, C creates 1 friendly group each, adding the A, B, C group gives k friendly groups. Case 2: n=2k Similar to above: each of A, B, C must have at least k+1 friends. To minimise the groups, let them each have exactly k+1 friends. So each of A, B, C has exactly (k+1)-2=k-1 friends that are not in A, B, C. Summing all the friendships between A, B, C and “not A, B, C” gives 3(k-1)=3k-3. Allocating these friendships among the n-3=2k-3 people not in A, B, C, gives at least (3k-3)-(2k-3)=k people not in A, B, C that are friends with 2 of A, B, C (pigeonhole principle). The minimum friendly groups occurs when there are exactly k people not in A, B, C that are friends with 2 of A, B, C. But this is only possible when there enough people not in A, B, C, ie. when n-3≥k, which is when n≥6. When n≥6: each of the k people not in A, B, C that are friends with 2 of A, B, C creates one friendly group each, adding the A, B, C group gives k+1 friendly groups. When n=4, the fourth person must be friends with all of A, B, C, giving (4C3)=4 friendly groups.