JMO 2014
問題 3

問題文 $(1),(2)$ のチームをそれぞれ友人チーム，非友人チームと呼ぶ．$n$ 人を友人チーム $a$ 個に分割する方法と非友人チーム $b$ 個に分割する方法であって，$a+b\leq n+1$ が成り立つようなものがあることを $n$ に対する帰納法で示そう．

$1$ 人のときは明らかである．$n$ で成り立つと仮定して，$n+1$ のときを考える．仮定より，ある生徒 $x$ を除いた $n$ 人を問題文のようにチーム分けする方法であって，$a+b\leq n+1$ なるものが存在する．

• $a+b\leq n$ のとき
  $x$ のみからなる友人チームと $x$ のみからなる非友人チームを新しく作ることで友人チームの個数と非友人チームの個数の和を $(a+1)+(b+1)\leq n+2$ とできる．
• $a+b=n+1$ のとき
  • ある友人チーム $A$ が存在して，$x$ が $A$ の全員と友人であるならば，$A$ に $x$ を追加した友人グループを作り，$x$ のみからなる非友人グループを考えることで友人チームの個数と非友人チームの個数の和を $(a+1)+b\leq n+2$ とできる．
  • ある非友人チーム $B$ が存在して，$x$ が $B$ の全員と友人でないならば，$B$ に $x$ を追加した非友人グループを作り，$x$ のみからなる友人グループを考えることで友人チームの個数と非友人チームの個数の和を $a+(b+1)\leq n+2$ とできる．
  • 上のどちらでもない場合，任意の友人グループ $A$ に対して，$x$ と友人でない生徒が少なくとも $1$ 人存在し，任意の非友人グループ $A$ に対して，$x$ と友人である生徒が少なくとも $1$ 人存在する．すなわち $x$ と友人である生徒が $a$ 人以上，友人でない生徒が $b$ 人以上存在することになるが，$a+b=n+1$ よりこれは $x$ の他に生徒が $n$ 人しかいないことに矛盾する．

以上より，$x$ を追加した $n+1$ 人でも適切にチーム分けをすることで友人チームの個数と非友人チームの個数の和を $n+2$ 人以下にできる．

一方で $n$ 人のうちどの $2$ 人も友達である場合を考えると $a+b\geq n+1$ である必要があるので，$N$ の最大値は $n+1$ である．