プリクラ問題の特殊解の図示

プリクラ問題とは

プリクラ問題とは、@hiroko_TB あしやまひろこ氏による、次のような問題である。

このとき、

マージャンのテーブル割当て

この問題は、共立出版『アルゴリズム辞典』の「ブリッジのテーブル割当て」の項にある、マージャンのテーブル割当て、という問題に似ている。まずブリッジのほうから説明する。(後から気付いたが、『数理パズル』により詳しい話があった。最後に追記してある)

ブリッジのテーブル割当て

名前には「ブリッジの」とあるが、問題内には実のところブリッジらしい点は特にない。従って以下の説明の読解にはブリッジ(コントラクトブリッジ)の知識は必要ない(おそらく同辞典の筆頭編集委員であった島内剛一先生の趣味ということであろう(島内先生は同辞典編纂中に59歳で急逝されている))。

ブリッジのテーブル割当てとは、

よって、常に待機チーム無し(もちろん重複なし)で上手に進行させれば、2n-1回(下限)で全対戦を組むことができそうだが、その具体的組合せは? □

この問題は次のように図を使って簡単に解くことができる。例として n==3 つまり6チームの場合の図を示す。

ドットが各チーム、ドットを結ぶ直線が対戦相手を示す。最初の回でこのように組合せたとして、次、その次は、点の配置が 1/5 の回転対称となっているから、順に回転させてゆけばよい。直観的に明らかなように、対戦が重複することはないし、下限である5回で全対戦が行われる。

nを任意の自然数として2nチーム、すなわちどんな偶数個チームの場合にも、このような図を描けることも直観で類推できるだろう。

マージャンのテーブル割当て

以上の手法を、

(マージャンは4人ゲームなので、4卓あれば16人が同時にプレイできる)
このとき、5回の対戦で誰が誰とも1回打っているようにすることが可能であることを具体例で示せ(3×5==15であるから、これも下限である)。 □

という問題に応用してみる。すると、次のような図が描けて、そのような対戦が可能であることがわかる。

一般化とプリクラ問題への応用

『アルゴリズム辞典』に書かれているのはここまでで、nを任意の自然数として4n人のマージャン大会について考える一般化や、m人ゲームについて考える一般化は与えられておらず、このような図がいつもうまく描けるか、は同書からは不明である。また、プリクラ機の定員をm人として人数がmの自然数倍の時という、プリクラ問題の特殊解と一致する。

ブロックデザイン

ブロックデザインの表現では「マージャンのテーブル割当て」は「分割可能 2-(16, 4, 1) デザイン」ということになる。ここで「カークマンの女学生問題」こと「分割可能 2-(15, 3, 1) デザイン」を同じ手法で図示してみようとしてもうまくできない(総当たりで確認)。2-(v, k, 1) デザインの、k が 2 の場合は最初のブリッジのようにうまくいく。しかし k が 2 より大きくて v に対して小さめの場合は、この手法はうまくいかない。「分割可能 2-(9, 3, 1) デザイン」であれば次のようにうまくいく。

次は「分割可能 2-(25, 5, 1) デザイン」の場合である。

前述のように、女学生問題の場合にうまくできないのは、内側の多角形を、2種類の異なった三角形にする必要があるが、それは不可能であるためである。
(というか、このような手法でうまくいかない問題として示されたのが「カークマンの女学生問題」なのか?)

v = k2 の場合に、以上の図による手法はうまくいく可能性がある(?)。

『数理パズル』にある解説

中公新書『数理パズル』 pp. 178 〜 187 の「図形で作るリーグ戦の組み合わせ」に、同様の問題がある。同書は分担執筆であるが、この部分の担当は中村義作先生である。

やはり趣味からであろうか、2人の対戦については相撲の取組として説き起こしている。n人ゲームのn2人による総当たり戦について、このページにここまで書いたものと同様の解説があり、3人以上の場合の出典は筆者自身による考察となっている。3人ゲーム9人の場合と、カークマンの問題(3人ゲーム15人、あるいはもっと多い)について簡単に紹介した後、マージャン(4人ゲームを16人)、5人ゲーム25人の場合の図示があり、6人ゲーム36人の場合は作れないが7人や8人の場合は作れる、同様にどんどん増やしてゆくと作れる場合と作れない場合がある、といったように説明が続いています。