tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

#素数大富豪札幌杯 で出された合成数出しカマトトについて

数学 整数論 日曜数学 素数大富豪

先日、素数大富豪の大会が札幌で開催されました。その名も「札幌杯」。一時期は開催が危ぶまれましたが、なんとか無事開催されることになりました。

少し長い動画ですが、YouTubeで大会の様子を見ることができます。
www.youtube.com

札幌杯では 「数学的に面白いシーン」 がありました。今日はそれを紹介したいと思います。

nishimura vs OTTY

nishimuraさんとOTTYさんの2人の対戦で事件（？）は起きました。お二人とも強豪同士という注目の対戦カードです。対戦も非常に熱かったのですが、今回見ていただきたいのは、動画の 2:12:00 あたりです。

f:id:tsujimotter:20200306011918p:plain:w400

OTTYさんの97843（5枚出し）に対して、nishimuraさんからこんな手が出されました

3^{567224} =_? 88111213

88111213は "88JQK" として出されていますので、5枚出しで問題ありません。しかし なんだこれは という手です。


合成数出しルールのおさらい

素数大富豪は基本的には素数を次々に出していくゲームですが、合成数も出すことができます。

たとえば、 105 = 3\times 5 \times 7 ですが、素因数の 3, 5, 7 をすべて手札から捨てることによって、場に 105 を出すことができます。

また「指数表記」というルールもあります。

65536 = 2^{16}

のような数に対して、手札から素因数の 2 と指数の 16 を捨てることで、 65536 を場に出すことができるようになるというルールです。

いずれのルールに対しても、合成数の計算に誤りがあった場合、ペナルティとして「捨てたカード」と「場に出したカード」の枚数の合計を山札から引かなければなりません。素直に考えると、手札の枚数が増えてしまうので、勝つことが難しくなってしまいます。

そのルールを逆手に取ったのが 「合成数出しカマトト」 という戦法です。素数大富豪においては、もちろん手札の枚数を減らした方がよいのです。一方で、手札に強いカードが少ない場合、あえてカードをたくさん引いて、強い手札を引き込むということが有効な場合もあります。

強いプレーヤー同士の闘いにおいては、この傾向は顕著です。たとえ手札の枚数が少なくても、強いカードを持っていなければあっという間に負けてしまうということもありえます。そこで、合成数出しのペナルティをもらえば、一気にカードの枚数を増やすことができ、チャンスを広げることができるというわけですね。

上のnishimuraさんの戦略でも

3^{567224} = 88111213

などという式はあきらかに成り立ちませんので（左辺があまりに大きすぎる）、ペナルティを狙って合成数出しカマトトを実行したという状況です。


一方で「このような戦法は本当に好ましいのか」という議論は、素数大富豪のプレーヤーの中でなされています。

そこで、せきゅーんさんによって、合成数出しカマトトをある程度制御する追加ルールが提案されています。詳細は以下を見てください。
integers.hatenablog.com

ざっくりいうと、最低限以下の２つは守ってくださいというものです。

  1. 素因数の大きさは、場に出すカードより小さいものにすること
  2. 素因数の積の1桁目は、場に出すカードの1桁目に一致すること

要するに「明らかに間違っているとわけるような合成数出しは避けてね」ということですね。

札幌杯においても、このせきゅーんさんによる追加ルールが採用されています。したがって、nishimuraさんが合成数出しカマトトを行うためには、最低限上の1, 2を守る必要があったというわけです。

ここまでが背景です。


果たして「合成数出しルールは守られているのか？」そして「それはただちに判定できるのか？」というのが今日の本題です。

合成数出しルールは守られているのか？

というわけで、nishimuraさんの一手

3^{567224} =_? 88111213

は、合成数出しカマトトできるのかを考えていきましょう。


まず、合成数出しルール1においては、素因数 3 が 88111213 を下回っているので問題ありません。

問題となるのはルール2ですね。 3^{567224} の1桁目は 3 に一致するでしょうか？

これが 結構厄介な問題 だと思います。というのも、少し計算してみると分かるのですが、 3^n の1桁目は同じ値をとるわけではないからです。

1桁目を考えることは、 \bmod{10} で考えることに相当しますので、 3^n \bmod{10} を計算してみます。

3^1 \equiv 3 \pmod{10}
3^2 \equiv 9 \pmod{10}
3^3 \equiv 7 \pmod{10}
3^4 \equiv 1 \pmod{10}

たしかに、べき乗するごとに次々と値が変わっていきますね・・・。これは困った。

もう少しだけ計算すると、下1桁の傾向が見えてきます。

3^5 \equiv 3 \pmod{10}
3^6 \equiv 9 \pmod{10}
3^7 \equiv 7 \pmod{10}
3^8 \equiv 1 \pmod{10}
3^9 \equiv 3 \pmod{10}
3^{10} \equiv 9 \pmod{10}
3^{11} \equiv 7 \pmod{10}
3^{12} \equiv 1 \pmod{10}

循環していますね。4乗するごとに、元の値に戻ってきているようです。

実際、この背景には合同式における「オイラーの定理」があります。 m と互いに素な整数 a に対して
a^{\varphi(m)} \equiv 1 \pmod{m}

が成り立ちます。ここで、 \varphi(m) は「 m より小さい自然数のうち m と互いに素な数の個数」を表す関数です。 \varphi(10) = 4 より

3^{4} \equiv 1 \pmod{10}

が成り立つということですね。よって、下1桁は4回に一回循環するというわけです。


したがって、 3^n の下1桁が 3 に一致するためには、指数の部分が「4で割って1あまる数」でなければなりません。

では、nishimuraさんのケースではどうでしょう。

567224 = 4 \times 141806 + 0

なので「4で割って0あまる数」です。よって、 3^{567224} の下1桁は 3 に一致しないことがわかります！

というわけで、合成数出しの追加ルールにより、合成数出しカマトトはできないことになりますね。


もちろん、ルールを守らなかったからといって直ちに敗戦というわけではなく、もう一度出し直しということになります。実際、その後すぐにnishimuraさんは

3^{567224} =_? 88131211

を出しています（JとKを交換しました）。この手は

3^{567224} \equiv 1 \pmod{10}

なので、問題なく出すことができますね。

これをnishimuraさんはとっさに出したわけですが、頭の中で上記のような計算をしていたということなんでしょうか。・・・すごい。

それはただちに判定できるのか？

ここで気になってくるのは、本当にこれはすぐに計算できるものなのかという問題です。

特に、素数判定員をする際には、このような手が出されたときに、ただちにルールに抵触しないか判定する必要が出てきます。

実際、当のnishimuraさんからは、合成数出しカマトトの判定が難しいということを逆手にとった、裏ワザめいた戦法がツイートされていたりします。

もちろん、nishimuraさんを含めた素数大富豪プレーヤーは、このようなことはしないかと思いますが。


もしもあなたが素数判定員を務める際に、上記のような状況が起きたとき、どのように対応すればよいでしょうか。指数出しの判定法について、あらかじめ考えてみましょう。

指数出しの下1桁を計算するためには、各素数をべき乗したときの下1桁をただちに計算する必要があります。先ほどは素数 3 について考えました。

実際、下1桁だけを考えればよいので、 1, 2, 3, 5, 7, 9 のべき乗について考えれば十分です。（それ以外の数字は、素数の下1桁にはなりえません。）

下1桁が1のとき

n が 1 以上の整数のとき、次が成り立ちます：

1^{n} \equiv 1 \pmod{10}

下1桁が2のとき

k が 0 以上の整数のとき、次が成り立ちます：

2^{4k+1} \equiv 2 \pmod{10}
2^{4k+2} \equiv 4 \pmod{10}
2^{4k+3} \equiv 8 \pmod{10}
2^{4k+4} \equiv 6 \pmod{10}

下1桁が3のとき

k が 0 以上の整数のとき、次が成り立ちます：

3^{4k+1} \equiv 3 \pmod{10}
3^{4k+2} \equiv 9 \pmod{10}
3^{4k+3} \equiv 7 \pmod{10}
3^{4k+4} \equiv 1 \pmod{10}

下1桁が5のとき

n が 1 以上の整数のとき、次が成り立ちます：

5^{n} \equiv 5 \pmod{10}

下1桁が7のとき

k が 0 以上の整数のとき、次が成り立ちます：

7^{4k+1} \equiv 7 \pmod{10}
7^{4k+2} \equiv 9 \pmod{10}
7^{4k+3} \equiv 3 \pmod{10}
7^{4k+4} \equiv 1 \pmod{10}

下1桁が9のとき

k が 0 以上の整数のとき、次が成り立ちます：

9^{2k+1} \equiv 9 \pmod{10}
9^{2k+2} \equiv 1 \pmod{10}


というわけで、 1, 5 のときには覚える必要はないですし、 2, 3, 7, 9 についても上記のリストを覚えておけば、あとは「指数部分を4で割ったあまり」さえ計算できれば、直ちに判定できますね。
（・・・できるかな？）

覚えていなくても、最初の4乗だけ計算できれば、表はすぐに復元できますね。
（・・・できるかな？？）


というわけで、実際の素数大富豪の試合で起きた状況が、整数論的に面白かったということで紹介されていただきました。今回もそうでしたが、素数大富豪も進化し続けていますので、また面白い戦略やルールが生まれてくるかもしれませんね。楽しみです。

それでは今日はこの辺で。

関連記事

今回の状況に非常によく似た計算を解説している記事です。この記事を書いた当時は、まさか素数大富豪でこのような考え方が使えるとは思いもしませんでした。
tsujimotter.hatenablog.com