ドブルというカードゲームがある。
英語ではSpot it!
このゲームは次のような性質を満たす（という）55枚のカードから成る。
それぞれのカードには8つの互いに異なるマークが描かれている。
どの2枚のカードを選んでもちょうど1つの同じマークが描かれている。
例えば、マークを自然数で表すとして、ドブルに含まれるカードを3枚抜き出したところ、(1,2,3,4,5,6,7,8), (3,10,21,39,41,46,50,55), (7,16,20,31,39,40,52,53)となっていたりするわけです。
1枚目と2枚目は「3」を共有しており、2枚目と3枚目は「39」を共有しており、1枚目と3枚目は「7」を共有している。
このカードセットに(11,15,23,29,30,42,51,54)や(2,11,20,21,33,46,47,48)というカードは含まれない。というのは、前者は先の1枚目と1つもマークを共有しないし、後者は先の2枚目のカードと2つマークを共有してしまうから。
このような条件を満たすマークの描かれたカードの集まりを、「ドブルのカードセット」とか単に「カードセット」と呼ぶことにする。
さて、数学的には
- ドブルのカードセットはそもそも存在するか
- 存在するとしてとしてマークは何種類あるのか、そのマークの種類としてありうる最小値最大値はいくらか。
- 存在するとして、「あるマークが何枚のカードに登場するか」という数はどのように分布しているか。
- 存在するとして、本質的に異なる（例えばマークの「ラベルの張り替え」によって互いに移りあわない）カードセットは何種類あるのか
などの疑問がわいてくる。
（まぁ商品としてドブルを売ってる以上そのようなカードセットは存在はするであろうという推測が成り立つが）
あまり高度な数学を使うわけではない考察によって、
- ドブルのカードセットが満たすべき条件として、「あるマークが何枚のカードに登場するか」の分布についてのある種の制限と、マークの種類としてありうる数
を決定し、
- ドブルのカードセットが存在すること
をそのような例を構成することにより証明できたのでここに紹介する。
長くなるので、カードセットの構成は次回に回し、今日はこの必要条件の方についてだけ書く。
ドブルのカードセットが満たすべき条件
まず、条件を満たすようなカードのセットがあったとして、そのようなカードセットが満たすべき必要条件について考察する。
まず、自明なカードセットとして、ある1つのマークが全てのカードに描かれており、そのマーク以外の7つのマークは全てのカードで異なる、つまりマークは全部で7*55+1=386種類あるようなものがある。
このようなカードセットは条件を満たしているが、基本的に以下ではこのような場合は「自明な場合」として、考慮しないことにする。
1枚カードを固定する。これをc1と名付ける。
これに描かれているマークを1, 2,…,8の自然数で表す。
他の54枚のカードの中うちどのカードも、c1とちょうど1個だけマークを共有している。
他の54枚のうち、マーク1を持つカードを全て集めたグループをA_1、マーク2を持つカードを全て集めたグループをA_2、…マーク8を持つカードを全て集めてきたグループをA_8とする。
もちろん、この時点では、マークn(1≦n≦8)を持つカードはc1だけかもしれないので、A_nが空集合ということもありうる。
しかしあるカードが異なる1≦i
さて、冒頭で述べたような自明な場合を除けば、ある相異なるi,jがあって、グループA_iとA_jはともに空集合でない。*1
A_iに属するカードを1つ固定し、これをc2とする。
A_jに属するカードを取ってくる。これをx1とする。
c2とxはマークをちょうど1つ共有しているが、そのマークはiでもjでもない（もし共有するのがiやjならそのカードはc1と2つ共有するマークがあることになってしまう）。
c2がxと共有するそのiでもjでもないマークをM(x1)とする。
A_jに属するx1と別のカードx2について、x2がc2と共有するマークをM(x2)とするとき、
M(x1)とM(x2)は異なるマークでなければならない。
なぜならば、M(x1)=M(x2)ならば、x1とx2は、M(x1)とjという2つのマークを共有することになり条件に反するからである。
同様に、A_jに属する各カードに対応して、c2はそのカードと共有するマークを持たなければならないが、そのマークは、A_jに属するカード毎に別のマークでなければならない。むろんそれらはiとも異なるマークでなければならない。
よって、A_jに属するカードはたかだか7枚であることがわかる。
（というのは、c2が持ちうるiとは異なるマークはちょうど7種類であり、もしA_jに8枚以上のカードが属するなら引き出し論法によりA_jに属するある2枚について、それらがc2と共有するマークは共通であることになり、このときこの2枚はjとこのマークという2つのマークを共有することになるからである*2）
ここでA_i, c2, A_jは（A_i, A_jは空でないという条件のもとで）任意にとることができたから、任意のn(1≦n≦8)に対しA_nに属するカードは7枚以下であることがわかる。
このことにより、各グループが含むカードの枚数の割り振りはかなり限られる。
A_nに属するカードの枚数を|A_n|で表す。
ちょうど7枚属するグループが5個以下しかないと仮定すると、A_1からA_8までのグループに属するカードの枚数の合計は、7*5+6*3=53以下となるが、このA_1, …, A_8に属するカードの合計はちょうど54になるはずだからである。
よってちょうど7枚属するグループは6個以上あることになり、そうすると、各グループに属するカードの枚数は、順番を無視して
{7,7,7,7,7,7,6,6}か{7,7,7,7,7,7,7,5}しかありえない。
特に、空集合はない。
今までカードc1を固定して議論してきたが、この議論はc1がどのカードであっても成り立つことである。
今までの結果をいったん定理の形で述べておく。
定理1
カードcを固定する。
カードcに現れるマークをM1,…M8とし、残りの54枚を、このカードcと共有するマークによって類別したグループを、（対応する順に）A_1,…A_nとするとき、これらは残りの54枚の分割になっており、かつ、各グループに属するカードの枚数の割り振りは、順不同で、{7,7,7,7,7,7,6,6}か{7,7,7,7,7,7,7,5}のどちらかである。
さて、引き続きカードc1を固定し、グループA_1,…A_8を用いる。
（必要ならばグループ名を付け替えて）グループA_1には7枚のカードが属するとして一般性を失わない。A_1に属する7枚のカードは、互いにマーク1を共有し、共有するマークはそれだけであることから、残りのマークの「空き枠」7*7=49枠は、全て互いに相異なる49種類のマークから成ることがわかる。
またこの49種類は、c1に属する1-8のマークとも異なるマークである（そうでなければc1と2つ以上共有する）。
つまり、今まででこの49種類のマークとc1のマーク1-8の、合計57種類のマークが存在することがわかっている。
この57種類のマーク以外の「未発見の」マークがあるだろうか。
それがないことを以下に示す。
さて、A_1以外のグループA_2,…,A_8のどれか（A_iとする(2≦i≦8)）に属するカードc3を1つ固定する。
c3はA_1に属するどの7枚ともちょうど1つマークを共有するが、先ほどと同様の議論により、c3がA_1のあるカードd1と共有するマークと、A_1の別のカードd2と共有するマークは異なる。
つまりc3は、A_1の7枚の各カードと共有するための別々の7種類のマークを持っている。
そしてこの7種類のマークとは別に、A_iに属するのだからマークiも持っている。
c3が持っているマークはこの8つで全部である。
つまり、c3は既に存在がわかっている57種類のマーク以外のマークを持たない。
c3は任意だから、A_2,…A_8に属するどのカードも、この57種類のマーク以外のマークを持たない。
以上より、このドブルのカードに描かれているマークは全部でちょうど57種類であることがわかる。
定理2
ドブルのカードに描かれているマークは全部でちょうど57種類である。
