Problem 218

First of all let us show that for each even $1 < n < 101$ we can choose a group of $n$ pupils satisfying conditions. When $n = 2$ any pair of friends can be chosen. Assume that for $n = 2l$ we have already constructed a group $A_{2l}$ of $n = 2l$ pupils satisfying the conditions. Let $S$ be the set of all pupils of the school. If $S - A_{2l}$ contains a pair of friends then by adding them to $A_{2l}$ we will get $A_{2l+2}$. If by repeating this process we can reach $A_n$ we are done. Otherwise for some $2m < n$ no two all pupils in $S - A_{2m}$ are friends. Then since each school pupil has a friend, any pupil from $S - A_{2m}$ has at least one friend in $A_{2m}$. Thus, by adding any $n-2m$ pupils from $S - A_{2m}$ to $A_{2m}$ we will get a desired $A_n$.

Now we show that for each odd $1 < n < 101$ we can choose a group of $n$ pupils satisfying conditions. We can start by choosing a group $A_3$ of three pupils and proceed as in the even case. Any pupil together with his two friends can be chosen for $A_3$. If there is no pupil with two friends then all $101$ pupils in the school will be partitioned into disjoint pairs of friends, a contradiction.