カークマンの組分け                     戻る

 15人を、3人ずつ、5班に分ける方法の数を求めることは、順列・組合せにおける標準的な
問題である。実際に、
             
ある。
 ところで、上の問題に対して、1度同じ班になった人とは2度と同じ班にならないと仮定する
ような場合の方が、実生活でよく直面する。

たとえば、6チームのリーグ戦(総当り戦)で、同時に3試合ずつ5回戦を行う場合とか...。

 1847年に、Kirkman(1806〜1895)は、次のような問題を提出している。
(正式な名前は、「カークマンの女生徒の問題」という。女生徒というのは、問題に対して本
質的ではないと思うのだが、なぜか、カークマンは「女生徒」と限定している!?)

 15人を、次のように班分けする。
1日目・・・15人を、3人ずつ、5班に分ける。
2日目・・・15人を、3人ずつ、5班に分ける。ただし、1度同じ班になった人とは2度と同じ班
      にならないものとする。
3日目・・・2日目と同様の条件で、15人を、3人ずつ、5班に分ける。
4日目、5日目、6日目、7日目も、2日目と同様の条件で、15人を、3人ずつ、5班に分ける。
 このとき、どんな班分けになるだろうか?

 これに対して、次のような班分けが知られている。(生徒を、1、2、3、・・・、15 で表す。)

1日目  1   2   5  3   4   7  6   8  14  9  10  13  11  12  15
2日目  1   3   9  2   8  15  4  11  13  5  12  14   6   7  10
3日目  1   4  15  2  13  14  3  10  12  5   6   9   7   8  11
4日目  1   6  11  2   7  12  3   8  13  4   9  14   5  10  15
5日目  1   7  14  2   4  10  3   5  11  6  13  15   8   9  12
6日目  1   8  10  2   9  11  3  14  15  4   6  12   5   7  13
7日目  1  12  13  2   3   6  4   5   8  7   9  15  10  11  14

1日目  1   2   8  3   5  13  4   7   9  6  10  15  11  12  14
2日目  1   3  11  2   5  14  4   8  15  6   7  13   9  10  12
3日目  1   4  13  2   7  10  3  14  15  5   6  12   8   9   11
4日目  1   5  10  2   3   9  4   6  14  7  11  15   8  12  13
5日目  1   6   9  2  13  15  3   7  12  4   5  11   8  10  14
6日目  1   7  14  2   4  12  3   6   8  5   9  15  10  11  13
7日目  1  12  15  2   6  11  3   4  10  5   7   8   9  13  14

 班分けの方法は、上記以外にも、たくさんある!

 はたして、このような班分けは、どのような考え方をすれば求められるのだろうか? いくつか
簡単な場合について検討し、考察することにしよう。

例 番号1、2、3、4、5、6 の6人が、リーグ戦(総当り戦)を行う。同時に3試合ずつ5回戦を
  行う場合、どのように試合の順番を決めればよいか?

 表を作って求めてみよう。(1〜5回戦を、記号 A〜E で表す。)

解の例1 解の例2
     
 
A B C D E
A E D B C
B E A C D
C D A E B
D B C E A
E C D B A
       
 
A B C D E
A D B E C
B D E C A
C B E A D
D E C A B
E C A D B

 解は、上記以外にも、たくさん作ることができる。

 上記の問題に対して、次のような素晴らしいアイデアがあることを最近知った。
(参考文献:ホームページ:「未菜実の数理パズル入門」の「リーグ戦の組合せ」)

 まず分かっていることは、番号1 は、番号2〜6 と 1 回だけ対戦するということ、そして、
隣り合う番号同士の対戦には限界があり、番号一つ飛ばしの対戦も適当に織り交ぜなけ
ればならないということである。
 そこで、次のような円を考え、中心には、番号1を配置し、円周の5等分点上に、番号2
〜6を配置する。
          


 上の図で、緑色の針を時計回りに72度ずつ回転させれば、解の例2にあるような対戦方法
を得ることができる。

 解の特徴から、番号2〜6 の円順列を考えることにより、このパターンの解は、24通りある
ことが分かる。しかしながら、解の例 1 が存在することからも分かるように、このアイデアによ
り、この問題に対する解が全て得られるわけではないということに注意しなければならない。
 ただ、この方法を知っていれば、人数が比較的多い場合でも、解の一つが、同様に簡便に
求められるという点で優れている。

例 番号1、2、・・・16 の16人が、リーグ戦(総当り戦)を行う。同時に8試合ずつ15回戦を
  行う場合、どのように試合の順番を決めればよいか?

この問題を試行錯誤で求めることは、至難の業でしょう。アイデアを使うと、簡単に求められる。


       

 上と同様に、1〜15回戦を、記号 A〜O で表すとすると、解の一つとして、次の組合せが考
えられる。

  10 11 12 13 14 15 16
A B C D E F G H I J K L M N O
A I B J C K D L E M F N G O H
B I J C K D L E M F N G O H A
C B J K D L E M F N G O H A I
D J C K L E M F N G O H A I B
E C K D L M F N G O H A I B J
F K D L E M N G O H A I B J C
G D L E M F N O H A I B J C K
H L E M F N G O A I B J C K D
10 I E M F N G O H A B J C K D L
11 J M F N G O H A I B C K D L E
12 K F N G O H A I B J C D L E M
13 L N G O H A I B J C K D E M F
14 M G O H A I B J C K D L E F N
15 N O H A I B J C K D L E M F G
16 O H A I B J C K D L E M F N G

 上のアイデアを用いて、カークマンの女生徒の問題を解こうとしたが、なかなか上手い図が
見つからない。現在、検討中である。

(追記)
 ホームページ「数学の部屋」の「3人ゲームのリーグ戦」によれば、次のような図形が求める
ものの一つの例になるらしい。
          

 作り方のポイントは、同一円上の弦同士が、回転しても重ならないように配置するところで
ある。後は、上の図を、数字は固定したままで、1/7周ずつ回転させれば、求める解の一つ
を得ることができる。

 代数学的にも、カークマンの女生徒の問題は、興味ある問題のようだ。
(有限体GF(24)を、素体GF(2)上の4次元ベクトル空間と考えて、その中の35の平面を、
5平面ずつの7組に分ける(但し、5平面の和集合は、GF(24))問題と同じである。)

(参考文献:山本幸一 著 カークマンの女生徒の問題―数学100の問題― (日本評論社))

(追々記) 上記で、「カークマンの女生徒の問題」は一応決着をみた訳であるが、最近運動部
      の顧問の方から、次のような問題提起がなされた。

  番号1、2、3、4、5、6 の6チームが、リーグ戦(総当り戦)を行う。ただし、同時に可能な
 試合は、2試合で、残りの2チームでそれぞれの試合の審判を担当させたい。もっとも能率
 的に運営するには、どのように試合の順番を決めればよいのだろうか?

  6チームのリーグ戦なので、試合数は、15試合である。この15試合を、6チームで担当
 するので、1チーム当たりの審判回数は、2〜3回である。チームによって、審判回数に差
 が出ることを了解すれば、次のように試合の順番を決めればよいだろう。

          

 上の図で、緑色の針を時計回りに72度ずつ回転させる。まず、「5−4」の矢印に対応する
チームを審判とし、次の回転で「2−1」の矢印に対応するチームを審判とする。この操作を
繰り返し続け、緑色の針を2回転させる。このとき、次の表を得る。

 
A  B G C H D I E J
A F D I B G E J C H
B G D I E J C H A F
C H B G E J A F D I
D I E J C H A F B G
E J C H A F D I B G

 上記の表から、2度目の対戦となる場合、およびそれに付随する審判を除くことにより、次
のような試合の運営方法の一例ができる。

 
A   B G C   D I E  
A F D I B E   C H
B G D E C A
C H B E J A F D
D I E C A F B
E J C H A D B G

 上記の表の問題点は、若干の無駄があるというところである。試合も後半になれば、疲れ
が出て、1試合ずつ消化する方が健康的かもしれないが、問題を数学的にとらえれば、この
ことは、「能率的」という意味からは許されないことである。

 上記の表を更に工夫すれば、次の表が最善の表となるであろう。

 
A B F C D G E
A F D G B E C H
B F D E G C A
C H B E G A F D
D G E C A F B
E G C H A D B F
   A ・・・ 1回戦(2試合)
   B ・・・ 2回戦(2試合)
   C ・・・ 3回戦(2試合)
   D ・・・ 4回戦(2試合)
   E ・・・ 5回戦(2試合)
   F ・・・ 6回戦(2試合)
   G ・・・ 7回戦(2試合)
   H ・・・ 8回戦(1試合)

  黒字は、試合をする組
  赤字は、審判をする組

 ただし、表は横方向にみる
 ことにする。

 上記の表では、残念ながら、3試合連続となる場合が含まれている。生徒の負担を考え
れば、せいぜい連続する試合数は、2までとしたいのだが、これは数学的に考えて、可能
なのであろうか?直感的には、3と5が互いに素なので、多分不可能だと思うのだが、そこ
ら辺のところは、今後の研究課題としておこう。もし、証明が出来た方、こちらまで、メール
にてご教示下さい。

 以上、このような表が、高体連や高文連などの専門委員の方に使われることを希望して、
筆をおくことにする。