クイズ大陸クイズ大陸

参加型ナゾトキサイト『クイズ大陸』で、脳トレをどうぞ！

 FAQ
feedRSS

シェア
クイズ大陸カップ　ノックアウトステージ
難易度：★★★ 　
?a2wz0ahz 2022/12/03 12:40
クイズ大陸カップのKOステージ進出チームが全て決定しました．
KOステージでは，1敗すると敗退となり，どのチームも同じ数の試合に勝たなければ優勝できません．
（通常の公平な勝ち残り式トーナメントということです．）
主催者が調べたところ，ある試合をするチームの戦力値がxとyのとき，その試合の利益がx×y万円となるように，KOステージに進出するチームの戦力を数値化できることが分かりました．
また，戦力値の高いチームが必ず勝つことも分かっています．
以下のようなケースでうまく試合を組み，利益を最大にしてください．

問題1. チーム数が8で戦力値が0～7
問題2. チーム数が16で戦力値が0～15

例えば，チーム数が4で戦力値が0～3の場合，

　┌─┴─┐
┌┴┐　┌┴┐
３　０　２　１

とすると，利益は3×0 + 2×1 + 3×2 = 8万円，

　┌─┴─┐
┌┴┐　┌┴┐
３　１　２　０

とすると，利益は3×1 + 2×0 + 3×2 = 9万円，

　┌─┴─┐
┌┴┐　┌┴┐
３　２　１　０

とすると，利益が3×2 + 1×0 + 3×1 = 9万円なので，2つ目あるいは3つ目の組合せで利益が最大になります．

　　　┌───┴───┐
　┌─┴─┐　　　┌─┴─┐
┌┴┐　┌┴┐　┌┴┐　┌┴┐


　　　　　　　┌───────┴───────┐
　　　┌───┴───┐　　　　　　　┌───┴───┐
　┌─┴─┐　　　┌─┴─┐　　　┌─┴─┐　　　┌─┴─┐
┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐


（答えは上の表を使ってもいいですし，数字を並べるだけでもOKです．）

おまけ. チーム数が64で戦力値が0～63
Answer【2チームのどちらがトーナメント表の左でどちらが右かは利益に関係ないので，次の法則Th2が成り立ちます．

Th2：利益が最大であるとき，左のチームが勝つとしてよい．
（「してよい」というのは，必ずそうなるという意味ではなく，利益が最大になる組み合わせの中に，そうなるものがあるという意味で考えてください）

以後，すべてのトーナメントの図で，左のチームが勝つとします．

戦力値が異なる非負の数である4チームのトーナメント戦が次のようであるとします．
　┌─┴─┐
┌┴┐　┌┴┐
x0　x1　x2　x3
総利益はx0 x1 + x2 x3 + x0 x2…①
Th2を決勝戦に使うと，①が最大のとき，x0 > x2としてよい．
①で，x2の係数がx3 + x0，x1の係数がx0，x3の係数がx2で，x0 > x2なので，①が最大のとき，x2 > x1 > x3としてよい．
（文字の係数は，そのチームが対戦した相手の戦力値を合計したものです．合計が大きい文字に，より高い戦力値を割り当てればよいと考えるとわかりやすいかと思います．）
以上より，x0 > x2 > x1 > x3．
したがって，次の法則Th4が成り立ちます．

Th4：利益が最大のとき，x0 > x2 > x1 > x3としてよい．

戦力値が異なる非負の数である8チームのトーナメント戦が次のようであるとします．
　　　┌───┴───┐
　┌─┴─┐　　　┌─┴─┐
┌┴┐　┌┴┐　┌┴┐　┌┴┐
x0　x1　x2　x3　x4　x5　x6　x7
左半分にTh4を使って，
x0 > x2 > x1 > x3．
右半分にTh4を使って，
x4 > x6 > x5 > x7．
2回戦以降にTh4を使って，
x0 > x4 > x2 > x6．
初戦敗退チームの，総利益の式の係数を比較して，
x1 > x5 > x3 > x7．
冗長にならないようにまとめると，次の法則Th16が成り立ちます．

Th8：利益が最大のとき，
x0 > x4 > x2 > x6 > x5，
x2 > x1 > x5 > x3 > x7，
としてよい．

戦力値が異なる非負の数である16チームのトーナメント戦が次のようであるとします．
　　　　　　　┌───────┴───────┐
　　　┌───┴───┐　　　　　　　┌───┴───┐
　┌─┴─┐　　　┌─┴─┐　　　┌─┴─┐　　　┌─┴─┐
┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐
x0　x1　x2　x3　x4　x5　x6　x7　x8　x9　x10 x11 x12 x13 x14 x15
左半分にTh8を使って，
x0 > x4 > x2 > x6 > x5，
x2 > x1 > x5 > x3 > x7．
右半分にTh8を使って，
x8 > x12 > x10 > x14 > x13，
x10 > x9 > x13 > x11 > x15．
2回戦以降にTh8を使って，
x0 > x8 > x4 > x12 > x10，
x4 > x2 > x10 > x6 > x14．
利益の式における，初戦敗退チームの係数を比較して，
x1 > x9 > x5 > x13 > x11，
x5 > x3 > x11 > x7 > x15．
冗長にならないようにまとめると，次の法則Th16が成り立ちます．

Th16：利益が最大のとき，
x0 > x8 > x4 > x12 > x10 > x9，
x4 > x2 > x10 > x6 > x14 > x13，
x2 > x1 > x9 > x5 > x13 > x11，
x6 > x5 > x3 > x11 > x7 > x15，
としてよい．

問題1.
Th8より，
x0 > x4 > x2 > x6 > x5，
x2 > x1 > x5 > x3 > x7，
とします．
x0 = 7，x4 = 6，x2 = 5，x5 = 2，x3 = 1，x7 = 0．
総利益の式において，x6の係数はx7 + x4 = 6，x1の係数はx0 = 7なので，x1 > x6としてよい．
x1 = 4，x6 = 3．

　　　┌───┴───┐
　┌─┴─┐　　　┌─┴─┐
┌┴┐　┌┴┐　┌┴┐　┌┴┐
７　４　５　１　６　２　３　０

問題2.
Th16より，
x0 > x8 > x4 > x12 > x10 > x9，
x4 > x2 > x10 > x6 > x14 > x13，
x2 > x1 > x9 > x5 > x13 > x11，
x6 > x5 > x3 > x11 > x7 > x15，
とします．
x0 = 15，x8 = 14，x4 = 13，x11 = 2，x7 = 1，x15 = 0．
利益の式において，x10の係数はx11 + x8 = 16，x1の係数はx0 = 15，x6の係数はx7 + x4 = 14となるので，x10 > x1 > x6としてよい．
x10 = 10，x1 = 9．
x5の係数はx4 = 13，x14の係数はx15 + x12 = x12でx12 < x4 = 13であるから，x5 > x14としてよい．
x5 = 6．
x12の係数はx13 + x14 + x8．
x14 > x13 > x11 = 2なのでx13 + x14 > 6であるから，x13 + x14 + x8 > 6 + 14 = 20．
x2の係数はx3 + x0．
x3 < x5 = 6であるから，x3 + x0 < 6 + 15 = 21
よって，x13 + x14 + x8 > x3 + x0であるから，x12 > x2としてよい．
x12 = 12，x2 = 11．
x13の係数はx12 = 12，x3の係数はx2 = 11であるから，x13 > x3としてよい．
x14 = 5，x13 = 4，x3= 3．
x9の係数はx8 = 14，x6の係数はx7 + x4 = 14であるから，x9 > x6としてよい（どちらでもよい）．
x9 = 8，x6 = 7．

　　　　　　　┌───────┴───────┐
　　　┌───┴───┐　　　　　　　┌───┴───┐
　┌─┴─┐　　　┌─┴─┐　　　┌─┴─┐　　　┌─┴─┐
┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐　┌┴┐
15　９　11　３　13　６　７　１　14　８　10　２　12　４　５　０

おまけ.
63，39，47，15，55，27，38，7，59，33，43，11，51，21，26，3，61，36，45，13，53，24，32，5，57，30，41，9，49，18，20，1，62，37，46，14，54，25，35，6，58，31，42，10，50，19，23，2，60，34，44，12，52，22，29，4，56，28，40，8，48，17，16，0】
■
解答が公開されました。引き続きコメントできます。

このクイズのヒント

    ヒント知らないよ

このクイズの参加者（2人）

ジャンル・キーワード

携帯用ページ


携帯電話のQRコード読み取り機能でこのページを見られます。

広告 お買い物は下記のリンクからどうぞ
楽天市場はこちらから
Amazonはこちらから

広告
クイズ大陸関連書籍