幼女たちには、1名につき最大3人のライバルがいる。「AのライバルがB」なら「BのライバルもA」になる。いま、この幼女たちを2グループに分けて、どの幼女も「同じグループ内にいるライバルは最大1人」という状態にしたい。幼女たちをどのようにグループ分けすればよいだろうか?さあ、解いてみよう!シンプルな問題ですが、なかなか手応えがあります。あらゆる場合分けを考えていたら時間が足りません。注目すべきポイントはどこか。下にスクロールすると答えがあります。全員をランダムにAグループとBグループに分けるAグループ内にいる「ライバルが2人以上」の幼女をBグループに移動させる(候補が複数の場合はランダムで選ぶ)その後、Bグループでも同じことを行う手順2,3をくりかえせば、最終的に全員が「同じグループ内にいるライバルは最大1人」という状態になる解説ライバルの特性1回で目的を達成するのは困難です。長期的に考えましょう。「1人の幼女は最大3人のライバルを持つ」という前提から、幼女は4種類に分類されます。「ライバルがいない幼女」「ライバルが1人いる幼女」に関しては無視しても構いません。「同じグループ内において幼女は最大1人のライバルと同居できる」ことが前提だからです。ライバル数が0,1の幼女たちは、いつ、どのグループにいても問題ありません。厄介なのは「ライバルが2人いる幼女」「ライバルが3人いる幼女」。「彼女たちをどう分けるか」が本問の趣旨になります。手順を追うまず、全幼女をテキトーに2グループに分けます。仮に「Aグループ」「Bグループ」と名前をつけましょう。次に、Aグループ内にいる「ライバルが2人以上いる幼女」をBグループに送り込みます。このとき、候補が複数いたらランダムで1人を選びます。「ある4人組の幼女がいて全員が自分以外の幼女とライバル」という場合、「ライバル3人の幼女」がその組内で4人いることになります。こんな時はとりあえず誰か1人を選んでBグループに送ります。つづいてBグループで「ライバルが2人以上いる幼女」をAグループに送り込みます。これを延々と繰り返します。最終的に、幼女全員が「同じグループ内にいるライバルは最大1名」という状態になり解決します。それで上手くいくのか当然の疑問となるのが、「その手順で上手くいく理由」。ひとつずつ考えていきましょう。やっていることは、「ライバルが2人以上の幼女」をグループ間で移動させまくって、全員が「多くともライバルが1人の幼女」だけにすること。「ライバルが1人以下」になった時点でその幼女は移動のループから外れるため、この方法を行えばいつかは必ず目標に到達できます。ここで、「任意の幼女が移動をくりかえしてもライバルが減らない状況」がありえないと証明できればいいわけです。「移動を繰り返してもライバルが減らない状況」とはすなわち、グループを移動する時、ライバルも一緒についてくるどちらのグループにもライバルが2人いるのどちらかです。前者の可能性は「候補が複数いたらランダムで1人を選んで移動させる」という手順で最終的に無効化できます。同じ組内でライバル関係が入り乱れている場合、そのうちの1人を選んで移動させる––ということをくりかえしていけば大丈夫です。後者については、前提から可能性が否定されています。1人の幼女が持てるライバルは最大3人。「どちらのグループにもライバルが2人いる」状況は「ライバルが4人いる」ことを意味しているため、ありえません。そんな感じで、最後には必ず「同じグループ内にはライバルが最大1人しかいない」ようなグループ分けが可能になります。問題の初出は1979年の第13回全ソ連数学オリンピック。プロフィールミライジョー(@Mirai_Joe)東京在住のWebマーケター。外資系で広告運用してます。