平成１６年９月１９日

[流れ星]

　　　　　第１４３回数学的な応募問題解答

　　　　　　＜解答募集期間：８月２９日〜９月１９日＞
［順位決定戦］

太郎さんは、アテネオリンピックの野球の観戦をしていて、予選リーグ戦方式と決勝トーナメント方式のあり方に疑問を待ちました。（青い字を９月１日に訂正しました）女子ソフトボールみたいなページシステム方式ならと考えてしまいます。
　もし、順位だけを決定する試合を行うとすると、一体何試合が必要になるか考えてみました。できるだけ少ない試合数で順位をつけたいと思います。
ただし、次のようなルールで行います。
（１）ＡがＢに勝ち、ＢがＣに勝ったときは、ＡはＣに勝つものとする。即ち、試合を行いません。
（２）引き分けはないものとする。
（３）各チームごとの試合数の多い少ないは考慮せず、総試合数だけを最小にする。

例えば、２チームで行いときは明らかに１試合で順位を決定できます。ここからが問題です。

問題１：３チームのときは、最低何回の試合で順位を決定できるか。具体的にいろいろな場合を考えてください。
問題２：４チームのときは、最低何回の試合で順位を決定できるか。具体的にいろいろな場合を考えてください。
問題３：５チームのときは、最低何回の試合で順位を決定できるか。具体的にいろいろな場合を考えてください。
問題４：同じルールで、（ｎ＋１）チームのときとｎチームのときでは最小総試合数の間にはどんな式ができるか、予想してください。

追加：できたら、ｎチームのときは、最低何回の試合で順位を決定できるか。考えてください。

ＮＯ１「H7K」 8/29: 11時14分受信 更新9/19更新
最小という証明はまだできていません，まだ「こういうふうにやれば順位決定できるね」という段階です．
A>B :⇔ AがBより上位，とする．
1. A>Bとする．A-Cを行い，A>Cのときは，B>CかB<Cか不明なので，B-Cを行う．
   C>Aのときは，これで決定．よって3試合．
2.(1) A〜Cの順位を先に決める．A>B>Cとする．B-Dを行い．B>DのときはC-D，B<DのときはA-Dを行えば良い．
  (2) A-B，C-Dを行い，A>B，C>Dとする．A-C，B-Dを行い，A>C，B>Dのときは，BとCの順位決定のためB-Cを行う．
      A>C，B<Dのときは，A>C>D>Bと確定．A<C，B>Dのときは，C>A>B>Dと確定．A<C，B<Dのときは，A-Dを行えば良い．
  よって，5試合．
4. 2.(1)の考えでいく．A_1>A_2>...>A_nとする．A_(n+1)とA_i (1<=i<=n)の順位を定めるのに，
   [log_2 (n+1)以上の最小の整数]回の試合が必要．(∵A_(n+1)のはいる場所はn+1通りあり，
   それを1つにしぼるには，「真ん中より上か」でわける方が良い．)

ＮＯ２「toru」　　 9/02: 14時12分受信 更新9/19更新
問題１　いろいろやってみると３試合
問題２　いろいろやってみると５試合
問題３　いろいろやってみると８試合
問題４　nチームの順位をまず決めてからn+1番目のチームの順位を決める。この時、２分探索法を用いるとする。(nチームのまずほぼまん中の順位（偶数の場合はまん中が２つあるのでどちらか）のチームとまず試合をし、勝った場合は、それより上位のチームのうちで,またほぼまん中の順位のチームと、負けた場合はそれより下位のチームのうちでほぼまん中の順位のチームと試合をするという具合にくり返して行く)　
この方法で試合数（必要試合数の最大値）が最小になりそうですが、証明はしておりません。（まあ問題文にも予想して下さいと書いてあるので、取りあえずこれで送っておきます）

　この場合、(n+1)番目のチームの順位を決めるのに、2^(N-1)≦n＜2^Nの時、（最大）N試合必要になるので、
ガウス記号を使えばN=[log n/log 2]+1 　
よってnチームの時のこの方法による必要最大試合数をF(n)、F(1)=0 とすれば
F(n+1)=F(n)+[log n/log 2]+1,　(n=1,2,3,----)

n=1,2,3,----に対してN(n)を順に書くと
1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6----
　F(n)はF(n)=F(1)+Σ(k=1〜n-1)N(k)=Σ(k=1〜n-1)N(k)、並べて書けば、
0,1,3,5,8,11,14,17,21,25,29,33,37,41,45,49,54,59,64,69,74,79,84,89,94,99,104,109,114,119,124,129,135,141,147,----

　数列N(n)はk(=1,2,3,---)が2^(k-1)ずつならんでいるから
N(n-1)=N’=[log(n-1)/log 2]+1としてN’-1までの和はΣ(k=1〜N’-1)k(2^(k-1))=N’ (2^(N’-1))-2^N’+1
　(n-1)番目までの、N’の個数は(n-1)-Σ(k=1〜N’-1)2^(k-1)=n-2^(N’-1)でこの部分の和は
 N’(n-2^(N’-1))この二つをたして

F(n)=N’n-2^N’+1=n([log(n-1)/log2]+1)-2^([log(n-1)/log2]+1)+1（n=2,3,4,------）

ＮＯ３「kasama」　 9/02: 18時32分受信 更新9/19更新
さて、今回は順序付けの問題ですね。我々プログラマにはソート問題として大変馴染みの深いものです。で、次のような考えているのですが、・・・

チームの順位を決めるというのは、例えば、先頭から強い順番にチームの代表者を一列に並ばせることと同じと考えられます。ここで、チームの試合＝要素の比較です。このように考えると、以降はソート手法の問題として扱うことができます。

すると、ソートのやり方のよって、最大比較回数は

　バブル・ソート・・・(n-1)*(n-2)
　単純選択法・・・(n*(n-2))/2
　単純挿入法・・・(n*(n-2))/4
　ヒープソート・・・n*log(n)/log(2)
　クイックソート・・・n^2

であることが知られています。私が知っている範囲内では、ヒープソートが比較回数が最も少なくて済みます(現実的なプログラミングで使用されるのはクイックソートですが)。

どのソートが良いかは別として、どのやり方でソートするかを決めておかないと、いろんな答えがでてくるのではないでしょうか。
問題文から推測して、

　n個のソート済みの要素列に新しい要素を追加する場合はn回の比較が必要と考えるのでしょうか。

「kasama」」 9/17: 20時37分受信 更新9/19更新
チームの順位を決めるというのは、例えば、先頭から強い順番にチームの代表者を一列に並ばせることと同じです。つまり、要素の並替えとして考えれることができます。ここで、チームの試合＝要素の比較とすれば、今回の問題は要素の並替えで、比較回数を最小にする問題と考えられます。


【並替えの方法】

並替えの方法は以前から研究されていて、いくつかはプログラミングで実用化されていますが、ここでは、以下のような方法で並び替えます。
順序付けられたn個の要素の並びに、新しい1個の要素をある順序にしたがって挿入するケースを考えます。ただし、n個の要素の順序付けに必要な比較回数を S_n、順序付されたn個の要素の並びをa₁,a₂,a₃,･･･, a_n、新しく挿入する要素をa_n+1とします。

�@並びを２つに分割
☆n＞1の場合
　k=[n/2]として、並びを集合{a₁,･･･,a_k} と集合{a_k+1,･･･,a_n} に分けます。
☆n＝1の場合
　a_nとa_n+1だけを比較して作業終了

�A比較（＝チームの試合）
a_kとa_n+1を比較します。『引き分けはない』ので、追加すべき集合の並びは
　a_k＞a_n+1なら集合{a₁,･･･,a_k}
　a_k＜a_n+1なら集合{a_k+1,･･･,a_n}
です。集合の要素数をnに設定して�@の操作に戻ります。

直感的に言って、挿入位置は1/2、1/4、1/8、･･･と絞り込まれるので、比較回数は高々[log₂n+ 1]ですね。よって、
　S_n+1 = S_n + [log₂n+1]
です。だだし、S₂=1です。


【問題１〜３】
上の漸化式を利用して
　S₃ = S₂ + [log₂2+1] = 3
　S₄ = S₃ + [log₂3+1] = 5
　S₅ = S₄ + [log₂4+1] = 8　　です。

【問題４】
上の漸化式より　　S_n+1 = S_n + [log₂n+1]　です。

ＮＯ４「キューダ」　 9/19: 21時48分受信 更新9/20更新
【必要な無いところをカットしました　　２００４／０９／１９】
４：天秤使いの妙技
５：問題
--------------------------------------------------------------------
重さが異なる五つの「重り」と「天秤」がありました。
Ａ君は、Ｂ君に、向かって
「君なら何回天秤を使って、重りを重い順に並べ替えられる？」と聞きました。
Ｂ君は、少し考え、「うーん、．．．８回かな」と答えました。
それに対し、Ａ君は、「７回あれば、十分なんだよ」とこたえ、重りを天秤に載せ始めました。

便宜上、重りには、Ａ，Ｂ，Ｃ，Ｄ，Ｅという名前を付けることにします。
最初の三回は、次のような操作をし、次のような結果を得ました。

１回目　　ＡとＢを比べ　　Ａ＞Ｂ（Ａの方がＢよりも重い）　が判明
２回目　　ＣとＤを比べ　　Ｃ＞Ｄ　が判明
３回目　　ＡとＣを比べ　　Ａ＞Ｃ　か判明

以下同様の操作を繰り返しましたが、なんと、６回目の比較が終わった時、
「運が良かったこともあるけど、６回で終わっちゃった。」と言って、重い順番に並べ替えました。

さて、Ａ君が出した結論は、次の（１）〜（15）のうちどれでしょうか？
可能性があるものだけを全て挙げて下さい。

　解答選択肢
（１）ＡＢＣＤＥ，　　（２）ＡＢＣＥＤ，　　（３）ＡＢＥＣＤ，
（４）ＡＣＢＤＥ，　　（５）ＡＣＢＥＤ，　　（６）ＡＣＤＢＥ，
（７）ＡＣＤＥＢ，　　（８）ＡＣＥＢＤ，　　（９）ＡＣＥＤＢ，
（10）ＡＥＢＣＤ，　　（11）ＡＥＣＢＤ，　　（12）ＡＥＣＤＢ，
（13）ＥＡＢＣＤ，　　（14）ＥＡＣＢＤ，　　（15）ＥＡＣＤＢ
答
　　￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
-------------------------------------------------------------------
６：問題の解答と解説
--------------------------------------------------------------------
解答

答　　　（３），（13），（15）
　　￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
解説　（ＭＳゴシックなどの、等幅フォントを使ってご覧ください。）

５個の重りの並び順は、５！（＝５×４×３×２×１）＝１２０通りあります。
一方、２＾７（＝２×２×２×２×２×２×２）＝１２８と、

５！　＜　２＾７

が成立するため、「うまく天秤を使えば７回で可能」となります。

しかし、１２０と１２８、とかなり近い値であるため、常に無駄な比較を行なわないことが要求されることになります。
この結果、比較する手順が、ほとんど確定され、これが、この問題が成立する所以です。

最初１２０通りの可能性があります。これを１回目の比較で６０通りに減らし、以下、３０通り、１５通りと、減らしていきました。

そしてその次、この１５通りを、例えば、６通りか９通りへ分かれるような比較を行った場合、その「手順」は「確実に７回以内の使用」という条件を満たせ得なくなり、失敗となります。なぜなら、９通りの方へいってしまった場合　９＞２＾３　なので、残り３回の比較では、決定できなくなるからです。

つまり１５通りになった後、解の候補数が次のようなになるように比較を行っていかなければなりません。

１５通り→８通りと７通り
　８通り→４通りずつ
　　４通り→２通りずつ
　　　２通り→確定
　７通り→４通りと３通り
　　３通り→２通りと１通り（１通りになった場合は確定）

このうち、この問題では６回の比較で確定したということから、
　　１５通り→７通り→３通り→確定
という経路をたどって決まったことがわかります。


さて、最初の三回の比較の結果、可能性がある順番は、選択肢にある１５通
りです。一方、行う可能性がある比較は次の６種類です。

ＡとＥ，ＢとＣ，ＢとＤ，ＢとＥ，ＣとＥ，ＤとＥ
（明らかにＡ＞Ｄが成り立つため、これは除いています。）

この６種類の中で、８通り＆７通りへと分けることができるのは、よく調べてみると、ＣとＥの比較しか無いことがわかります。
従って、４回目の比較は、必然的にＣとＥの比較に決定されてしまいます。
以下同様な理由で、「可能な比較」はかなり限定されてしまい、この様な事情をうまく取り入れ、比べるべきものを十分検討したものが、Ａ君が見つけた「必ず７回で十分な手順」です。
そして、具体的には、次のような図として表すことができます。

１５通り
    ┣C>E━８通り
    ┃       ┣D>E━４通り
    ┃       ┃       ┣B>D━２通り
    ┃       ┃       ┃       ┣B>C━ＡＢＣＤＥ
    ┃       ┃       ┃       ┗C>B━ＡＣＢＤＥ
    ┃       ┃       ┗D>B━２通り
    ┃       ┃                ┣B>E━ＡＣＤＢＥ
    ┃       ┃                ┗E>B━ＡＣＤＥＢ
    ┃       ┗E>D━４通り
    ┃                ┣B>E━２通り
    ┃                ┃       ┣B>C━ＡＢＣＥＤ
    ┃                ┃       ┗C>B━ＡＣＢＥＤ
    ┃                ┗E>B━２通り
    ┃                         ┣B>D━ＡＣＥＢＤ
    ┃                         ┗D>B━ＡＣＥＤＢ
    ┗E>C━７通り
           ┃┣A>E━４通り
           ┃┃       ┣B>C━２通り
           ┃┃       ┃       ┣B>E━ＡＢＥＣＤ
           ┃┃       ┃       ┗E>B━ＡＥＢＣＤ
           ┃┃       ┗C>B━２通り
           ┃┃                ┣B>D━ＡＥＣＢＤ
           ┃┃                ┗D>B━ＡＥＣＤＢ
           ┃┗E>A━３通り
           ┗┓     ┃┣B>C━確 定━━ＥＡＢＣＤ　　※
             ┃     ┃┗C>B━２通り
             ┃     ┗┓       ┣B>D━ＥＡＣＢＤ
             ┃       ┃       ┗D>B━ＥＡＣＤＢ
             ┃       ┣B>D━２通り
             ┃       ┃       ┣B>C━ＥＡＢＣＤ
             ┃       ┃       ┗C>B━ＥＡＣＢＤ
             ┃       ┗D>B━確 定━━ＥＡＣＤＢ　　※
             ┣B>C━３通り
             ┃     ┃┣A>E━２通り
             ┃     ┃┃       ┣B>E━ＡＢＥＣＤ
             ┃     ┃┃       ┗E>B━ＡＥＢＣＤ
             ┃     ┃┗E>A━確 定━━ＥＡＢＣＤ　　※
             ┃     ┗┳B>E━確 定━━ＡＢＥＣＤ　　※
             ┃       ┗E>B━２通り
             ┃                ┣A>E━ＡＥＢＣＤ
             ┃                ┗E>A━ＥＡＢＣＤ
             ┗C>B━４通り
                    ┃┣A>E━２通り
                    ┃┃       ┣B>D━ＡＥＣＢＤ
                    ┃┃       ┗D>B━ＡＥＣＤＢ
                    ┃┗E>A━２通り
                    ┗┓       ┣B>D━ＥＡＣＢＤ
                      ┃       ┗D>B━ＥＡＣＤＢ
                      ┣B>D━２通り
                      ┃       ┣A>E━ＡＥＣＢＤ
                      ┃       ┗E>A━ＥＡＣＢＤ
                      ┗D>B━２通り
                               ┣A>E━ＡＥＣＤＢ
                               ┗E>A━ＥＡＣＤＢ

図中、※で表した４通りが、Ａ君が出した可能性のある順番で、これらがこの問題の答えとなります。

＜水の流れ：コメント＞ 大変、皆さんにとって論理的で良く分かり易いです。誠にありがとうございます。（９月２０日記）

ＮＯ５「H7K」 9/21: 17時35分受信 更新9/２１更新
もう期間過ぎてますね……すみません．
「キューダ」さんの投稿を見て，こちらでも同様の結果がえられていることを思い出しました．

まず，6チームのとき，試合数は10試合で十分．
これをいうために，まず5チームのときについて考える，
A>B,C>D,A>Cとするとき，A,B,C,D,Eの並べ方は15通りあり，
彼の投稿から，その15通りをあと4試合で決定できることがわかります．
さて，A,B,C,D,E,Fの6チームについて，
A>B, C>D, E>F, A>C>Eとするとき，並べ方は720/6/8=15通りあり，
しかも，Aが先頭に来るのは確定なので，
B〜Eについて，B->E, C->A, D->B, E->C, F->D という変換をすると，
先の5チームの際の「A>B,C>D,A>C」のもとでの並べ方に1対1対応する．
よって，6チームのときは，4+3+3 (A,C,E)=10試合でできる．
一方，nチームのとき，最小試合数をmとすると，n!<2^mが必要なので，
n=6 -> m>=10である．よって，最小試合数は10試合．

ここまではいいんですが，nチームの最小試合を具体的に求める，というところで悩んでます．

＜水の流れ：コメント＞これは、難しいです。それなりに漸化式はありまして、また、いずれ研究をしてください。
私の手元には、ｎ＝１００までの最小の試合数の表があります。
　それによると、ｎ＝７のとき、１３試合　ｎ＝８のとき、１６試合　ｎ＝９のとき、１９試合　ｎ＝１０のとき、２２試合
・・・・　です （９月２１日記）

ＮＯ６「kiyo」 9/22: 01時17分受信 更新9/22更新
いつもお世話になっています。清川（kiyo）です。

   0    1    3    5    7   10   13   16   19   22
   26   30   34   38   42   46   50   54   58   62
   66   71   76   81   86   91   96  101  106  111
  116  121  126  131  136  141  146  151  156  161
  166  171  177  183  189  195  201  207  213  219
  225  231  237  243  249  255  261  267  273  279
  285  291  297  303  309  315  321  327  333  339
  345  351  357  363  369  375  381  387  393  399
  405  411  417  423  429  436  443  450  457  464
  471  478  485  492  499  506  513  520  527  534
  541  548  555  562  569  576  583  590  597  604
  611  618  625  632  639  646  653  660  667  674
  681  688  695  702  709  716  723  730  737  744
  751  758  765  772  779  786  793  800  807  814
  821  828  835  842  849  856  863  870  877  884
  891  898  905  912  919  926  933  940  947  954
  961  968  975  982  989  996 1003 1010 1017 1024
 1032 1040 1048 1056 1064 1072 1080 1088 1096 1104
 1112 1120 1128 1136 1144 1152 1160 1168 1176 1184
 1192 1200 1208 1216 1224 1232 1240 1248 1256 1264

 階差数列
 1, 2 2 2, 3 3 3 3 3, 4 4 4 4 4 4 4 4 4 4 4 ,5*11,6*21,7*43,

 1, 3, 5, 11,21,43,85,171,
 A(n)=A(n-1)+2*A(n-2), A(n)=(2^n-(-1)^n)/3　

問題４
B(n)-B(n-1)=ceiling( log(3*n/4)/log(2) ) 常用対数

　プログラムでn=200まで出してみました。

＜水の流れ：コメント＞「kiyo」さん、ありがとうございます。私の手元にある、ｎ＝１００までの値と同じです。（９月２２日記）

ＮＯ７「中川幸一」 9/29: 22時10分受信 更新10/1更新
今回の場合は演繹的に書き並べるのが大変だったので, トーナメントの一例を挙げておきました。

5 チームのとき少なくとも 7 回の試合を行えば充分ですが, シードの形が余りにも不平等であるために出来るだけ平等な形を考えて, 少なくとも 8 回の試合を行えば充分なトーナメントにしました。
尚, 少なくとも 7 回の試合で順位が全て決定するものも一応はトーナメントと分類はされるはずです。少し不安なので今度機会があったら調べてみます。
因みに 7 回の試合の場合は
強い順番に A, B, C, D, E とおくと,
第 1 試合  A - E
第 2 試合  B - D
第 3 試合  A - B
第 4 試合  B - C  (ここで 1 位は A と決定) (ここで 2 位は B と決定)
第 5 試合  C - D
第 6 試合  D - E  (ここで 4 位は D と決定)
第 7 試合  C - E  (これで全順位が決定)
という形になります。

5 チームのとき少なくとも 7 回の試合を行えば充分と考えていったときの数列は『Number of comparisons for merge sort of n elements』
という数列です。数列の作り方は
Maple:     Digits := 60: A001768 := proc(n) local k; add( ceil(log(3*k/4)/log(2)), k=1..n); end;　です。

ＮＯ８「中川幸一」 10/3: 22時46分受信 更新10/４更新

＜水の流れ：「中川幸一」さんからは「2004/09/29 (水) 16:25 に『第１４３回数学的な応募問題の解答の訂正』というタイ
トルで添付ファイルを付けて送信したつもりですが, 届いてなかったでしょうか？
一応念のためにあのとき送ったファイルと同じものをもう一度添付しておきます。」ということでした。
何かの関係で、受信されていませんでした。もしかして、私のミスで削除したかもしれません。大変申し訳ありませんでした。＞

ＮＯ９「キューダ」 10/4: 22時13分受信 更新10/9更新
第１４３回の問題に関連して、いくつか解った事がありますので、ご連絡します。

必要な比較回数の階差数列がceiling( log(3*n/4)/log(2) )になるような、比較方法、Merge Insertionの具体的な手順が解りました。
意外に単純な手順でした。（もし必要であれば、テキストファイルにして提出したいと思います。）

また、勝手に取り組んでいたN=12の場合ですが、どのような手順を用いても２９回の比較では不可能であることが、証明されているようです。
３０回でソートする手順は単純ですが、３０回でソートするのが最小である事の証明は、簡単ではないようです。「図」がたくさん必要なようです。
極めて優秀な方法だと言えますね。
　しかしながら、もちろん、Merge Insertionが完全というわけでもありません。N=47の時、Merge Insertionでは、２０１回必要ですが、４２個と５個の２グループに分け、それぞれをソートし（１７１＋７＝１７８回必要）、この２グループを合体させる戦略をとると、後２２回、つまり、合計で２００回で可能なようです。奥の深い問題ですね。

　
＜自宅＞　　mizuryu@aqua.ocn.ne.jp