« 密造酒で死者 | トップページ | スノーフレーク »

2019年2月21日 (木)

トーナメントの試合数

http://yamada-kuebiko.cocolog-nifty.com/blog/2019/02/post-fbf9.html
2019年2月18日 (月) 朝めし前クイズ
「1回割るごとに1つ増える。11回割ると12個になる。」
↑この記事に、kankikoh さんからコメントを頂きました。
「これってトーナメントの試合数に似てますかね。チーム数-1=試合数ですね。」

私も
「似てます。チョコレートの場合ほど一般的ではないけれど。今、解説を考えています。後で記事にしますが、とりあえず御礼まで。」

★さて、私の「愚かなる考え」をご披露しなければならない。トホ。

nチームが参加するトーナメントを考えます。それを一枚の「板」と考えます。この板は「負けていないチーム」が属する板です。
チョコレートの問題での「割る」という操作は、割れてできたかけらのサイズを問う必要がありません。
12分割できるチョコレートを、まず8・4の2枚に割り、8のかけらを6・2に割り・・・などと続けてもかまいません。
しかし、トーナメントではそうはいかない。
「割る」という操作に対応するのは「試合」です。
最初の1試合で、「負けた」1チームと「負けていない」(n-1)チームに分割されます。
以降の試合でも、試合ごとに「負けた」1チームと、残る「負けていない」チームとに分割されて「1試合ごとに1つ増え」ますね。
「1回割るごとに1つ増える」が「1試合ごとに1つ増える」になるのです。
そして(n-1)試合で、n校全部ばらばらになりますが、最後の試合=分割において「負けなかった」1チームが優勝校になりますね。
ということで、チーム数-1=試合数 の関係が成立します。
板チョコ分割問題と、トーナメントとのアナロジーはこんなものでしょうか。

★普通はもっと単純に表現しますね。
n校が参加するトーナメントでは、1校のみが優勝し、(n-1)校はそれぞれ必ず1敗します。
つまり(n-1)の敗戦が生じます。(n-1)の敗戦が生じるためには、(n-1)試合が必要です。
と、こんな感じの説明になりますね。

↓正統派の数学的証明があります。ふ~ん、くらいの気分を味わってください。
http://web.sfc.keio.ac.jp/~mukai/modular/tournament.pdf

トーナメントの試合数と一対一対応
 高校野球の全国大会はトーナメント方式(勝ち抜き戦)である.参加高校の数がNの場合,何試合必要だろうか?ただし,引き分けはないものとする.
・・・
一般のNの場合も試合数はN-1となるだろうか?この予想は成立する.実際そのことをここできちんと証明してみよう.
次の証明では,集合と全単射の考えを使う.証明に用いるトーナメント方式の性質は次の2点である.
・全勝は1チームだけ.
・他のチームはすべて1回だけ負ける.

« 密造酒で死者 | トップページ | スノーフレーク »

理科おじさん」カテゴリの記事

コメント

詳しい解説ありがとうございました。なるほど……です。

コメントを書く

(ウェブ上には掲載しません)

« 密造酒で死者 | トップページ | スノーフレーク »

2021年5月
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
サイト内検索
ココログ最強検索 by 暴想
無料ブログはココログ