問題
幼女たちには、1名につき最大3人のライバルがいる。
「AのライバルがB」なら「BのライバルもA」になる。
いま、この幼女たちを2グループに分けて、どの幼女も「同じグループ内にいるライバルは最大1人」という状態にしたい。
幼女たちをどのようにグループ分けすればよいだろうか？
さあ、解いてみよう！
シンプルな問題ですが、なかなか手応えがあります。
あらゆる場合分けを考えていたら時間が足りません。
注目すべきポイントはどこか。
少し下にスクロールすると答えがあります。
正解
- 全員をランダムにAグループとBグループに分ける
- Aグループ内にいる「ライバルが2人以上」の幼女をBグループに移動させる（候補が複数の場合はランダムで選ぶ）
- その後、Bグループでも同じことを行う
- 手順2,3をくりかえせば、最終的に全員が「同じグループ内にいるライバルは最大1人」という状態になる
解説
ライバルの特性
1回で目的を達成するのは困難です。
長期的に考えましょう。
「1人の幼女は最大3人のライバルを持つ」という前提から、幼女は4種類に分類されます。
- ライバルがいない幼女
- ライバルが1人いる幼女
- ライバルが2人いる幼女
- ライバルが3人いる幼女
「ライバルがいない幼女」「ライバルが1人いる幼女」に関しては無視しても構いません。
「同じグループ内において幼女は最大1人のライバルと同居できる」ことが前提だからです。
ライバル数が0,1の幼女たちは、いつ、どのグループにいても問題ありません。
厄介なのは「ライバルが2人いる幼女」「ライバルが3人いる幼女」。
「彼女たちをどう分けるか」が本問の趣旨になります。
手順を追う
まず、全幼女をテキトーに2グループに分けます。
仮に「Aグループ」「Bグループ」と名前をつけましょう。
次に、Aグループ内にいる「ライバルが2人以上いる幼女」をBグループに送り込みます。
このとき、候補が複数いたらランダムで1人を選びます。
たとえば「ある4人組の幼女がいて全員が自分以外の幼女とライバル」という場合、「ライバル3人の幼女」がその組内で4人いることになります。
こんな時はとりあえず誰か1人を選んでBグループに送ります。
これでOKです。
つづいてBグループで「ライバルが2人以上いる幼女」をAグループに送り込みます。
これを延々と繰り返します。
最終的に、幼女全員が「同じグループ内にいるライバルは最大1名」という状態になり解決します。
なぜそれで上手くいくのか
当然の疑問となるのが、「その手順で上手くいく理由」。
ひとつずつ考えていきましょう。
やっていることは、「ライバルが2人以上の幼女」をグループ間で移動させまくって、全員が「多くともライバルが1人の幼女」だけにすること。
「ライバルが1人以下」になった時点でその幼女は移動のループから外れるため、この方法を行えばいつかは必ず目標に到達できます。
ここで、「任意の幼女が移動をくりかえしてもライバルが減らない状況」がありえないと証明できればいいわけです。
「移動を繰り返してもライバルが減らない状況」とはすなわち、
- グループを移動する時、ライバルも一緒についてくる
- どちらのグループにもライバルが2人いる
のどちらかです。
前者の可能性は「候補が複数いたらランダムで1人を選んで移動させる」という手順で最終的に無効化できます。
同じ組内でライバル関係が入り乱れている場合、そのうちの1人を選んで移動させる––ということをくりかえしていけば大丈夫です。
後者については、前提から可能性が否定されています。
1人の幼女が持てるライバルは最大3人。
「どちらのグループにもライバルが2人いる」状況は「ライバルが4人いる」ことを意味しているため、ありえません。
そんな感じで、最後には必ず「同じグループ内にはライバルが最大1人しかいない」ようなグループ分けが可能になります。
参考
問題の初出は1979年の第13回全ソ連数学オリンピック。
Find minimum number of groups such that no enemies in same group
reducing enemies – geometry puzzle
140字以内の問題文
幼女たちには、1名につき最大3人のライバルがいる
「AのライバルがB」なら「BのライバルもA」になる
今この幼女たちを2グループに分けて、どの幼女も「同じグループ内にいるライバルは最大1人」という状態にしたい
幼女たちをどのようにグループ分けすればよいだろうか？
