じゃんけんから未解決問題へ

昨日までの経緯。

〜じゃんけんの手の種類を2n+1に拡張する方法は(2n)!通りあると思い込んで証明できたと思ったら間違っていた〜

そんなこんなで、じゃんけんの拡張についてあーだこーだ考えているうちに、未解決問題にぶちあたりました。

まずは、手をr種類に拡張した「じゃんけん」を定義し、そこから考えます。
以下の2つの条件が満たされるとき、これをr-じゃんけんと呼ぶことにします。
条件1.r種類ある手のうち、任意の異なる2つの手の間に強弱関係が定義されている（同じ手の強さは同一とする）。
条件2.手によって勝ちやすさ、負けやすさの差がない。言い換えると、勝てる手の数と負ける手の数は、どの手も等しい。

この2条件のもと、手の種類が偶数の場合にはr-じゃんけんが存在しないことは昨日の記事に書いた通り。
手の種類が奇数の場合にはr-じゃんけんが存在することは明らかなのですが、それでは、それは何通りあるのか、ということが問題になっていたのでした。

手作業で調べた結果、手が3種類のときは2通り、手が5種類のときは24通りあることが分かりました。
3→2=(3-1)!
5→24=(5-1)!
そのようなわけで、手が2n+1種類の場合には、じゃんけんが(2n)!通りあるのではないか、という安易な予想が立ったのですが、証明できたと思ったものの不備が見つかり、その後、いくら考えても証明できませんでした。
とりあえず、拙いプログラムを書いて検証してみたところ、手が7種類のときには2640通りになることが分かり、予想が間違っていたことが分かりました。

さあ大変。困りました。
そこで、数列を検索できる
The On-Line Encyclopedia of Integer Sequences
というサイトで、2,24,2640を検索してみました。
すると、見つかりました。これです。
見てみると、
「Number of labeled regular tournaments with 2n+1 nodes.」
と書かれています。
やはり、グラフ理論に関係があるようです。

ここで、話を分かりやすくするために、用語を定義しておきます。
完全グラフ：任意の2頂点間に辺が存在するグラフ
トーナメント：完全グラフの各辺に向きを付け、有向グラフとしたもの
正則（有向）グラフ：有向グラフのうち、各頂点の入次数と出次数が等しいもの

これらの用語を使うと、r-じゃんけんの定義を正確に述べることができます。
条件1.により、各手の強弱を矢印を使って表すことにすると、トーナメントが出来上がります。
また、条件2.により、グラフは正則になります。
したがって、r-じゃんけんとはすなわち、頂点数がrの正則トーナメントのことに他なりません。
よって、頂点数がrの正則トーナメントの数を求める公式を導くことが、今回の目的だと言い換えることができます。やったね。

それで、色々と調べた結果、公式が見つかっていないことが分かりました。
あれまー。未解決問題だったのね。
ただ、何だか安心しました。ちょっとくらい考えたって、解けなくて当たり前なのですから。

ちなみに、漸近公式は見つかっているようで、学術論文が公開されています。

たかがじゃんけんと言えども、その背景には数学的に難しい問題をはらんでいるのですね。