ドブル (Dobble / Spot it!) 自作 (4): 2枚に2つのシンボルが共通するデッキ

## はじめに

ボードゲーム [ドブル](https://amzn.to/45XW20t) (Dobble / Spot it!) を Python 実装した **[dobble-maker][dobble-maker]** の解説です。

https://github.com/youce23/dobble-maker

本記事では、通常のドブルと異なる **任意の 2 枚のカードに必ず 2 つのシンボルが共通するデッキの構築** について説明します。

- [ドブルデッキの構築][art1]
  - 任意の 2 枚のカードを選んだ時に、必ず共通するシンボルが 1 つだけ存在するような組み合わせを決定する
- [カード内でのシンボルのレイアウト][art2]
  - シンボル間の重なり無く、程よくランダムに配置する
- [生成ツールの紹介][art3]
  - 画像ファイルから印刷用 PDF まで生成するツールの紹介
  - **仕組みはいいから作りたい！** という方はこちらです
- **2 枚に 2 つのシンボルが共通するデッキ**
  - 通常ドブルとは異なる特性を持ったデッキを作ります
- [3 枚に 1 つのシンボルが共通するデッキ][art5]
  - また別の特性を持つデッキです
- [派生版のアイデア帖][art6]
  - デッキの解釈を変えて新しいデッキについて考えてみます

[dobble-maker]: https://github.com/youce23/dobble-maker
[art1]: https://qiita.com/youce/items/e67b0bf50d955a98c70e
[art2]: https://qiita.com/youce/items/0cf902357b183500fb45
[art3]: https://qiita.com/youce/items/8cb30104759c1fe5f10f
[art4]: https://qiita.com/youce/items/aebd114ab01a8d0d4292
[art5]: https://qiita.com/youce/items/96497bcf5db616268685
[art6]: https://qiita.com/youce/items/547d732995be7c8ef839

## 更新履歴

2024/10/21: 以下の構成が誤りだったので削除
2024/10/5: ~~[付録: t-デザインによるデッキの構築](#付録-t-デザインによるデッキの構築) を追記~~

## ドブルの構成をパラメータ化

まずは今回やりたいことを説明するために、通常のドブルの構成をパラメータ化しながらおさらいします。

### 通常ドブルの場合

- 1 枚のカードに $k = 8$ 個のシンボルが存在
  - [過去記事][art1]では $N$ としていたパラメータですが、ここでは$k$に置き直します
- 全カード数は $b = 57$ 枚
  - [過去記事][art1]では $N * (N-1) + 1 = 57$ としていました
- 全シンボル数は $v = 57$ 個
  - 全シンボル数は全カード数と同じでした
- **2 枚のカードに 1 つのシンボルが共通**
  - ここは変数化せずにいったん置いておきます

### 今回作りたいドブルの場合

- カードあたりのシンボル数 $k$, 全カード数 $b$, 全シンボル数 $v$ は問わない
- **2 枚のカードに 2 つのシンボルが共通**
  - ここが通常版との差分です

本記事では、以下のスレッドを参考にしてデッキを構築していきます。

https://math.stackexchange.com/questions/3990502/algorithm-to-create-spot-it-dobble-cards-but-with-two-common-images-from-an

## ブロックデザインの導入

ここからは組み合わせ論の考え方の一つである **ブロックデザイン** を導入し、ドブルの各パラメータをブロックデザインでよく扱われる変数に当てはめていきます。

以下は[こちらの参考文献][ref2]に基づいて、ブロックデザインについて解説します。

### ブロックデザイン

まず、ブロックデザインでは、組み合わせ問題を以下のようにパラメータ化します。

- $v$ 種類の要素 $\lbrace V_1, ..., V_v \rbrace$ がある
- 複数の要素をまとめたものをブロック $B$ とし、そのブロックに含まれる要素の数をブロックの大きさとする
  - 例えばブロック $B_1 = \lbrace V_1, V_3, V_4 \rbrace $ は3つの要素を持つため、ブロックの大きさ $|B_1| = 3$ である
- さらに$b$ 個のブロックをまとめたセット $\lbrace B_1, B_2, ..., B_b \rbrace$ がある

ブロックデザインとは、このように何個かの要素を持つブロックを複数作り、ブロック間で「何らかのバランス」を持ったもののことです。

この「何らかのバランス」の決め方、つまり制約の与え方によって、ブロックデザインには名前が付けられています。

### t-デザイン

ブロックデザインに対して以下の制約を与えたものは、 **t-デザイン** と呼ばれています。

#### t-デザインの制約

- 各要素 $V_i$ は 1 つのブロックに重複して出現しない [^multiset]
  - 例えば $B_i = \lbrace V_1, V_1, V_2 \rbrace$ は許容しない
- 全 $b$ 個のブロック $\lbrace B_1, ..., B_b \rbrace$ について、各ブロックの大きさは、全て等しく $k$ である
  - 例えば ブロック $B_1 = \lbrace V_1, V_3, V_4 \rbrace$、$B_2 = \lbrace V_1, V_2, V_5 \rbrace$、$B_3 = \lbrace V_3, V_4, V_5 \rbrace$ から成るセット $\lbrace B_1, B_2, B_3 \rbrace$ は、各ブロックの大きさが $k=3$ と等しい
  - このため、もし $v = k$ とした場合、ブロックに全ての要素が含まれる、という自明の構成にしかならない。そのため $k < v$ という制約を付ける。
- 各要素 $V_i$ を含むブロックの数（＝$V_i$ の出現回数）は、全て等しく $r$ である
- 任意の $t$ 個の要素のセットについて、これらを含むブロックの数（＝ $t$ 個の要素セットの出現回数）は全て等しく $\lambda$ である
  - 例えば $\lbrace B_1 = \lbrace V_1, V_2, V_3 \rbrace, B_2 = \lbrace V_2, V_3, V_4 \rbrace, B_3 = \lbrace V_1, V_3, V_4 \rbrace, B_4 = \lbrace V_1, V_2, V_4 \rbrace \rbrace$ について考えると……
    - $t=2$ 個の要素セット（以下の全て）は、いずれも $\lambda=2$ 個のブロックに含まれ、制約を満たす
      - $\lbrace V_1, V_2 \rbrace, \lbrace V_1, V_3 \rbrace, \lbrace V_1, V_4 \rbrace, \lbrace V_2, V_1 \rbrace, ..., \lbrace V_3, V_4 \rbrace$

[^multiset]: ブロックデザインのブロックが要素の重複を許さない set （集合）なのか重複を許す multiset （多重集合）なのかわからなかったので、ここでは t-デザインで付与される制約としてしています。

**まとめると、以下を満たすものが t-デザインとなります。**

- 各ブロックの大きさは、常に一定値 $k$ である（$k < v$）
- 各要素の出現回数は、常に一定値 $r$ である（$r < b$）
- 任意の $t$ 個の要素セットの出現回数は、常に一定値 $\lambda$ である（$2 \leq t \leq k$ 及び $1 \leq \lambda < r$）

#### t-デザインの性質

ここまでの説明で出現した t-デザインのパラメータは、$v, b, r, k, \lambda, t$の 6 つです。ここでは、これらの関係について明らかにしていきます。

まず「すべてのブロックに出現する要素数の合計」を表す関係式として、以下の式（1）が得られます。

$$
bk = vr \qquad (1)
$$

- 左辺
  - 各ブロックの要素数（大きさ）は $|B_i|=k$ なので、 $\sum_i^b{|B_i|} = \sum_i^bk = bk$
- 右辺
  - $v$ 種類ある要素が、ブロック全体でそれぞれ $r$ 回ずつ出現するため、上記は$vr$と等しい

さらに「$t$ 個の要素セットの全パターンの総出現回数」を表す関係式として、以下の式（2）が得られます。

$$
\lambda \times {}_vC_t = b \times {} _kC_t \qquad (2)
$$

- 左辺
  - 任意の $t$ 個の要素セットのパターン数は、$v$種類の要素から$t$個を選択する総数なので、${}_vC_t$
  - 各要素セットはそれぞれ $\lambda$ 回ずつ出現するため、上記は $\lambda \times {}_vC_t$ となる
- 右辺
  - 各ブロックに含まれる $k$ 個の要素から $t$ 個を選ぶ方法は ${} _k C _t$ 通り
  - ブロック数は全部で $b$ 個あるため、上記は$b \times {}_kC_t$ と等しい

ここで（2）を変形して $b = \frac{\lambda \times {}_vC_t}{{} _k C _t}$とし、これを（1）に代入すると $r = \frac{\lambda \times {} _v C _t}{{} _k C _t}\frac{k}{v}$となります。

つまり、 **t-デザインは $v, k, \lambda, t$ の 4 つのパラメータで表現できます** （$b$, $r$はこれらが与えられれば算出できる）。そのため、t-デザインは **t-(v, k, λ) デザイン** と表記されることが多いです。

### BIBD

t-デザインに対して、さらに $t=2$ という制約を付けたものは、特に **BIBD: Balanced Incomplete Block Design** と名前が付いています。これは **2-(v, k, λ) デザイン** 、あるいは単に **(v, k, λ) デザイン** と表記されます。

BIBD の制約である $t = 2$ を式（2）に入れて展開すると、以下の関係が得られます。

```math
\begin{align}
\lambda \times {}_vC_t &= b \times {}_kC_t \\
\lambda \frac{v(v-1)}{2\times1} &= b \frac{k(k-1)}{2\times1} \\
\lambda v(v-1) &= b k(k-1) \qquad (3)
\end{align}
```

### 対称 BIBD

さらに、BIBD に対して $b = v$ の制約を付与したブロックデザインは **対称 BIBD（Symmetric BIBD）** と呼ばれます。対称 BIBD では式（1） $bk = vr$ と 制約 $b = v$ から、 $k = r$ という関係も成り立ちます。

ここで式（3）に$b = v$を入れて$v$について解くと、以下の関係が得られます。

```math
\begin{align}
\lambda v(v-1) &= b k(k-1) \\
\lambda v(v-1) &= v k(k-1) \\
\lambda (v-1) &= k(k-1) \\
v &= \frac {k(k-1)}{\lambda} + 1 \qquad (4) \\
\end{align}
```

ここで、対称 BIBD の各パラメータについてまとめます。

- $v$ 種類の要素 $\lbrace V_1, ..., V_v \rbrace$ がある
- $k$ 個の要素をまとめたブロック $B_i$ がある
- $b$ 個のブロックをまとめたセット $\lbrace B_1, B_2, ..., B_b \rbrace$ がある
- 各要素は $r = k$ 回出現する
- 任意の $t=2$ 個の要素セットは、 $\lambda$ 回出現する
- $b = v = \frac{k(k-1)}{\lambda} + 1$ である

## ドブルをブロックデザインのパラメータで表現

続いて、ドブルをブロックデザインの、特に対称 BIBD のパラメータで表現するために、先にまとめた対称 BIBD のパラメータを次のように言い換えます。

- $v = 57$ 種類のシンボル $\lbrace V_1, ..., V_{57} \rbrace$ がある
- $k = 8$ 個のシンボルをまとめたカード $B$ がある
- $b = 57$ 枚のカードを持つデッキ $\lbrace B_1, B_2, ..., B_{57} \rbrace$ がある
- 各シンボルは $r = k = 8$ 回出現する
- 任意の $t = 2$ 個のシンボルの組は、 $\lambda = 1$ 回出現する
- $b = v = \frac{8(8-1)}{1} + 1 = 57$ である

つまり、ドブルは $(v=57, k=8, \lambda=1)$ デザインである、ということです。

## 2 枚に 2 つのシンボルが共通するデッキ

さて、本記事の目的は「2 枚に 2 つのシンボルが共通するデッキ」を構成することでした。

これはつまり、 $t = 2$ 個のシンボルが同時に出現するカードが $\lambda = 2$ 枚となる $(v=\frac{k(k-1)}{2}+1, k, \lambda=2)$ デザインを解くことに相当します。

では、対称 BIBD の解はどのように得れば良いでしょうか？

実は、計算ソフトの SageMath では、BIBD を解く関数 `balanced_incomplete_block_design()` が提供されています（[リンク][sagemath_bibd]）。これに $v, k, \lambda$ を渡せば良いだけです。

SageMath はローカルにインストールし Python から呼び出すこともできるようですが、インストール不要でブラウザから実行できる [SageMathCell][sagemathcell] も公式から提供されているので、今回はこちらを用います。

それでは、 [SageMathCell][sagemathcell] に以下のコードをコピペして、`Language`を`Python`に切り替えて実行してみましょう。

```py:BIBDの計算
from sage.all import *

lambd = 2
for k in range(2, 11):
    v = k * (k - 1) / lambd + 1
    try:
        blocks = designs.balanced_incomplete_block_design(
            v,
            k,
            lambd=lambd,
            existence=False,
            use_LJCR=True
        ).blocks()
        print(f"k={k}: ", blocks)
    except Exception as e:
        print(f"k={k}: no blocks")
```

すると、以下の出力が得られます。$k$ 毎のデッキ構成が得られていて、その中から任意の 2 枚のカードを選ぶと必ず 2 つのシンボルが共通しています。

```py:計算結果
k=2: no blocks
k=3:  [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]]
k=4:  [[0, 1, 2, 4], [0, 1, 3, 6], [0, 2, 5, 6], [0, 3, 4, 5], [1, 2, 3, 5], [1, 4, 5, 6], [2, 3, 4, 6]]
k=5:  [[0, 1, 2, 6, 9], [0, 1, 5, 8, 10], [0, 2, 3, 4, 8], [0, 3, 5, 6, 7], [0, 4, 7, 9, 10], [1, 2, 3, 7, 10], [1, 3, 4, 5, 9], [1, 4, 6, 7, 8], [2, 4, 5, 6, 10], [2, 5, 7, 8, 9], [3, 6, 8, 9, 10]]
k=6:  [[0, 1, 2, 10, 11, 15], [0, 1, 4, 5, 6, 14], [0, 2, 3, 8, 9, 14], [0, 3, 6, 7, 10, 13], [0, 4, 9, 11, 12, 13], [0, 5, 7, 8, 12, 15], [1, 2, 7, 12, 13, 14], [1, 3, 4, 7, 8, 11], [1, 3, 5, 9, 13, 15], [1, 6, 8, 9, 10, 12], [2, 3, 4, 5, 10, 12], [2, 4, 6, 8, 13, 15], [2, 5, 6, 7, 9, 11], [3, 6, 11, 12, 14, 15], [4, 7, 9, 10, 14, 15], [5, 8, 10, 11, 13, 14]]
k=7: no blocks
k=8: no blocks
k=9:  [[0, 1, 3, 7, 17, 24, 25, 29, 35], [0, 1, 5, 11, 13, 14, 16, 20, 30], [0, 2, 3, 5, 9, 19, 26, 27, 31], [0, 2, 6, 16, 23, 24, 28, 34, 36], [0, 4, 10, 12, 13, 15, 19, 29, 36], [0, 4, 14, 21, 22, 26, 32, 34, 35], [0, 6, 8, 9, 11, 15, 25, 32, 33], [0, 7, 8, 12, 18, 20, 21, 23, 27], [0, 10, 17, 18, 22, 28, 30, 31, 33], [1, 2, 4, 8, 18, 25, 26, 30, 36], [1, 2, 6, 12, 14, 15, 17, 21, 31], [1, 3, 4, 6, 10, 20, 27, 28, 32], [1, 5, 15, 22, 23, 27, 33, 35, 36], [1, 7, 9, 10, 12, 16, 26, 33, 34], [1, 8, 9, 13, 19, 21, 22, 24, 28], [1, 11, 18, 19, 23, 29, 31, 32, 34], [2, 3, 7, 13, 15, 16, 18, 22, 32], [2, 4, 5, 7, 11, 21, 28, 29, 33], [2, 8, 10, 11, 13, 17, 27, 34, 35], [2, 9, 10, 14, 20, 22, 23, 25, 29], [2, 12, 19, 20, 24, 30, 32, 33, 35], [3, 4, 8, 14, 16, 17, 19, 23, 33], [3, 5, 6, 8, 12, 22, 29, 30, 34], [3, 9, 11, 12, 14, 18, 28, 35, 36], [3, 10, 11, 15, 21, 23, 24, 26, 30], [3, 13, 20, 21, 25, 31, 33, 34, 36], [4, 5, 9, 15, 17, 18, 20, 24, 34], [4, 6, 7, 9, 13, 23, 30, 31, 35], [4, 11, 12, 16, 22, 24, 25, 27, 31], [5, 6, 10, 16, 18, 19, 21, 25, 35], [5, 7, 8, 10, 14, 24, 31, 32, 36], [5, 12, 13, 17, 23, 25, 26, 28, 32], [6, 7, 11, 17, 19, 20, 22, 26, 36], [6, 13, 14, 18, 24, 26, 27, 29, 33], [7, 14, 15, 19, 25, 27, 28, 30, 34], [8, 15, 16, 20, 26, 28, 29, 31, 35], [9, 16, 17, 21, 27, 29, 30, 32, 36]]
k=10: no blocks
```

以上により、 無事に **「2 枚に 2 つのシンボルが共通するデッキ」が構築できました** 。

## 別案: ガッチャンコ方式

ブロックデザインで解くのも非常に美しくて良いのですが、今回参考にした [こちらのスレッド][ref1] では、通常版ドブルを 2 つ作って結合する方式（ガッチャンコ方式）も投稿されていたので、紹介します。

[dobble-maker][dobble-maker] の `v0.8.0` では、 $k$ 次第でブロックデザイン方式とガッチャンコ方式を切り替えて使っています。

以下、 $k = 6$ の例で作り方を説明します。まず、カードあたりのシンボル数 $k/2$ で通常版ドブルを作ります。

```math
\begin{matrix}
0 & 1 & 4 \\
2 & 3 & 4 \\
0 & 3 & 5 \\
2 & 1 & 5 \\
0 & 2 & 6 \\
1 & 3 & 6 \\
4 & 5 & 6 \\
\end{matrix}
```

これを 2 つ作って、各デッキから適当な 2 枚のカードを選択して結合します。

```math
\begin{matrix}
0 & 1 & 4 & 0' & 1' & 4' \\
2 & 3 & 4 & 2' & 3' & 4' \\
0 & 3 & 5 & 0' & 3' & 5' \\
2 & 1 & 5 & 2' & 1' & 5' \\
0 & 2 & 6 & 0' & 2' & 6' \\
1 & 3 & 6 & 1' & 3' & 6' \\
4 & 5 & 6 & 4' & 5' & 6' \\
\end{matrix}
```

以上です。この方法で作ったデッキの特徴は以下です。

- カードあたりのシンボル数 $k = 2×(素数の累乗+1)$
- カード枚数 $b = \frac{k}{2}(\frac{k}{2}-1) + 1$
  - ブロックデザイン方式では $\frac{k(k-1)}{2} + 1$ であり、カード枚数は約半減する
- 全シンボル数 $v = 2b = k(\frac{k}{2}-1)+2$
  - ブロックデザイン方式では $\frac{k(k-1)}{2} + 1$ であり、必要なシンボル数はほぼ変わらない
- 各シンボルの出現回数 $r = \frac{k}{2}$
  - ブロックデザイン方式と比べて、半減する
- 2 枚のカードに共通して出現する 2 つのシンボルのセットは、限定的
  - 例えば上記のデッキであれば、任意の 2 枚のカードの共通シンボルとして出現するのは $\lbrace a, a' \rbrace$のみ

このようにブロックデザイン方式と比べると制限があります。

$k$ のバリエーションが増えるため選択肢としてあって良いとも思いました。一方で、共通して現れるシンボルセットが非常に限定的なため、何度か遊んでいるとシンボルセットを覚えてしまうかもしれませんね。

## 最後に

本家ドブルに同梱の説明書には、以下の記載があります。

> 1976 年に、Jacques Cottereau 氏は、「15 人の女学生がいる。この女学生たちは、毎日 3 人ずつ 5 組の班に分かれて登校する。1 週間のうちに、どの学生も他の 14 人とちょうど 1 回ずつ一緒に登校できるように、一週間の班の振分けを考えよ。」という有名な数学パズル「カークマンの女学生問題」より着想を得ました。
>
> 誤り訂正符号の定理から導き出された手法の助けを借りて、彼は問題を一般化したいくつかの構造に構築しました。この構造は数学者の間では「ブロックデザイン」と呼ばれています。
>
> これらの構造（交差と最適化の公理）の特別な解に基づき、Jacques Cottereau 氏はこの構造に肉付けをするという今までにない方法で 2 つのゲームを続けて作りました。

ドブルはもともとブロックデザインから発生している、ということですね。

次の記事では「3 枚に 1 つのシンボルが共通」する構成について説明する予定です。そちらは誤り訂正符号に基づきデッキを構成するので、Jacques Cottereau 氏の考え方を逆から追うような形になっています。

ちなみにカークマンの女学生問題は[このスライド][ref3]がわかりやすかったです。

## 参考

- [Algorithm to create "Spot It"/"Dobble" cards, but with two common images from any two cards][ref1]
  - 今回の記事は、上記のサイトの Travis Willse 氏の回答をヒントに作成しました
  - 最初から`One can generate such a deck with a symmetric block design`と書かれているのですが、「symmetric block design」を理解して、その解法を探すのに偉く時間がかかりました……
- [ブロック・デザインと符号][ref2], 中村（信州大工）, オペレーションズ・リサーチ, vol.23, no.8, pp.497-503, 1978.
  - ブロックデザインの非常にわかりやすい解説です
- [カークマンの女学生問題と有限幾何][ref3]
  - カークマンの女学生問題は2-(7, 3, 1)デザインという話

[ref1]: https://math.stackexchange.com/questions/3990502/algorithm-to-create-spot-it-dobble-cards-but-with-two-common-images-from-an
[ref2]: https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.23_08_497.pdf
[ref3]: https://www.slideshare.net/slideshow/ss-27340068/27340068

[sagemath_bibd]: https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/designs/bibd.html#sage.combinat.designs.bibd.balanced_incomplete_block_design
[sagemathcell]: https://sagecell.sagemath.org/

## 付録: t と λ とドブルのルールについて

本文ではさらっと流しましたが、BIBD における $t$ と $\lambda$の関係と、ドブルにおけるカード枚数と共通シンボル数の関係は、直接は一致していません。

- BIBD の場合、「 $t$ 個の要素セットの出現回数は $\lambda$ 」である
- ドブルの場合、「2 枚のカードに共通するシンボル数は 1」である

以下では、この点について説明を補足します。

### t = 2、λ = 1 の対称 BIBD と通常ドブルの関係

「$t = 2$ 個のシンボルセットが出現するカードは必ず $\lambda = 1$ 枚」となる対称 BIBD が、通常ドブルの条件である「2 枚のカードに共通するシンボル数は必ず 1」を満たすことを証明します。

<details><summary>【証明】</summary>

---

まず、対称 BIBD の条件より以下が成り立ちます。

- カードの枚数 $b$ は、シンボルの種類数 $v$ に等しい（ $b = v$ ）
- 各シンボルを持つカード枚数 $r$ は、 カードあたりのシンボル数 $k$ と等しい（ $r = k$ ）
- 任意の $t = 2$ 個のシンボルは、 $\lambda = 1$ 枚のカードにのみ出現する
- 式（4）より $\lambda (v-1) = v-1 = k(k-1)$

上記を踏まえて、あるカードに着目して共通シンボル数について考えます。

- あるカード（着目カード）には $k$ 個のシンボルが含まれている
  - 例えば $k = 8$
- 着目カード内のあるシンボルを持つカードの枚数は、着目カードを除くと $(r-1)$ 枚
  - 特定のシンボルを持つカードの枚数は、全体で $r$ 枚のため
  - 例えば、シンボル A を持つカードは、着目カードの他に 7 枚ある
- 着目カード内の $k$ 個の各シンボルは、それぞれが $(r-1)$ 枚のカードと共通していて、それらは重複しない
  - 例えば着目カードがシンボル A と B を持ち、A を持つカードは他に 7 枚あり、B を持つカードもまた他に 7 枚あり、A と B を同時に持つカードは着目カード以外に存在しない（ $t=2$ 、 $\lambda=1$ であるため）
- よって、着目カードと共通するシンボルを持つカードの枚数は、 $k(r-1)$ 枚
  - 着目カードが 8 個のシンボルを持つなら、それと共通するシンボルを持つカードの枚数は $8 \times (8-1) = 56$ 枚
- 着目カードと共通するシンボルを持たないカードの枚数は、以下より 0 になる
  - 着目カード以外のカードの枚数は $(b-1)$ 枚
  - 着目カードと共通するシンボルを持つカードの枚数は $k(r-1)$ 枚
  - 着目カードと共通するシンボルを持たないカードの枚数は
    ```math
    \begin{aligned}
    (b-1) - k(r-1) &= (v-1) - k(k-1) \\
    &= k(k-1) - k(k-1) \\
    &= 0
    \end{aligned}
    ```

---

</details>

すなわち、対称 BIBD により構成されるデッキは以下を満たし、通常ドブルの条件を満たします。

- 任意の 2 枚のカードは必ず共通するシンボルを持つ
  - 上記より、任意のカードと共通するシンボルを持たないカードは 0 枚であるため
- 共通するシンボルを持つ任意の 2 枚のカードは、2 個以上のシンボルを共有しない
  - もし 2 枚のカードが 2 個（以上）のシンボルを共有すると、それは 「$t=2$ 個のシンボルセットは $\lambda=1$ 回のみ出現する」前提に違反するため、あり得ない

### t = 2、λ = 2 の対称 BIBD と拡張ドブルの関係

同様に、「$t = 2$ 個のシンボルセットが出現するカードの枚数は $\lambda = 2$ 枚である」対称 BIBD を構築することで、本記事の目的である「2 枚のカードに共通するシンボル数は必ず 2 である」拡張版ドブルを構築できることを証明します。

<details><summary>【証明】</summary>

---

先ほどと同様に、対称 BIBD の条件より以下が成り立ちます。最初の 1 つは先ほどと同じで、あとの 2 つが異なります。

- カードの枚数 $b$ は、シンボルの種類数 $v$ に等しい（ $b = v$ ）
- 任意の $t = 2$ 個のシンボルは、 $\lambda = 2$ 枚のカードにのみ出現する
- 式（4）より $\lambda (v-1) = 2(v-1) = k(k-1)$

続いて、あるカードに着目して共通シンボル数について考えます。

- あるカード（着目カード）には $k$ 個のシンボルが含まれている
- 着目カード内のある $t=2$ 個のシンボルセットを持つカードの枚数は、着目カードを除くと $(\lambda-1)$ 枚
- 着目カード内の ${} _k C _{t=2}$ 個の各シンボルセットは、それぞれが $(\lambda-1)$ 枚と共通する
- よって、着目カード内の ${} _k C _{t=2}$ 個の各シンボルセットと共通するシンボルを持つカードの枚数は、 ${} _k C _{t=2} \times (\lambda-1)$ 枚
- 着目カードと共通する $t=2$ 個のシンボルセットを持たないカードの枚数は、以下より 0 になる
  - 着目カード以外のカードの枚数は $(b-1)$ 枚
  - 着目カードと共通する $t=2$ 個のシンボルセットを持つカードの枚数は ${} _k C _{t=2} \times (\lambda-1)$ 枚
  - 着目カードと共通する $t=2$ 個のシンボルセットを持たないカードの枚数は
    ```math
    \begin{aligned}
    (b-1) - {}_kC_{t=2} \times (\lambda-1) &= (b-1) - \frac{k(k-1)}{2 \times 1} \times (2-1) \\
    &= (b-1) - \frac{k(k-1)}{2} \\
    &= (v-1) - \frac{k(k-1)}{2} \\
    &= \frac{k(k-1)}{2} - \frac{k(k-1)}{2} \\
    &= 0
    \end{aligned}
    ```

---

</details>

上記より、任意の 2 枚のカードは、必ず少なくとも 2 個のシンボルを共通して持つことが言えます。

加えて、任意の 2 枚のカードが 3 個以上のシンボルを共有しないことを証明したいのですが、 **できませんでした……** どなたか教えてください。