博士

ロボ子、今日のニュースはカードゲームのSetじゃ！1974年に考案されたらしいのじゃ。

ロボ子

Setですか、博士。知りませんでした。どんなゲームなのですか？

博士

81枚のカードを使うゲームで、各カードには4つの特徴があるのじゃ。数、形、模様、色、じゃ。

ロボ子

それぞれの特徴に3つのバリエーションがあるんですね。例えば、数は1つ、2つ、3つ、のように。

博士

そう！そして、3枚のカードの組み合わせが「セット」になる条件が面白いんじゃ。4つの特徴すべてにおいて、3枚が全部同じか、全部違う必要があるのじゃ！

ロボ子

なるほど。例えば、3枚のカードがすべて同じ色で、数が全部異なり、形も全部異なり、模様も全部異なれば、セットになるんですね。

博士

その通り！でも、どれか一つの特徴で、2枚が同じで1枚が違うと、セットにならないのじゃ。

ロボ子

デザイナーの方が遺伝学の仕事で使っていたコーディングシステムから発展したというのは興味深いですね。

博士

1991年にはMensa Select賞も受賞しているのじゃ！そして、つい最近、全米Set選手権が開催されたらしいぞ。

ロボ子

へえ、競技として成立するほど奥が深いんですね。

博士

ゲームのルールは簡単なのに、組み合わせ論が複雑なのじゃ。完全にランダムに選んだ3枚のカードがセットになる確率は1/79らしいぞ。

ロボ子

意外と低いんですね。セットが作れない最大のカードの組み合わせは20枚まで、というのも面白いです。

博士

12枚のカードの中にセットがない確率は30:1、15枚だと88:1らしいのじゃ。だから、ゲーム開始時にセットを見つけるのが難しいこともあるのじゃな。

ロボ子

約30%のゲームでは、最初に配られた12枚の中に必ずセットがあるんですね。運も重要そうですね。

博士

12枚のカードにおけるセットの平均数は約2.78個らしいぞ。最大で14個もセットがある場合もあるらしいのじゃ。

ロボ子

Setの一般化において、カードの組み合わせからSetが存在するかどうかを判断することがNP完全である、というのも興味深いです。計算量的な難しさがあるんですね。

博士

そう！Setは見た目以上に奥が深いゲームなのじゃ。ところでロボ子、今度私とSetで勝負しないか？

ロボ子

いいですね、博士。でも、博士は天才なので、私が勝てる見込みは薄いかもしれません…。

博士

大丈夫！私がハンデとして、カードを全部裏向きにしてプレイしてあげるのじゃ！

ロボ子

それだと、もはやゲームとして成立しない気が…。