amori's blog

よろず技術系と趣味関係の雑記です

カードゲーム ドブル(Dobble)の数理

ドブル(Dobble)というカードゲームをご存知でしょうか
本家はこちら
https://hobbyjapan.co.jp/dobble/

ゲームの感じはこちらがわかりやすいでしょう
http://primaryplus1.com/dobble

全部で55枚のカードにそれぞれ8つの絵というかシンボルが描かれており、任意の2枚のカード間でひとつだけ同じシンボルがあるようになっていて、この仕組みを使ったゲームが色々と遊べるようになっています。

単純に二つのカードで共通のシンボルを早い者勝ちで宣言する、というシンプル極まりないルールでも結構盛り上がりそうです。

さて、ここで興味深いのは「任意の2枚のカードで共通のシンボルが必ずひとつしかない」という構成です。
全てのカードに共通なひとつのシンボル、という自明な構成を除き、その構成はどのようになっているのでしょうか。

少ない数から試してみましょう。

例えばシンボルが一枚あたり2個ならば、{A,B}{B,C}{C,A}と3枚になり、
3個なら、

A B C
A D E
A F G
B D F
B E G
C D G
C E F

と7組でシンボルも7つになります。

4つ以上になるとなかなか複雑になってきて直感的に構成するのはちょっと難しいです。
そして1枚当たり8シンボルのDobbleでは全部でいくつシンボルが必要で、そしてカードの数が何故55枚になるかは、なかなか興味深い問題です。

で、結論から言いますと55枚の理由はわかりませんでした(^_^;)

いや、導出法はわかったのです。
しかしその結果は最大57枚になるはずなんですよ。
なんで55枚なんだろなあ。
もしかしたら遊ぶ時の配分の関係か、商品化で枚数制限があったのかもしれません・・


それでは、ドブルにおけるシンボル数とカードの最大数の関係およびシンボルのパターンの導出について解説しましょう。

まずはカードの数。
シンボル数をnとした場合のカードの最大数はn×(n-1)+1です。Dobbleでは8×7+1=57枚です。この時必要なシンボルの数も同じです。

既に示したn=2の時は3、n=3の時は7となってます。

ただし、全てのnに対してこれが成立するわけではなく、n=p^k+1 つまり素数の冪乗+1の時にこの最大値になります。
・・・たぶん(^_^;)

実はこの条件での導出方法はわかったんですが、その他の場合に最大値になる構成はできないということは証明できてなくてたぶん無理だろうというところまでしかわかりませんでした。

以下にその導出法を説明します。
1. まずm=n-1について、m人ゲームのm^2人総当たり問題を解きます。これはm=4の場合、いわゆる16人麻雀総当たり問題と呼ばれるものです。
2. 1からm人m組がm+1回戦する組み合わせが求まります。
3. k回戦の各組に「k」を追加します。
4. 1からm+1からなる組を追加します。
5. 以上でm×(m+1)+1=n×(n-1)+1組が求められ、これがDobbleのカードに相当する組み合わせになります。

具体的にn=4の例で説明します。
1.の3人ゲームの9人総当たりは4回戦になりa-iで組み合わせると、

a d g a b c a b c a b c
b e h d e f f d e e f d
c f i g h i h i g i g h

となります。縦の3つがひとつの組です。
これに全4回戦に一人づつ加えて、さらに1組足します。

1 1 1 1 2 2 2 3 3 3 4 4 4
2 a d g a b c a b c a b c
3 b e h d e f f d e e f d
4 c f i g h i h i g i g h

この13組の任意の2組について必ず同じものがひとつだけとなっています。
これは総当たり組み合わせの特徴から明らかで、例えば1回戦のa,b,cの組の3つは他の回戦で必ず別々の組になっています。ですからこのa,b,cの組と2〜4回戦の任意の組とでは必ずaかbかcのどれかひとつだけが一致します。
また各回戦の全組に共通のものを加えたので、回戦内の任意の2組でもそれが唯一の一致するものになります。
あと全回戦の要素で1組追加でき、これも当然他の組とはひとつしか共通要素がありません。

ドブルのカードの場合は、7×7人総当たりを求めて57通りの組を導出することができます。ドブルのカードのシンボルの数は57通りらしいので、理論的にはあと2枚追加可能です(^_^)

この導出法は、m人ゲームm×m総当たり問題が導出可能である限り適用可能であり、その導出法は有限体の性質から導くことができ、有限体の位数(要素数)の条件「mが素数の冪乗」がそのまま条件になります。

この導出法については「麻雀16人組み合わせ問題」として有限体の応用として有名ですので(^_^;)例えば
http://www.ne.jp/asahi/music/marinkyo/matematiko/kombinajxteorio.html.ja
を参照ください。ここに有限体を用いた一般化について必要なことは、教科書の引用ですが、全部書かれています。

以上から有限体の位数の条件、2,3,4,5,7,8,9,11,13,16,17,19,,,
で総当たりが可能なので、
3,4,5,6,8,9,10,12,14,17,18,20,,,.
で,ドブル構成(と、とりあえず呼びます)の最大数を導けることになります。

これが「最大」であることについては別にまた証明が必要ですが、意外に簡単に説明できるので別途説明します。

さて、「有限体とならない位数で総当たりができない→Dobble構成の最大値とならない」か、どうかは自明ではありません。わたしには証明できていません。
しかし、例えばn=7でDobble構成が可能となるならば、逆にm=6で総当たり組み合わが可能であることは、導出手順の4,→3.で明らかです。そして総当たりの組み合わせは有限体の条件によって同形でユニークに求められているので、逆に有限体となることが必要になり矛盾する、のではないかと思います。
(すみません、感覚的でして証明は出来てません..)

以上、ドブル構成の導出方法についてまとめました。その気になれば自分の好きなシンボルでオリジナルのドブルつくれますよ。

ちなみにシンボル数6と10についてはdobbleのアプリでオプションになってました。

ドブルの数理(2) に続きます。
http://amori.hatenablog.com/entry/2016/10/10/030856