平方を引く

引き算ゲーム（テイク・ア・スクエアとも呼ばれる）は、2人用の数学的な引き算ゲームである。2人でコイン（または他のトークン）の山を挟んでプレイする。プレイヤーは順番に山からコインを取り除き、常に0以外の平方数のコインを取り除く。このゲームは通常、通常のプレイゲームとしてプレイされ、最後のコインを取り除いたプレイヤーが勝ちとなる。^{[1] [2]これは}公平なゲームであり、どの位置からでも実行できる動きのセットは、誰の番であるかに依存しない。ソロモン・W・ゴロムは、このゲームの発明者をリチャード・A・エプスタインであるとしている。^[3]

13 枚のコインで始まる通常のプレイ ゲームでは、最初のプレイヤーが 1 枚減算して開始した場合、最初のプレイヤーが勝ちます。

プレイヤー1: 13 - 1*1 = 12

プレイヤー 2 には、1、4、9 を引くという 3 つの選択肢があります。これらのいずれの場合も、プレイヤー 1 は、数回の移動で数字 2 がプレイヤー 2 に渡されるようにすることができます。

プレイヤー2: 12 - 1*1 = 11 プレイヤー2: 12 - 2*2 = 8 プレイヤー2: 12 - 3*3 = 3
プレイヤー1: 11 - 3*3 = 2 プレイヤー1: 8 - 1*1 = 7 プレイヤー1: 3 - 1*1 = 2
                               プレイヤー2: 7 - 1*1 = 6 または: 7 - 2*2 = 3   
                               プレイヤー1: 6 - 2*2 = 2 3 - 1*1 = 2

次に、プレイヤー 2 は 1 を引く必要があり、続いてプレイヤー 1 も同じことを行います。

プレイヤー2: 2 - 1*1 = 1
プレイヤー1: 1 - 1*1 = 0
  プレイヤー2が負ける

上記の例では、数字「13」は勝ちまたは「ホット」な位置を表し、数字「2」は負けまたは「コールド」な位置を表します。各整数に「ホット」または「コールド」というラベルが付けられた整数リストが与えられている場合、ゲームの戦略は単純です。つまり、「コールド」な数字を相手に渡すようにすることです。これは、「ホット」な数字が提示されている限り常に可能です。どの数字が「ホット」で、どの数字が「コールド」であるかは、再帰的に決定できます。

1. 数字の0は「冷たい」、1は「熱い」です
2. 1からNまでの数字が「ホット」か「コールド」に分類された場合、
   • 正の二乗を引いた数だけ「ホット」な数に到達できる場合、数N+1は「コールド」である。
   • 数N+1は、正の平方を引いて少なくとも1つの「コールド」数に到達できる場合に「ホット」である。

このアルゴリズムを使用すると、コールド番号のリストが簡単に得られます。

0、2、5、7、10、12、15、17、20、22、34、39、44、…（OEISの配列A030193）

より高速な分割統治アルゴリズムは、任意の閾値までの同じ数列を時間 で計算することができる。^[4]${\displaystyle n}$${\displaystyle O(n\log^{2}n)}$

コールドナンバーは無限にあります。もっと強い言い方をすると、ある閾値までのコールドナンバーの数は少なくとも の平方根に比例しなければなりません。そうでなければ、すべてのホットナンバーから勝ちの動きを提供するのに十分な数のコールドナンバーがないからです。^[3] コールドナンバーは、0、2、4、5、7、または9で終わる傾向があります。他の数字で終わるコールド値は非常にまれです。^[3]これは特に、6で終わるコールドナンバーに当てはまります。4000万未満の180,000を超えるコールドナンバーのうち、6で終わるのは11,356だけです。^[5]${\displaystyle n}$${\displaystyle n}$

2 つのコールド数に 1 平方の差があるはずはありません。もし 1 平方の差があると、2 つのうち大きい方から小さい方への移動が勝利となり、両方がコールドであるという仮定に矛盾するからです。したがって、フュ ルステンベルク-サルコジ定理により、コールド数の自然密度はゼロです。つまり、すべてのおよび十分に大きい に対して、 までの数のコールド数の割合は未満です。さらに強く、すべての に対して、${\displaystyle \epsilon >0}$${\displaystyle n}$${\displaystyle n}$${\displaystyle \epsilon }$${\displaystyle n}$

${\displaystyle O(n/(\log n)^{{\frac {1}{4}}\log \log \log \log n})}$

コールド数は までです。^[6]コールド数の正確な増加率は不明ですが、実験的には任意の閾値までのコールドポジションの数はおよそ であるように見えます。^[4]${\displaystyle n}$${\displaystyle n}$${\displaystyle n^{0.7}}$

減算ゲームは、複数の数字を使ってプレイすることもできます。各ターンで、手番のプレイヤーはまず数字の 1 つを選択し、それからその数字から 1 マス減算します。このような「通常のゲームの合計」は、Sprague-Grundy 定理を使用して分析できます。この定理は、減算ゲームの各位置が、同等のnim ヒープ サイズにマッピングされる可能性があることを示しています。最適なプレイは、可能であれば、同等の nim ヒープ サイズのnim 合計が 0 になるような数字のコレクションに移動することです。位置の同等の nim ヒープ サイズは、1 回の移動で到達できる位置の同等のサイズの最小除外値として計算できます。減算位置の値が 0、1、2、... の場合、同等の nim ヒープ サイズは次のようになります。

0、1、0、1、2、0、1、0、1、2、0、1、0、1、2、0、1、0、1、2、0、1、0、1、2、0、1、0、1、2、3、2、3、4、…（OEIS のシーケンスA014586 ）。

特に、subtract-a-square の位置は、それと同等の nim ヒープ サイズが 0 の場合にのみコールドになります。

このゲームのバリエーションとして、正方形以外の動きを使って遊ぶこともできます。例えば、ゴロムはモーザー・ド・ブリュイン数列に基づいた類似のゲームを定義しました。これは正方形と同様の漸近速度で増加する数列で、コールドポジションのセットをより簡単に決定し、簡単に計算できる最適な動きの戦略を定義することができます。^[3]

勝利条件を変えずに、プレイヤーに追加の目標を追加することもできます。たとえば、勝者には勝利までに要した手数に基づいて「スコア」を与え（目標は可能な限り低いスコアを得ること）、敗者には勝者が勝利するまでにできるだけ長い時間をかけるようにする目標を与えることができます。この追加の目標ペアと、両方のプレイヤーが最適なプレイをしているという仮定により、開始位置 0、1、2、... のスコアは次のようになります。

0、1、2、3、1、2、3、4、5、1、4、3、6、7、3、4、1、8、3、5、6、3、8、5、5、1、5、3、7、…（OEIS のシーケンスA338027 ）。

引き算ゲームは、最後に引き算をしたプレイヤーが負けるミゼールゲームとしてもプレイできます。ミゼール ゲームの「ホット」な数字と「コールド」な数字を決定する再帰アルゴリズムは、通常のゲームと同じですが、ミゼール ゲームでは数字 1 が「コールド」で、2 が「ホット」である点が異なります。したがって、ミゼール バリアントのコールドな数字は、通常のゲームのコールドな数字を 1 シフトしたものになります。

ミゼールは「冷たい」数字を演奏する：
1、3、6、8、11、13、16、18、21、23、35、40、45、...

• ニム
• ウィトフのゲーム