このクイズのヒント
-
ヒント知らないよ
このクイズの参加者(3人)
広告
広告
クイズ大陸関連書籍
![]() ![]() |
![]() |
![]() |
![]()
難易度:★★★★
![]() ![]() クイズ大陸カップの開幕が近づいてきました.
クイズ大陸カップのグループステージでは,各チームをグループに分け,各グループの上位チームがノックアウト(KO)ステージに進出します. グループ内では,すべてのチームに強さの順序があり,強いチームが必ず勝ち,引き分けはありません. グループ内で試合を行うことで,あらかじめ決められた数の強いチームがKOステージに進出することになりますが,主催者はできるだけ少ない試合数でこれらのチームを見つけたいと考えています. 以下のようなケースでうまく試合を組み,試合数の期待値をできるだけ小さくしてください. (期待値が最小であることを示す必要はありません) 問題1. 4チーム中2チームがKOステージ進出 問題2. 6チーム中3チームがKOステージ進出
|
![]()
a2wz0ahz
早速のご参加ありがとうございます.
千夜一夜さんは天秤問題もよく出題されるので,お得意かもしれませんね. 瞬殺されたか… ![]() とあせりました. 4人の実力をA,B,C,Dとします。
2回の試合をします。A:B,C:D 一般性を失うことなく、 A>B,C>D とできます。 3回目の試合として、A:Cをします。 一般性を失うことなく、 A>C とできます。 1位はAと定まりました。 あとは2位決定戦として B:C をします。これが4回目の試合。 ![]() ![]() 問題1。
問題2は難しいです。 ![]()
a2wz0ahz
残念!
もう少しいい組み方がありそうです. もしかしたら,見落とされているかとも思いますが,今回は期待値の最小化ですので,ご注意ください. 私が述べた「7試合で定まる」というのは間違いでした。早とちり。
5人の実力をソートするのに7試合で済む方法は知られていますので、暫定3位の人と、残る1人とで試合を組めば、上位3名は判明します。計8試合となります。 ![]() ![]() 問題2。
不安です。 追記:わあ!?……期待値? 見落としてました。 参りました。 ![]()
a2wz0ahz
No.2と同様,期待値であることを見落とされているのかもしれません.
>> 5人の…方法は知られていますので そんなのがあるのですね! 知りませんでした. さすが,よくご存じですね ![]() ![]() ![]() 本問が全く解らなままなのですが、
折角ですのて、互いに大きさの異なる5個の数について 大小関係の比較を7回でソートする方法を書いておきます。ただし、略解です。 まず失敗作を。 5個のうち4個を取り出してその範疇のみでソートするのに5回の比較が必要です。この4個を a<b<c<d とします。 5番目のeが、この列のどこにもぐり込めるかを確認するためには、残り3回の比較が必要です。 合計8回の比較を要します。 以上が、失敗作です。 次は正解です。 5個のうち4個について次の2つともに知ることが出来るためには、比較を3回要します。 系列1:a<b<c 系列2:a<d 5個めのeについて、系列1のどこにもぐりこめるかを知るためには2回の比較を要します。 ここまで合計5回の比較です。 結果は、以下の2つのケースに分岐します。 ◆ケース1 系列1:v<w<x<y 系列2:v<z ◆ケース2 系列1:v<w<x<y 系列2:w<z いずれのケースにおいても、 zが、 w<x<y のどこにもぐるこめるかを決定するのに 2回の比較ですみます。 合計7回の比較でソートが完了します。 失敗作に比べると、 系列2をうまく使って、1回ぶんの比較を節約できています。 以上です。 ![]()
a2wz0ahz
ありがとうございます.
質問です. 最初の3回の比較で, a < b c < b a < d となったときは,どうすればよろしいでしょうか? ![]() ![]() おこたえします。
@とAとを比較します。 一般性を失うことなく @<Aとできます。 BとCとを比較します。 一般性を失うことなく B<Cとできます。 @とBとを比較します。 一般性を失うことなく @<Bとできます。 早い話が4人でトーナメントなのです。 トーナメントの勝ち上がりの図式は 様々に考えられますが 一般性を失うことなく、 上記で統一的に記述できます。 @<B<C @<A これを改名して a<b<c a<d とします。 v,w,x,y,z についても、さまざまなabcdとeとの比較の結果について改名しています。 プログラミングの言葉で言えば仮引数で関数・モジュールをコールする要領です。 ![]()
a2wz0ahz
そういうことだったんですね.
なるほど ![]() これで理解できました. ありがとうございました. 問題1.
まず適当な3チームを選んで順位を確定させます. 全ての組み合わせ(3回分)の試合を行えば完全な順位が確定出来ますが, 運が良ければ2回で済む可能性もあります. 具体的には最初の2試合両方に出場するチームが, 3チーム中で2番目の強さを保有するときに, 2回目の結果までで全ての力関係が分かりますが, 対戦順序を無作為に決めるとするとそのようになる確率は1/3です. この時点で3チーム中一番強いチームはKOステージへの進出が確定し, 一番弱かったチームはKOステージに進出出来ないことが確定します. あとは2番目のチームと残ったチームを対戦させれば, 最後のKOステージ進出チームが決定します. 従って総合的な試合回数期待値は, 1/3*3+2/3*4=11/3回です. 問題2. この場合自分より弱いチームが3チームあればKOシリーズへの進出が確定します. 従って適当な4チームを選んで一般的な形の平等なトーナメント表を作れば, 3回の試合でKOシリーズに進出するチームを1チーム決定できます. この手順を3回繰り返すことで9試合で全てのKO進出チームを決定できますが, 2回目以降のトーナメント表の作り方を工夫することで, 試合数を削減することが出来ます. 例えば最初のトーナメントではAチームがBチームに勝ち,CチームはDチームに勝ち, その後決勝戦でCチームがAチームに勝ち進出を決めた状況を考えます. このときAチームとBチームはKO進出候補に残っていますが, 既に一度対戦を行っている状態です. 従って2回目のトーナメント表を作るときの第1試合をA対Bとしてしまえば, 一回分試合する手間が省けます. よって残り2試合で2番目のKO進出チームを確定出来ます. 3回目のトーナメント表でも同様のことは出来るので, 結局3+2+2=7試合で全てのKO進出チームが確定できます. このやり方の場合試合回数が確率で変わることは無いので, 試合回数の期待値は7回です. ![]() ![]() 問題1は全ての可能性を検証したつもりです.
問題2は思いつきの解答です. もっと良い手順があるか考え中です. ![]()
a2wz0ahz
logiさん,ご参加ありがとうございます.
問題1.見事に正解です. 解答もすっきりしていて,説明も非常にわかりやすいです. 残念ながら,問題2.にはもっと良い手順があります. ご回答をお待ちしております. 問題1
1. A vs B 2. C vs D 3. 1勝者 vs 2敗者 2敗者が勝てば、CとDがKO進出決定。 1勝者が勝てば、1勝者はKO進出決定。残りの1枠を 4. 1敗者 vs 2勝者 で争ってもらう。なお、この時点で2敗者は2名に負けたので、KO進出できない。 期待値は、試合3で1勝者が勝つパターンが1/6で、2勝者がかつパターンが5/6なので、23/6 問題2 1. A VS B 2. C vs D 3. E vs F 4. 1勝者 vs 2 敗者 2敗者が勝ったら、1と同様の解き方で、6回か、運が良ければ5回 1勝者が勝ったら 5. 1勝者 vs 3敗者 3敗者が勝ったらE,FはKO進出決定。 残り1枠を1勝者vs2勝者で争う。6回。 1勝者が勝ったら1勝者はKO進出決定。 次に3勝者と2敗者で戦う。 6. 3勝者 vs 2敗者 2敗者が勝ったらE,Fは脱落。残り1脱落を1敗者vs2敗者で決める。 3勝者が勝ったら、EFの勝敗だけついているので、問題1のような試合を行なえば合計で9回か、運が良ければ8回で決まる。 最大で9回だけど、運が良ければ5回で終わる。期待値は知らない。(計算がかなり複雑になる。) ![]() ![]() 問題1は自信あるけど、問題2はもっといいパターンがありそうな気がする。試合数が多くなりすぎた。でも、とりあえず答えてみる。
![]() ![]()
a2wz0ahz
けんさん,ご参加ありがとうございます!
とりあえずでも,答えてみていただければうれしいです ![]() 問題1については,残念ながらまだ良いパターンがあります. 期待値の計算などは正しくできています. ぜひ,より良い組み合わせを探してみてください. 問題2についてですが,6試合目で,3勝者が勝った場合にどうするかを詳しく教えていただけますでしょうか. 試合の組み方が分かれば,期待値の計算は,こちらでもできると思います. 1手目は必然で、 2チームを任意に選び、対戦させます 。 勝ったほうの実力をA,負けたほうの実力をBとします。 実力が大きいほうが勝つものとします。 すなわち、 A>B となります。 残りの2チームの実力をC,Dとします。 以上が1手目です。 2手目は、B,Cの戦いです。 結果は、2つに分岐します。 2-1と2-2と書くこととします。 2-1:B>C 2-2:B<C 2つの分岐は上の通りとなります。 それぞれが起きる確率は 2-1:B>C:1/3 2-2:B<C:2/3 です。 以上が2手めです。 3手目以後は2手目での分岐別に書きます。 ◆2-1(B>C)1/3で発生。 A>B>C ですから 次が明らかとなります。 ◎Cが3位以下 ◎Aが2位以上 ◎Bは2位または3位。 こうなれば4手めはB,Dの一騎打ちです。 B,Dどちらが勝っても、上位2位が決まります。 手数の期待値への、この分岐からの寄与は即ち、 (1/3)*4=4/3 となります。 ◆2-2 (B<C)2/3で発生。 このとき、以下が明らかになります。 @Bは3位以下。 AAとCとの大小関係不明。 ここでBは上位2位からは脱落。 再度まとめなおすと、 互いに大小関係がわからないA,C,D から最下位を決めたい、あと何手? 3手目でAとCとを比較し、4手めで 負けたほうとDとを比較すれば、3チーム内での最下位が決まります。 手数の期待値への、この分岐からの寄与は即ち、 (2/3)*4=8/3 となります。 2つの分岐からの寄与を合算すると、 4/3+8/3=4 となります。 ![]() ![]() 問題1。
もうちよつとエレガントな解があるのではと、悩んでいます。 ![]()
a2wz0ahz
正解です!
正解です!…が,期待値は違います. うっかりミスがあります. 書いていただいたやり方で,求まったものよりもっといい期待値になりますよ ![]() 6で3勝者が勝った場合、2敗者は1勝者・2勝者・3勝者に負けたことになるので、脱落決定。
残り 1敗者 2勝者 3勝者 3敗者 なので、 7. 1敗者 vs 2勝者 8. 7勝者 vs 3敗者 3敗者が勝てば1勝者・3勝者・3敗者がKO進出決定。 7勝者が勝てば1勝者・7勝者がKO進出決定で、残りの1枠を 9. 7敗者 vs 3勝者 で争ってもらう。 ![]() ![]() 1でまだ詰められるんだ。
![]() ![]() ![]()
a2wz0ahz
問題2の詳細,ありがとうございます.
進出チーム決定までの試合数とその確率は, 5試合:1/30 6試合:7/30 7試合:1/10 8試合:1/15 9試合:17/30 となりました. 9試合になる確率が意外と多くなってしまいました ![]() 期待値は79/10試合で,もっと良い試合の組み方があります. ぜひ,探してみてください. 問題1
第2試合までを 1. A vs B 2. C vs D で行うと、次の試合では必ず第1試合と第2試合のチームが戦うことになる。この時、勝者同士を戦わせると、 3. 1勝者 vs 2勝者 で、3勝者はKO進出決定だが、2着がわからないため、必ず4試合かかる。 敗者どうしを戦わせてもやはり4試合かかる。 もっと試合数を減らすには、第2試合を変える必要がある。 試しに 2. 1勝者 vs Cとすると、、、! Cが勝てばCがKO進出決定。1敗者は脱落で、残り1枠を 3. 1勝者 vs Dで争える。 なお、こうなる確率は1/3 一方で、2/3を引いて1勝者が勝った場合、1勝者はKO進出決定。第3試合は 3. C vs Dを行う。 どちらが勝っても、 4. 1敗者 vs 3勝者 として、勝った方がKO進出となる。 このパターンだと、期待値は11/3試合となるので、23/6より僅かに優秀。 答え 1. A vs B 2. 1勝者 vs C 2でCが勝てばCがKO進出決定。 3. 1勝者 vs D で勝った方がKO進出決定。 2で1勝者が勝てば1勝者がKO進出決定。 3. C vs D 4. 1敗者 vs 3勝者 で勝った方がKO進出決定。 期待値は11/3試合 ![]() ![]() 問題1は今度こそ正解のはず。
問題2は試合数を減らそうとして、逆に多くなってしまった感じがする。 ![]() でも、問題1のシステムをうまく使えば、もっと少ない組み方を見つけられる気がする。頑張る。 ![]()
a2wz0ahz
正解!
今度こそ正解です ![]() 書いていただいたような考え方を進めていけば,問題2でも組み方を改善できるのではないかと思います. がんばってください. 問題2.
ここでは最初に具体的な試合プロセスを述べることにして, 期待値の計算は後で行うことにします. ================================================================== 余談ですが解答を考えるときは, 各点をそれぞれのチームに対応させたグラフを考え, 1試合行うごとに勝ったチームから負けたチームに向かって, 矢印を引いた図を考えて解きました. 解答では図を書く方法が分からなかったので不等式で表しましたが, お手元で図を書きながら読んでいただくと読みやすいかもしれないです. ================================================================== 最初に無作為に2チーム選んで対戦を行います. 以下その試合が初試合となるようなチームを選ぶ状況では, まだ一度も試合を行っていないチーム(残りのチームと呼ぶことにします) の中から無作為に選ぶものとします. 次に最初の試合の勝者と残りのチームの中の1チームで試合を行います. このとき2つのケースが考えられます. ケース1. A>B>C ケース2. A>B,A>C 以下各チームの名前をA,B,C,D,E,Fと書くことにします. ただし最初に全てのチームに名前を割り振るのではなく, そのチームが他のチームと区別できるようになった段階で, 名前を付けることにします. (最初に名前を付けることにしてしまうと, 上のような場合A>B>Cが起きる場合は最初の対戦はB対Cでなければなりませんが, そうするとケース2を書くときにB>A, B>Cと書かざるを得なく, 見づらくなってしまいます.) ケース1のAとケース2のAは異なる可能性がありますが, ケース1以降の議論に出てくるAは全て同じチームを表します. まずケース1について考えます. この場合は次の第三試合ではBと残りの1チームを対戦させます. ここでも2つの可能性が考えられます. ケース1-1. A>B>C,B>D ケース1-2. A>B>C,B<D 先にケース1-1を考えます. この時点でAはB,C,Dの3チームより強いので,KO進出が確定します. 次の第四試合ではBと残りの1チームを対戦させます. ここでも場合分けがあります. ケース1-1-1. E>B,B>C,B>D ケース1-1-2. B>E,B>C,B>D ここでは既に結果が確定したAに関する条件は省略しました. 以降冗長な条件は適宜省略しますが,いずれのケースでも, つねにそれ以前の全ての条件を隠し持っています. ケース1-1-1について考えます. この場合はEがKOに進出することが確定するので残りの枠は1枠です. またCとDはBより弱いので残りの1枠には入れません. 従って第五試合でBとFで対戦を行い勝ったほうがKO進出確定です. 都合5回の試合で全て確定させることが出来ます. これをパターン1と呼ぶことにします. パターン1(5回) 続いてケース1-1-2について考えます. この場合はBが2枠目に入り残り一枠ですが, C,D,E,Fの全チームに進出の可能性が残ります. 仕方がないのでトーナメント(3試合)で最後の枠を決めます. この場合をパターン2とします. パターン2(7回) ここでケース1-2に戻りますが,本問題は上位3チームを決める問題であると同時に, 下位3チームを決める問題であるとみなすことも出来ます. 1-1と1-2の条件は強弱をいれかえると対称なので1-1の戦略について, 勝ち負けの結果を逆にして問題を下位3チームを求めるものと読み替えれば, (対称的に)全く同じ結果を得ることが出来ます. パターン1,パターン2に対応するものをそれぞれパターン1',パターン2'とします. パターン1'(5回) パターン2'(7回) 続いてケース2について考えます. 第三試合ではCと残りの1チームを対戦させます. ここでBとCは対称ですが,以降は第1試合で負けたチームをB, 第二試合で負けたチームをCと呼ぶことにします. ケース2-1. A>B,A>C,C>D ケース2-2. A>B,A>C,D>C まずはケース2-1を考えます. この場合はAが最初のKO進出チームとなります. 第四試合ではCと残りの1チームを対戦させます. ケース2-1-1. E>C,C>D ケース2-1-2. C>E,C>D ケース2-1-1の場合を考えます. 第五試合ではBとCを対戦させます. ケース2-1-1-1. E>C,C>B,C>D ケース2-1-1-2. E>C,B>C,C>D ケース2-1-1-1ではEが2枠目の進出チームとなります. 第六試合でCとFを対戦させて勝ったほうが3枠目です. これをパターン3とします. パターン3(6回) ケース2-1-1-2の場合はC,Dが進出候補から外れます. (仮にCが進出すると仮定するとEとBも進出することになるが, 残り2枠しか無いのでこれは不可能.) よってB,E,Fの中の上位2チームが進出することになります. したがってあとは3チーム中最弱のチームを割り出せば,全ての枠が確定します. 適当な2チームで第六試合を行い, その敗者と残りのチームで第7試合を行えばその敗者が最弱であることが分かります. これをパターン4とします. パターン4(7回) 続いてケース2-1-2を考えます. 第五試合ではEとFを対戦させます. ケース2-1-2-1. C>E,E>F,C>D ケース2-1-2-2. C>E,F>E,C>D ケース2-1-2-1について考えます. この場合はCが2枠目を取ります. 残り1枠なのでEに負けたFは進出不可能です. B,D,Eの中の最強のチームが3枠目を獲得します. 適当な2チームで第六試合を行いその勝者と残りのチームで第七試合を行えば, 最強のチームが判明します. これをパターン5とします. パターン5(7回) 次にケース2-1-2-2を考えます. この場合Eが進出候補から外れます. B,C,D,Fで残り2枠を争います. 第六試合ではCとFで対戦させます. ケース2-1-2-2-1. F>C>D ケース2-1-2-2-2. C>D,C>F ケース2-1-2-2-1ではFの進出が確定します. 第七試合でBとCで試合を行い勝ったほうが第三枠を獲得します. これをパターン6とします. パターン6(7試合) ケース2-1-2-2-2ではCの進出が確定します. B,D,Eの中の最強チームが第三枠を獲得しますが, これまでと同様に2試合あれば最強チームを決定できます. これをパターン7とします. パターン7(8試合) 続いてケース2-2を考えます. 第四試合ではDと残りの1チームを対戦させます. ケース2-2-1. A>B,A>C,E>D,D>C ケース2-2-2. A>B,A>C,D>E,D>C ケース2-2-1ではCが進出できないことが確定します. 残りの5チーム中下位の2チームが分かれば全ての進出チームが分かります. 第五試合でBとDで対戦し,負けた方は(F以外に勝てるチームは無いので), 進出出来ないことが確定します. 第五試合でBが負けた場合はA,E,Fの中の最弱のチームが, 最後の進出不可能なチームになります. 第五試合でDが負けた場合はB,E,Fの中の最弱のチームが, 最後の進出不可能なチームになります. いずれも残り2試合で最弱を決められます. これをパターン8とします. パターン8(7試合) 続いてケース2-2-2を考えます. 第五試合ではCとFを対戦させます. ケース2-2-2-1. A>B,A>C,D>E,D>C,C>F ケース2-2-2-2. A>B,A>C,D>E,D>C,F>C ケース2-2-2-1ではAとDの進出が確定します. B,C,Eで最後の1枠を争いますが,これは2試合あれば事足ります. これをパターン9とします. パターン9(7試合) ケース2-2-2-2ではCが進出出来ないことが確定します. 残りの5チーム中下位の2チームが分かれば全ての進出チームが分かります. 第六試合でBとEで対戦し,負けた方は(F以外に勝てるチームは無いので), 進出出来ないことが確定します. 第六試合でBが負けた場合はA,E,Fの中の最弱のチームが, 最後の進出不可能なチームになります. 第六試合でEが負けた場合はB,D,Fの中の最弱のチームが, 最後の進出不可能なチームになります. いずれも残り2試合で最弱を決められます. これをパターン10とします. パターン10(8試合) ここまでで一つの戦略が作れました. 続いてこの戦略における試合回数の期待値を求めます. そのためにそれぞれのパターンが発生する確率を求めます.
パターン1'とパターン2'はそれぞれパターン1とパターン2と一致します.
全てのパターンの確率が計算できました. 改めて結果をまとめます. ただしパターン1と1',2と2'はそれぞれ合わせて一つのパターンI,IIとします. パターンI (5回) 2/15 パターンII (7回) 1/5 パターン3 (6回) 1/15 パターン4 (7回) 1/20 パターン5 (7回) 1/24 パターン6 (7回) 1/20 パターン7 (8回) 1/24 パターン8 (7回) 3/20 パターン9 (7回) 1/12 パターン10 (8回) 11/60 これらからこの戦略の期待値を求めると, 5*2/15+6*(1/15)+7*(1/5+1/20+1/24+1/20+3/20+1/12)+8*(1/24+11/60) =2/3+2/5+7*23/40+8*9/40 =(80+48+483+216)/120 =827/120≒6.892回となります. ![]() ![]() 流石a2wz0ahzさんの問題,一筋縄ではいきませんね.
ずいぶん苦労しましたが,前回より少し良い結果が得られました. 正直言うと直感的には前回の解答が最適だと思っておりましたので, より良い方法があったことに驚いております. 相変わらず最善かどうかは分かりませんが, 現状のマイベストスコアを提出させて頂きます. ![]() ![]()
a2wz0ahz
詳しいご回答をありがとうございました.
しかし,残念ながら不正解です ![]() お書きになった組み合わせの期待値の計算には間違いはありませんでしたが,実はもっと良い組み合わせがあります. ぜひ,チャレンジしてください. |