Japan Mathematical Olympiad Final Round

Call a team a good team if any pair of students in the team are mutual friends, a bad team if any pair of students in the team are not mutual friends. By agreement, we consider a team consisting of only one student to be both good and bad. Let us show that the minimum value of $N$ we seek is $n+1$.

If, in a certain school having $n$ students, every pair of students are mutual friends, then they have to form $b=n$ bad teams, since every team must contain only one student in this case to get a partition into bad teams. Since, we must have $a\ge 1$ also, we see that $N\ge n+1$.

We next show by induction on $n$, that for any school $N\le n+1$ must hold.

When $n=1$, we have $a=b=1$, and therefore, $N\le a+b=2=n+1$ and our claim holds in this case.

Assume that our claim $N\le n+1$ is satisfied for the case $n=k$, and consider the case of $n=k+1$. Choose a student and call him $A$. By the induction hypothesis, there is a way to partition the student body of $k$ students excepting $A$ into $a^{\prime }$ good teams and also into $b^{\prime }$ bad teams in such a way that $a^{\prime }+b^{\prime }\le k+1$ is satisfied.

If $a^{\prime }+b^{\prime }\le k$, then adding a team consisting of student $A$ only to each of the two ways of partitioning students beside $A$ into good and bad teams as above, we obtain the partitions of all $k+1$ students into $a=a^{\prime }+1$ good teams and $b=b^{\prime }+1$ bad teams, for which we have $N\le a+b=(a^{\prime }+1)+(b^{\prime }+1)\le k+2=n+1$.

If $a^{\prime }+b^{\prime }=k+1$, we can consider the following three cases:

(i) If among $a^{\prime }$ good teams of $k$ students there is a team whose members are all friends of $A$, then adding $A$ to this team, we get a partition of all $k+1$ students into $a=a^{\prime }$ good teams. We can also form a partition of all students into $b=b^{\prime }+1$ bad teams by creating a team consisting of $A$ only. Then, we get partitions into $a$ good teams and $b$ bad teams for which $N\le a+b=a^{\prime }+(b^{\prime }+1)=k+2=n+1$.

(ii) Similarly, if, among $b^{\prime }$ bad teams there is a team all of whose members are not friends of $A$, then we can get a partition of all $k+1$ students into good teams and bad teams for which $N\le k+2=n+1$.

(iii) If every one of $a^{\prime }$ good teams contains at least one student who is not a friend of $A$, and every one of $b^{\prime }$ bad teams contains at least one student who is a friend of $A$, then $A$ must have at least $a^{\prime }$ students who are not his friends and also have at least $b^{\prime }$ students who are his friends, which implies that the number of students in this school besides $A$ must be at least $a^{\prime }+b^{\prime }$. But, since the number of students besides $A$ is $k$ which equals $a^{\prime }+b^{\prime }-1$ by our assumption, we get a contradiction.

This completes our induction, and establishes that $N\le n+1$, and proves that $N=n+1$ is the desired answer for the problem.