Mediterranean Mathematical Competition PETER O' HALLORAN MEMORIAL

We start with the set $M_0=\varnothing$, and we modify/improve it step by step until it satisfies the two desired conditions. There are two possibilities for an improving step:

1. If there is a student $x\in M$ who has $\ge 4$ friends in $M$, then $x$ is removed from $M$.

2. If there is a student $y\notin M$ who has $\le 3$ friends in $M$, then $y$ is added to $M$.

These improving steps may behave quite chaotically, and they can add the same student many times to $M$ (and then remove it again from $M$). However, we can show that the improvement process must eventually terminate. For a set $M$, let $p(M)$ denote the number of ordered pairs $(x,y)\in M\times M$ for which $x$ and $y$ are friends. We associate with set $M$ the function value

$$f(M):=7|M|-p(M).$$

Clearly $f(M)$ only takes integral values. Furthermore, it is bounded from above by $7$ times the total number of students and its starting value is $f(M_0)=0$. We will show that every improving step strictly increases the value of $f(M)$. Hence, after a finite number of steps the process terminates with a set $M$ that satisfies the two desired conditions.

First assume that there is a student $x\in M$ with $\ge 4$ friends in $M$ (as in improving step #1). Then there are at least $8$ pairs of friends $(x,y)$ and $(y,x)$ in $M\times M$. Hence if we remove $x$ from $M$, then $p(M)$ decreases by at least $8$, whereas $|M|$ decreases by $1$; but this means that $f(M)=7|M|-p(M)$ strictly increases.

Next assume that there is a student $y\notin M$ who has $\le 3$ friends in $M$ (as in improving step #2). If we add $y$ to $M$, then $p(M)$ increases by at most $6$, whereas $|M|$ increases by $1$; hence also in this case $f(M)$ strictly increases.