30th Junior Turkish Mathematical Olympiad

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.