◆宮城県　斉藤　誠さんからの解答。

　不戦勝を数えるのは不自由なので「戦わないチーム」と戦った数をかぞえることとします。

「戦わないチーム」のグループを「ゴースト」とし、トーナメントツリーにすべてのチームを配置し、参加チームが２の累乗に不足する場合に「ゴースト」チームを配置することで完全なツリーとします。

　すると「不戦勝を最小にする」は、この「ゴースト」と戦う対戦数を最小にすることになります。
最善の場合は「ゴースト」グループ（２の累乗のチーム数のとき）での優勝チームと１度だけ戦えば、不戦勝１回で済みます。

　さて、ここに参加８チームのトーナメントツリーを考えます（図１）。
「┃」の配下（枝と呼ぶことにします）のチーム数を見ると、それぞれ２の累乗になっています。
０段目＝１チーム　　１段目＝２チーム　２段目＝４チーム　３段目＝８チーム
ここに「ゴースト」を配置することを考えます。
３チームの場合が図２です。

　「不戦勝を最小」にすることは、「ゴーストとの対戦を最小にする」ことなので、出来る限り多くの「ゴースト」を１つの枝に配置する必要があります。
図２の様に１つの枝がいっぱいになってから隣の枝に配置していきます。
　このようにすると、真のチームと「ゴースト」が対戦するのは、どの回戦でも多くても１試合になります。
１試合以上の対戦が行われるとすれば、「ゴースト」が２チーム以上あるので「ゴースト」同士の試合が組めるので最適な配置になっていません。

　最適な配置ができたら、どの回戦でも「ゴースト」との対戦がある場合は、「ゴースト」はその枝配下の２の累乗チームの代表ですから、「ゴースト」のチーム数との関係が求まります。
　ｐ回戦目に「ゴースト」との対戦があれば、「ゴースト」は２のｐ乗チームあるので、２進数のｐ桁目 と対応しますので、対戦があるところを「１」ないところを「０」で表した２進数が「ゴースト」のチー ム数です。

　図２の場合は「０１１」となり３チームです。
また、１のところは「ゴースト」との対戦ですので「不戦勝」を表し、この１の数が不戦勝の回数２となり、「ゴーストチーム数を２進数で表したときの１の数が不戦勝の試合数」に対応します。

　「ゴースト」チーム数は完全なトーナメントツリーから出場チーム数を減算したものですので

　Ｋ（２の累乗）ーｎ（出場チーム）＝「ゴースト」チーム数

　「ゴーストチーム数を２進数で表したときの１の数が不戦勝の試合数」

となります。

　『不戦勝の試合数』へ

　数学の部屋へもどる