初期手札のうち詰んでるセットはいくつあるのか - 素数大富豪が8121013倍強くなりたい

この記事は素数大富豪 Advent Calendar 2022 - Adventarの14日目の記事です。昨日はカステラさんによるオンライン素数大富豪大会「梅森戦」告知 - 初代素数王の備忘録でした。梅森戦楽しみですね。前もって対戦者が指定されないというのは斬新ですよね。

はじめに

今回は初期手札のお話です。初期手札11枚としてありうるものは何通りあるのか、その中に3の倍数になるものは何通りあるのか、素数を作れるものは何通りあるのかなどについて調べたので書いておこうと思います。

これを調べようと思ったきっかけはTTTTJJJQQQQという組です。この組は3の倍数ではなく、奇数が含まれているのにどう並べ替えても11の倍数となってしまうのです。このことは11の倍数の判定法を考えて、どう並べ替えても各桁の交代和をとると0になることからわかります。めっちゃ強いのに11枚出しできないの面白いですよね。
TTTTJJJQQQQは11の倍数という分かりやすいケースでしたが、もっと意外な組、例えば3枚組の178みたいに素数になりそう感があるけど実は素数にならない組はあるのでしょうか。あるとしたらそれはいったいどんな組なのか、いくつあるのか知りたいですね。
以下178のような「3の倍数でなく、奇数*1が1枚以上含まれている組のうち、どう並べ替えても素数を作ることのできない組」を詰んでるセットと呼びます。

初期手札の詰んでるセットがいくつあるのか調べるなら、初期手札全体における詰んでるセットの個数は多いのか少ないのかも知りたいですね。そうなると初期手札が何通りあって、そのうち何通りが全部偶数なのか、3の倍数なのかを調べる必要が出てきます。
ということで、今回は「初期手札のうち詰んでるセットはどれぐらいあるのか」ということを寄り道しながら調べていこうと思います。

初期手札は何通りあるのか？

まずは初期手札の総数を考えましょう。ひとまずジョーカーのことは抜きにしてA~Kまでのトランプから11枚選ぶ通りの数を求めます。トランプにはA~Kは各々4枚ずつ計52枚あります。素数大富豪なのでスートは当然無視です。このときの初期手札の総数は次のようにして求めることができます。*2

A~Kまでの52枚のトランプから11枚選ぶ通りの数は $(1+x+x^2+x^3+x^4)^{13}$ を展開したときの $x^{11}$ の項の係数と一致します。

どうしていきなり $x$ 出てきたんだ？？って感じですよね。
なんでこんなことが成り立つか超ざっくり説明します。例えばAAAA2223345という手札を考えましょう。Aが4枚、2が3枚、3が2枚、4が1枚、５が1枚、6~Kが0枚という構成で4+3+2+1+1+0+0+0+0+0+0+0+0=11枚の手札ですね。下の赤字のところが、今回の手札に対応する部分です。

$(1+x+x^2+x^3+{\color{red} {x^4}})(1+x+x^2+{\color{red} {x^3}}+x^4)(1+x+{\color{red} {x^2}}+x^3+x^4)(1+{\color{red} {x}}+x^2+x^3+x^4)(1+{\color{red} {x}}+x^2+x^3+x^4)…({\color{red} {1}}+x+x^2+x^3+x^4)$

$x^4*x^3*x^2*x*x*1*1*1*1*1*1*1*1=x^{4+3+2+1+1+0+0+0+0+0+0+0+0}$ となりますね。

こんな感じで、ほかの初期手札もA~Kの枚数を0~4で選んで $(1+x+x^2+x^3+x^4)$ という箱から各トランプの枚数が対応するものを取り出してやれば $x^{11}$ の1つに対応します。
$(1+x+x^2+x^3+x^4)^{13}$ を展開して $x^{11}$ の係数を見れば
AAAA2222333( $x^{4+4+3+0+0+0+0+0+0+0+0+0+0}$ に対応)から
JJJQQQQKKKK( $x^{0+0+0+0+0+0+0+0+0+0+3+4+4}$ に対応)までの手札の総数が出てきます。

詳しくは詳しい人に聞いてください。

というわけで $(1+x+x^2+x^3+x^4)^{13}$ を展開しましょう。
展開すると下のようになります。(これ手作業でできたりするんですかね？)

長いですね。 $x^{11}$ の係数は1111760なので、A~Kからなる52枚のトランプからなる11枚初期手札は1111760通りになります。
$x^{n}$ の係数はトランプからn枚選ぶ通りの数に対応しています。ということは $x^{10}$ の係数は10枚選ぶ通りの数に、 $x^{9}$ の係数は9枚選ぶ通りの数に対応します。よって $x^{11}$ の係数がジョーカー0枚の初期手札の数、 $x^{10}$ の係数がジョーカー1枚の初期手札の数、 $x^{9}$ の係数がジョーカー2枚の初期手札の数となるため、ジョーカー込みの初期手札は1111760 + 566280 + 270270=1948310通りあります。こんなに簡単に求まるの面白いですね。

脱線して、ここら辺の話をちょっとします。

当たり前なのですが、 $x^{n}$ の係数と $x^{52-n}$ の係数が等しいの面白いですね。手札に対して、残りの札が1対1に対応するからですね。
ジョーカー含むものの数だけを直接出したいなら上でやったのと同じように $(1+x+x^2+x^3+x^4)^{13}(1+x+x^2)$ を展開することで求められます*3。色々応用が利きそうですね。
$(1+x+x^2+x^3+x^4)^{13}(1+x+x^2)$ に $x=1$ を代入したら $5^{13}*3$ になります。これはあり得る手札の総数ですね。(ゲーム中あり得るという意味なら手札0枚、54枚はありませんが......)

話を戻します。
とりあえずこれで初期手札の個数がわかりました。
今回ジョーカーを含むものについては最後に考えるので、とりあえずジョーカーを含まない1111760 通りについて見ていくことにします。

3の倍数でないものの個数について

ジョーカーを含まない初期手札1111760 通りのうち和が3の倍数でないものはいくつあるのでしょうか。
だいたい3つに2つなので1111760*2/3通りぐらいですが、きちんと求めておきます。
以下1の3乗根のうち1でないものの一つを ${\omega}$ とします。 ${\omega}^3=1$ 、 ${\omega}^2+{\omega}+1=0$ が成り立ちます。これを使って求めましょう。

$(1+x+x^2+x^3+x^4)^{4}(1+{\omega}x+{\omega}^2x^2+x^3+{\omega}x^4)^{5}(1+{\omega}^2x+{\omega}x^2+x^3+{\omega}^2x^4)^{4}$ を展開したときの $x^{11}$ の項の係数と先ほど求めた総数から求めることができます。
初期手札のうち和が3の倍数となるものの数を $A_0$ 、3で割って1余るものの数を $A_1$ 、3で割って2余るものの数を $A_2$ とすると、 $x^{11}$ の項の係数は $A_0+A_1{\omega}+A_2{\omega}^2$ になります。また先ほどの話から $A_0+A_1+A_2=1111760$ が成り立ちます。

$(1+x+x^2+x^3+x^4)^{4}$ の部分は3の倍数(3,6,9,Q)に対応する部分、
$(1+{\omega}x+{\omega}^2x^2+x^3+{\omega}x^4)^{5}$ の部分は3で割って1余る数(A,4,7,T,K)に対応する部分、
$(1+{\omega}^2x+{\omega}x^2+x^3+{\omega}^2x^4)^{4}$ の部分は3で割って2余る数(2,5,8,J)に対応する部分です。
Aが2枚なら ${\omega}^2x^2$ に、2が2枚なら ${\omega}x^2$ 、6が3枚なら $x^3$ に対応してます。要するに ${\omega}$ の指数部分が3で割ったときの余り、 $x$ の指数部分がそのカードを何枚選んだかになるんですね。

例えば、AAAA2223345という手札を考えましょう。Aが4枚、2が3枚、3が2枚、4が1枚、５が1枚、6~Kが0枚という手札ですね。この手札の和を3で割ったときの余りは1ですね。

この手札は
${\omega}x^4*x^3*x^2*{\omega}x*{\omega}^2x*1*1*1*1*1*1*1*1={\omega}^4x^{11}={\omega}x^{11}$

に対応して確かに ${\omega}x^{11}$ となりますね。こんなことが他の組についても成り立ちます。

まぁ、雑な説明なので詳しく知りたい人は詳しい人に聞いてください。

$(1+x+x^2+x^3+x^4)^{4}(1+{\omega}x+{\omega}^2x^2+x^3+{\omega}x^4)^{5}(1+{\omega}^2x+{\omega}x^2+x^3+{\omega}^2x^4)^{4}$ を展開すると次のようになります。*4

というわけで $A_0+A_1{\omega}+A_2{\omega}^2=20{\omega}^2$ となることがわかりました。
$A_0+A_1+A_2=1111760$ と合わせることで、
$A_0=370580$ 、 $A_1=370580$ 、 $A_2=370600$ と求められます。
よって初期手札のうち3の倍数でないものは $A_1+A_2=370580+370600=741180$ 通りとなります。 $A_2$ が他より20個も多いのはちょっと意外ですね。

初期手札で札が全部偶数のものは何通りあるのか

以下5は偶数とします。札が全部偶数の初期手札とは、4556666TTTQみたいな最悪な手札のことです。見るだけで気持ち悪くなってきますね。
2,4,5,6,8,T,Qから11枚選ぶ方法の数は先ほどと同じ理屈で $(1+x+x^2+x^3+x^4)^{7}$ の $x^{11}$ の項の係数を見ればよいですね。これで手札が全部偶数のものは6055通りであることがわかります。

次に手札全部偶数のもののうち3の倍数でもあるものの個数を求めます。これも先ほどの3の倍数の個数を求めたのと同じようにして求めます。
$(1+x+x^2+x^3+x^4)^{2}(1+{\omega}x+{\omega}^2x^2+x^3+{\omega}x^4)^{2}(1+{\omega}^2x+{\omega}x^2+x^3+{\omega}^2x^4)^{3}$
の $x^{11}$ の項の係数と全部偶数のものが6055通りあることを使えば求まります。

省略しますが、計算することで3の倍数のものが2017通り、3で割って1余るものが2021通り、3で割って2余るものが2017通りとなることがわかります。
これを使うことで3の倍数でない、奇数が1枚以上含まれている初期手札の数が741180-(2021+2017)=737142通りと求められました。

さて、ここまででわかったことをまとめておきます。

手札が全部偶数のものって少ないんだなぁと感じました。ここまで割とあっさり求められるのは面白いですね。

詰んでるセットの個数

さて今回のメインディッシュ、詰んでるセットはいくつあるかに入りましょう。といってもここからは実際に並べ替えて素数ができるかを調べるので力業ですね。パソコン君に頑張ってもらいましょう。
3の倍数でない、奇数が1枚以上含まれている初期手札737142通りをちまちま素数ができるか1個1個調べてもらいます。

C++を用いて調べた結果、詰んでるセットは(間違いがなければ)............................................

2通りになりました！！！！！！！！！！

すっくな！！！！

詰んでるセットはTTTTJJJJQQK、TTTTJJJQQQQだけだそうです。見事に11の倍数のものだけですね。737142通りのうち2通りしかないというのはめっちゃ少ないですね。10枚偶数で1枚だけ奇数という組でも必ず素数が作れるというのは面白いですね。11枚だとこんなことになるんですねぇ。本当にあってるか不安になりますね。

最後にジョーカーが1枚以上ある場合を考えましょう。ジョーカーがあれば3の倍数と手札が全て偶数になることを回避でき、またジョーカーを何にするか適切に選べばTTTTJJJJQQK、TTTTJJJQQQQにしないようにできるので詰んでるセットにはなりえないということになります。3枚出しにおけるQQXみたいなジョーカーがあるのに詰んでるみたいなことはないんですね。ちょっと残念ですね。

おわりに？

詰んでるセットがもっとあると思っていたので、11の倍数であるTTTTJJJJQQK、TTTTJJJQQQQのみという結果は少し残念でした。しかし一方で、3の倍数でなく、奇数が1枚以上ありTTTTJJJJQQK、TTTTJJJQQQQではないとき初手全出しで上がれる可能性があるということは競技素数大富豪プレイヤー的には嬉しいことなのかもしれません。運命力さえあればかなりの場合で勝てる可能性があるからです。理論上、素数を737140個覚えれば初期手札で11枚出しできるときに必ず勝てようになるということですね。

そして実は今回見たTTTTJJJJQQK、TTTTJJJQQQQについては絵札11枚あることから、相手は絵札(ジョーカー含む)を高々7枚しか持っていないので、8枚+3枚で勝つことができますね(具体的にはQTJJTTJJ+QTK、QTTQQTQJ+TJJなど)。ということでこれらは詰んでるセットだけど相手の手札にかからわず、知識が十分あれば勝てる手札ではあるんですね。3の倍数でもこのような勝ち確定手札はあるでしょう。勝ち確定できる初期手札がどれぐらいあるか気になりますよね。

ということで「理論上、先手番で勝ち確定の初期手札は何通りあるのか」という気になる問題が生まれました。
まず今回の話からTTTTJJJJQQK、TTTTJJJQQQQを含め、3の倍数でなく1枚以上奇数がある初期手札は勝ち確定です。また、ジョーカーを含むものも勝ち確定ですね。
問題は主に3の倍数です。まずは合成数ですかね。3の倍数の初期手札のうちどのくらい合成数出しできるのか知りたいです。
3の倍数かつ合成数出しができなくても勝ち確定の初期手札は存在します。例えばKKKQQJ+(3で割って1余る5枚出し素数)のように組めるパターンです*5。KK=K*TA、KKQKJなどについても同じことが言えますがKKJについてはKKQ、KKKで返されないかを考えないといけませんね。大変そうですね。
33555577779*6などのグロタンカカットしたら合成数で上がれるようになるものも忘れちゃいけませんね。それから、ドローのことまで考慮すると結構大変かもしれません*7。

あと、偶数のみでも48828Q5=5^5*5^6という11枚使った合成数は存在します。他にもあったりするんですかね？

ということで、結構面倒そうですが気が向いたら勝ち確定手札について調べていこうと思います。
ここまで読んでいただきありがとうございました！間違っているところあったら是非教えてください。

さて、明日のアドベントカレンダーは翳猫さんで「20枚OVER 超多枚数出しの世界」です。僕は20枚出し以上を殆ど覚えていないので是非参考にしたいです。楽しみです。

*1:5は偶数

*2:こんなことせずに最初からプログラミングで求めろという意見は無視します

*3:

あってると思います。

(1+x+x^2+x^3+x^4)^13*(1+x+x^2)
の11次の係数とも言えますね。
— はち (@82JQ7) 2021年9月11日

*4: $(1+x+x^2+x^3+x^4)^{4}(1+{\omega}x+{\omega}^2x^2+x^3+{\omega}x^4)^{5}(1+{\omega}^2x+{\omega}x^2+x^3+{\omega}^2x^4)^{4}$ を変形すると $(1+{\omega}x+{\omega}^2x^2+x^3+{\omega}x^4)(1+x^3+x^6+x^9+x^{12})^{4}$ になるので、これなら手作業でもできるか？？

*5:相手がドローして手札12枚でもKKKQQJに返す合成数出しは不可能

*6:11枚合成数上りができるかは未確認なのでグロタンカットしないで上がれる可能性あり

*7:存在は未確認ですが11枚では勝ち確定でないがA~Kどれを引いても合成数出しまたは素数出しできるものようになるものがあったら面白いですね