インテジャーズ

INTEGERS

数、特に整数に関する記事。

合成数出しにおけるルール変更案

この記事は素数大富豪 Advent Calendar 2019 - Adventarの14日目の記事です。
13日目の記事は岩淵夕希(物智)さんのペアが重要!素数大富豪の新戦略「魔神出し」 | 岩淵夕希(物智)公式ブログです。

もりしーさんの先日の記事素数大富豪研究会2019 - 素数交響曲第2番と内容の重複があります。

PrimeQK

12月7日に開催された第二回素数大富豪研究会に参加してきました。その打ち上げにおいて、素数大富豪の英語名の正式名称を決めて欲しいと言われました。

これまでにも幾つかの案は考えていたのですが、正式名称としては決まっていませんでした。色々な観点を考慮して、最終的にPrimeQKに決定致しましたことをここに再度報告致します。

そのうち、私自身で英語版公式ルールを書くことができればよいのですが、いつになったら時間が取れるかは今の段階ではわかりません。

カマトト

素数大富豪では手札からカードの組を作り、場に出すことがプレイヤーの基本的な行動となります。

このとき、手札から作ったカードの組は「場に出せる組」と「出せない組」に分かれます。

更に、場に出せた組に対して、「ペナルティを受けない組」と「ペナルティを受ける組」に分かれます。

素数大富豪ではルール上「わざとペナルティを受ける組を場に出す行為」を禁止していません。ペナルティを受けるからといって悪い行為・禁止された行為というわけではないのです。素数大富豪プレイヤーらによって、このような行為は「カマトト」と呼ばれるようになりました。

素数大富豪においては、手札を減らすことが最終目標でありながら、可能な組合せを増やすために手札を増やすことが戦略上有効になり得るというパラドキシカルな側面があります。

そのため、カマトトは実際にプレイヤーによって多用され、素数大富豪におけるありふれた行為となっています。

一方で、本来の素数大富豪の勝利目標からすると、わざと手札を増やす行為は無気力試合のようにも見えなくもないため、禁止すべきであるという考え方もあり得ます。

しかしながら、上述の通り実は無気力というわけではなく戦略を練った行為として用いられることがあることや、「わざと間違えた」ということを判断することが難しい(不可能)ということからカマトト行為は公式ルールにおいては禁止されていません。

合成数出しカマトト

カマトトは合成数出しを考慮に入れない場合はさほど問題になりません。

というのも、ペナルティを受けるためには「場に出せる組」という条件を満たしている必要があるからです。

その条件は、直近で場に出ているカードの組をA、出そうとしているカードの組をBとするとき、AとBのカードの枚数が同じであることと、Bの数値がAの数値より大きいことです*1

この条件により、とりあえず先攻初手全出しだけは裏技的ではあるものの、無条件にいつでも手札を二倍に!という感じにはなりません。


ところが、合成数出しを考慮に入れると話が変わってきます。

「素因数場に出せるカードの組」は「場に出せるカードの組」と比較して条件がかなり弱いため、素因数分解をデタラメにすることによって、大抵の場合「手札の全出し」が出来てしまいます。

これを使って手札を倍増させる裏技的手法は「合成数出しカマトト」と通称されています。

第二回素数大富豪研究会の研究テーマにも上がりましたが、合成数出しカマトトによる手札倍増裏技は現在の上位プレイヤーにとって実際にかなり強力な手法であることが分かりつつあり、実戦でも多用されているようです。

通常のカマトトと違い、合成数カマトトによっていつでも手札を倍増できるというのはチート的でゲームの欠陥とも言えますし、抵抗を示すプレイヤーもいます。

素因数分解が見るからにデタラメなので、証明は出来ないにせよ、明らかに「わざと」間違えています。ルール上問題ないといえばそれまでですが、やはり「わざと間違える」という行為が嫌な人もいるでしょう。

他にも手札が増えるとゲーム時間が延びることが多々あり、大会の進行上好ましくないという観点もあります。

合成数出しにおける一つのレギュレーション

このように合成数出しカマトトの是非をめぐって素数大富豪プレイヤーの中でも活発に議論されたり意見が割れたりしている現状です。

うまく合成数出しカマトト問題を緩和するようにルールを変更できれば解決に近づくかもしれません。

そのようなルール変更案を一つ提示するのが本記事の主目的です。

「素因数場に出せるカードの組」に課せられる条件が弱すぎることが問題なのでした。いくらか前、特に考えることなしにパッと思いついたのが「場に出した数より大きい数を構成するカードの組を素因数場に出すことを禁じる」だったのですが、二世さんに「それだと場に出した数より小さくなるように組を分割して簡単に全部出せるため問題解消になっていない」と指摘されました。

そこで、別の条件を提示します。

素因数場に出せるカードの組に課せられる新条件
素因数分解公式が少なくとも10を法とした合同式としては成立していなくてはならない。

例えば、不成立である式「10=2\times 3」でカードを出そうとしても「0 \not \equiv 6\pmod{10}」なので認められない一方で、不成立である式「10=32\times 534235」は10を法とした合同式としては成立していることが右辺の一桁目だけを掛け算すれば容易に確認でき、このような合計9枚出しは可能ということです。

人は素数判定は容易には出来ません。それが素数大富豪のゲーム性を生みだしており、素数判定は機械に任せるのでした。

一方で、枚数チェックや大小比較は素数判定に比べれば簡単にできます。少なくとも素数判定員にはそれが瞬時に出来ることを必須スキルと課すことによって「場に出せる組の条件」というルールが機能していました。

このように素数判定とは別の比較的簡単に判定できる条件を最低条件として設けることによって過剰なカマトトがあらかじめ制限されていました。

「素因数場に出せるカードの組」には同様の「丁度良い最低条件」が設けられていなかったわけですが、上記提案の「10を法とした合同式として成立していること」という条件は素因数分解の式が成立することを確認することと比較すると、やはり格段に簡単な作業となります(\bmod計算は掛け算の都度、一桁に還元可能)。「簡単にチェックできるし、最低限それは満たしてね」ということです。

合成数カマトトを試みるプライヤーは限られた考慮時間の間に「場に出せる組の条件」と「素因数場に出せるカードの組の条件」のチェックの作業をしなければならないため、今までほどは裏技的な手札倍増が頻繁には出来なくなるのではないかと期待しています。素数判定員のチェックにより条件が満たされていなければペナルティは受けられません。

うーん。それにしても、自分で書いてて「10=32\times 534235」はひどい。昔の案と合わせるのはどうだろうか。つまり、

素因数場に出せるカードの組に課せられる新条件(改)
素因数として出す各組の数値は場に出すカードの組の数値より小さく、素因数分解公式が少なくとも10を法とした合同式としては成立していなくてはならない。

組を分割すればその分だけ暗算すべき掛け算が増えますし、これだったらよいかもしれません。とは言っても、テストプレイしてみないとわからないので今回は提案にとどめます*2


合成数カマトトに関する皆さんの考えも是非お聞かせください。

素数大富豪アドベントカレンダー明日の記事は二世さんの「もっと素数大富豪がしたい人へ」です。

*1:ラマヌジャン革命はここでは考慮に入れないことにします。

*2:これからの素数判定員は「3の100乗を19で割ったあまりは?」を4通りの方法で計算する - tsujimotterのノートブックを読んでおく必要があるかもしれませんぞ。

調和級数と優収束定理

f_n\colon\mathbb{R}\to\mathbb{R}f_n:=\frac{1}{n}\mathbf{1}_{[0,n)}で定義する. ここで, \mathbf{1}_Aは集合Aの指示関数を表す. (f_n)_{n\in\mathbb{Z}_{>0}}は定数関数0に各点収束する.

調和級数\displaystyle \sum_{n=1}^{\infty}\frac{1}{n}が有限値 H に収束したと仮定する.

関数 g\colon\mathbb{R}\to\mathbb{R}\displaystyle g(x):=\sum_{n=1}^{\infty}\frac{1}{n}\mathbf{1}_{[n-1,n)}(x)で定義すると, 任意の正整数nと実数xに対して|f_n(x)|\leq g(x)が成り立っており, 更に g(x)は可積分関数である: \displaystyle \int_{\mathbb{R}}g(x)\mathrm{d}x=H.

よって, Lebesgueの優収束定理によって

\displaystyle \int_{\mathbb{R}}\lim_{n\to\infty}f_n(x)\mathrm{d}x=\int_{\mathbb{R}}0 \ \mathrm{d}x=0

\displaystyle \lim_{n\to\infty}\int_{\mathbb{R}}f_n(x)\mathrm{d}x=\lim_{n\to\infty}\frac{1}{n}\times n=1

は等しい.

クラトフスキの閉包・補集合定理

定理 (Kuratowski, 1922) (X,\mathcal{O})を位相空間とする。このとき、Xの部分集合Aに対して閉包および補集合を取る操作を繰り返しても高々14個の集合しか得られない。また、実際に相異なる14個の集合が得られる例がある。

この定理の証明を解説します。

Kuratowskiモノイド

位相空間(X,\mathcal{O})に対する閉包、補集合を取る写像 2^X\to 2^Xをそれぞれ b, cと表す*1。また、\mathrm{id}\colon 2^X\to 2^Xは恒等写像とする。合成を積、\mathrm{id}を単位元とし、b,cが生成するモノイドをK(X,\mathcal{O})と表すことにする。

b^2=b, c^2=\mathrm{id}である。

f,g \in K(X,\mathcal{O})に対して大小関係 f\leq gを、任意のA\subset Xに対して f(A)\subset g(A)が成り立つことと定める。f\leq gかつ f\geq gであれば f=gである。

bは包含順序を保つので (A\subset B\subset X \Longrightarrow b(A)\subset b(B))、g_1\leq g_2であれば bg_1\leq bg_2が成り立つ。

cは包含順序を逆転させるので (A\subset B\subset X \Longrightarrow c(A)\supset c(B))、g_1\leq g_2であれば cg_1\geq cg_2が成り立つ。

内部を取る写像をiとすると、i=cbcである。任意の f\in K(X,\mathcal{O})に対して if\leq fである。

補題 bcbcbcb=bcbである。

証明. cbcbcb=ibcbなので、

cbcbcb \leq bcb.

よって、bの性質より

bcbcbcb\leq bbcb=bcb \tag{1}

が成り立つ。cbcb=ib\leq bなので、bの性質より

bcbcb\leq bb=b.

cの性質より、

cbcbcb\geq cb.

よって、bの性質より

bcbcbcb\geq bcb \tag{2}

が成り立つ。(1)(2)よりbcbcbcb=bcbが示された。 Q.E.D.

高々14個であることの証明。

命題 K(X,\mathcal{O})=\{\mathrm{id},b,c,bc,cb,bcb, cbc,bcbc,cbcb,bcbcb,cbcbc,bcbcbc,cbcbcb,cbcbcbc\} である。

証明. b^2=b, c^2=\mathrm{id}という性質からK(X,\mathcal{O})\mathrm{id}以外の任意の元はbcを交互に繰り返す文字列に還元される。bcbcbcbおよび8文字以上を使うこのような文字列は補題によって必ず長さを短く還元できるので証明が完了する。 Q.E.D.

14個得られる実例

X=\mathbb{R}として通常の位相を考える。

A:=(0,1)\cup (1,2)\cup \{3\} \cup ([4,5]\cap\mathbb{Q})

とせよ。

\begin{align}
A&=(0,1)\cup (1,2)\cup \{3\} \cup ([4,5]\cap\mathbb{Q})\\
b(A)&=[0,2]\cup\{3\}\cup[4,5]\\
c(A)&=(-\infty,0]\cup\{1\}\cup[2,3)\cup(3,4)\cup([4,5]\setminus\mathbb{Q})\cup (5,\infty)\\
bc(A)&=(-\infty,0]\cup\{1\}\cup[2,\infty)\\
cb(A)&=(-\infty,0)\cup(2,3)\cup(3,4)\cup(5,\infty)\\
bcb(A)&=(-\infty,0]\cup[2,4]\cup[5,\infty)\\
cbc(A)&=(0,1)\cup(1,2)\\
bcbc(A)&=[0,2]\\
cbcb(A)&=(0,2)\cup(4,5)\\
bcbcb(A)&=[0,2]\cup[4,5]\\
cbcbc(A)&=(-\infty,0)\cup(2,\infty)\\
bcbcbc(A)&=(-\infty,0]\cup[2,\infty)\\
cbcbcb(A)&=(-\infty,0)\cup(2,4)\cup(5,\infty)\\
cbcbcbc(A)&=(0,2)
\end{align}

の14個は全て相異なっている。

*1:閉包(closure)、補集合(complement)ともに頭文字はcであるが、閉包の方はよく\overline{A}で表すので、barのbを採用した。