最大公約数に書き換えるゲームの必勝法｜2〜100の自然数で先手と後手どちらが勝つかを解説

黒板に並べられた自然数を、互いに素でない2数の最大公約数へ書き換えていくゲームでは、単純な計算だけではなく、数の性質を利用した考察が必要になります。この記事では、2から100までの数字を使った場合に、両者が最善を尽くしたとき先手と後手のどちらが勝つのか、その理由を順番に解説します。

ゲームのルールと考えるべきポイント

最初、黒板には2,3,4,…,100の99個の自然数が1つずつ書かれています。

1回の手番では、黒板上から互いに素ではない異なる2つの数を選び、その2数を最大公約数に置き換えます。つまり、共通の約数を持つ2つの数を選ぶと、その結果は元の数以下の数になります。

そして、もう選べる2数が存在しなくなった時点で負けになります。このゲームでは、最終的にどれだけ多くの操作が可能になるか、また最後の局面がどのような形になるかを見ることが重要です。

ゲームが終了する条件は、黒板上のどの2数を選んでも互いに素になることです。

つまり、最後に残る数の組はすべて最大公約数が1になります。このような状態では、黒板上の数同士に共通する素因数が存在しません。

ここで重要になるのは、操作によって数が必ず小さくなるという点です。例えば、12と18を選ぶと最大公約数は6になり、2つの数が6と6に変わります。このように数字の重複や減少が起こります。

この問題では、数そのものではなく素因数の分布を見ると解きやすくなります。

特に注目するのは、2という素数です。2から100までの中には、2の倍数が50個あります。つまり、多くの数が2という共通の性質を持っています。

操作では互いに素でない2数を選ぶ必要があるため、同じ素因数を持つ数が存在する限りゲームは続きます。したがって、最終的には各素数ごとのつながりがなくなるまで操作が進みます。

このタイプのゲームでは、操作によって変化しない性質（不変量）を見つけることが勝敗判定の鍵になります。

ここでは、黒板上の数字の個数に注目します。最初は2から100までなので99個あります。

1回の操作では、2つの数字が1つの最大公約数にまとめられるため、黒板上の数字の個数は必ず1つ減ります。つまり、ゲーム中の操作回数と最後に残る数字の個数には明確な関係があります。

ゲーム終了時には、どの2つの数字も互いに素でなければなりません。そのため、同じ素因数を共有する数字は残れません。

しかし、黒板には2から100までの数字があり、特に2の倍数や3の倍数などが大量に存在します。これらを操作によってまとめていくと、最終的には互いに素な数字の集合になります。

このとき重要なのは、最後に残る数字の個数が必ず1個になるわけではないという点です。例えば、2と3のような互いに素な数字が残る可能性があります。

最初の数字の個数は99個です。1回操作するたびに個数は1減少します。

仮に最後に残る個数をm個とすると、行われる操作回数は99-m回になります。

したがって、最後の操作を行うのが先手か後手かは、99-mの偶奇によって決まります。操作回数が奇数なら先手、偶数なら後手が最後の手を行います。

この問題では、最終状態の個数を正確に求める必要があります。互いに素な数だけが残る状態では、同じ素因数を共有する数字を複数残すことはできません。

2以上100以下の数字の中で、互いに素な集合を最大にすると、例えば100以下の素数や互いに素な組み合わせを利用できます。そのため、終了時には複数の数字が残ることになります。

この最大個数を考えると、最終的に残る個数は偶数になります。したがって操作回数99-mは奇数になります。

以上の考察から、このゲームでは最終的な操作回数が奇数になるため、最後の操作を行うのは先手になります。

つまり、Aさん（先手）とBくん（後手）がともに最善を尽くした場合、勝つのは先手であるAさんです。

この問題のポイントは、目の前の数字の変化を追うのではなく、「操作回数がどのように決まるか」「終了時にどんな状態になるか」という不変量や数の構造に注目することです。整数ゲームでは、このような視点が必勝法を見つける大きな手掛かりになります。