今回は、実際に問題を変形して、学会で発表した例を紹介します。私は高校生ですが、問題変形をすることで論文レベルの発見ができます。このブログは高校生が書いているので、高校生以上であれば理解できると思います。
そもそも…
Multiplyting to 1000(21game)というよく知られた数学的パズルがあります。このパズルの変種を作り、必勝手についての研究を行いました。当ブログの前半部はあまり数学的な理論を使わずに書きます。
タイトル＆きっかけ
Multiplying to 1000 とその変形
Multiplying to 1000 and its Variant Problem
良く知られた “Multiplying to 1000” という問題を変形して新しい問題を考え，それを解析しました。 私達が調べた限りでは，今回行ったような，使うこと ができる数字を減らした研究はありませんでしたたが，難しい問題ではないので，どこかで行われている可能性はあります.ただし，私達のように数学ソフト Mathematica を使うと，設定を変えながら後手必勝の条件を調べる ことができます.高校生や大学生によるミニ研究の方法 としては有効であると考えて，発表することにしました。 (論文一部引用)
これから、この研究の流れについて説明します。
ルール説明
自然数の集合 T1 = {2,3,4,5,6,7,8,9} を 固定する。ゲーム開始時にある自然数が与えられる. A が T1 のうちから数を 1 つ選んで，その自然数に掛 ける.そして得られた自然数に B が T1 のうちから 数を 1 つ選んで，掛ける.次は A の番で，このよう に A, B が交互に T1 のうちから数を 1 つ選んで掛け ていき，先に 1000 を超えた方が勝つ.
すごくややこしい言い方ですので、要約すると、
手順
⒈ゲーム開始時にある自然数が与えられる
2.プレイヤーAが2,3,4,5,6,7,8,9のうちから数を1つ選んでその自然数に掛ける．
3.得られた自然数にプレイヤーB が2,3,4,5,6,7,8,9のうちから数を1 つ選んで掛ける
この操作を繰り返して自分の番で、数字を1000以上にすると勝者になる。
Mathematicaのコード
これをMathematicaのコードにしました。P-positionは後手必勝の時の値です。（コードの解説は長くなるので割愛 P-positionの説明はブログ後半へ）
in[]:=
ss = 1000; allcases = Table[a, {a, 1, ss}];
move[z_] := Block[{p = z}, If[p <= 1000, Table[p*k, {k, 2, 9}], {}]];
Mex[L_] := Min[Complement[Range[0, Length[L]], L]];
Gr2[pos_] := Gr2[pos] = Mex[Map[Gr2, move[pos]]];
pposition = Select[allcases, Gr2[#] == 0 &]
0ut[]:=
{4,5,6,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72, 73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91, 92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107, 108,109,110,111}
変種の作り方
元問題
ある自然数に対して2人のプレイヤーが2,3,4,5,6,7,8,9から数字を選び,前の数にその数を掛けていく
変種作り方（変形）
上記の問題を変形しやすい部分に分けてみる（例）青い点々の線に注目！！
ある自然数に対して2人のプレイヤーが
から数字を選び,前の数にその数を掛けていく（元問題）
掛けることのできる数のうち
2,3,4,5,6,7,8,9
赤の数字のどれか一つを省くことで変種を作る
よって、変種は
変種
ある自然数に対して2人のプレイヤーが
2,3, ,5,6,7,8,9から数字を選び,前の数にその数を掛けていく
詳しく書くとすると
a を2から9 までの自然数のどれかとして，a を固定する．T2 = T1−{a} とする．定義1 のゲームにおいて，T1 の代わりにT2 を使う．
自然数の集合 T2を 固定する。ゲーム開始時にある自然数が与えられる. A が T2のうちから数を 1 つ選んで，その自然数に掛 ける.そして得られた自然数に B が T2 のうちから 数を 1 つ選んで，掛ける.次は A の番で，このよう に A, B が交互に T2 のうちから数を 1 つ選んで掛け ていき，先に 1000 を超えた方が勝つ.
要するにT1の数を一つずつ減らしてみたということである。
Mathematicaのコード
Mathematicaのコードはこうなります。変形ですので、数字を変えるだけで変形できます。
ss = 1000; allcases = Table[a, {a, 1, ss}]; use = {3, 4, 5, 6, 7, 8, 9};
move[z_] := Block[{p = z},
If[p <= 1000, Table[p*use[[k]], {k, 1, Length[use]}], {}]];
Mex[L_] := Min[Complement[Range[0, Length[L]], L]];
Gr2[pos_] := Gr2[pos] = Mex[Map[Gr2, move[pos]]];
pposition = Select[allcases, Gr2[#] == 0 &]
0ut[]:=
{4,5,6,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72, 73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91, 92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107, 108,109,110,111}
useの中の数字を変えるという変形です。
結果として、aが2か9の時以外はP-position（後手必勝）は同じになることがわかります。
定理1
使うことができる数字2,3,4,5,6,7,8,9のうちで、
3から8までの数から１つを決めて省いても、先手必勝の場合と後手必勝の場合は元の問題と変わらない
この問題のように数字を減らしたりするだけでも問題の変形になり、おもしろい結果が出ると論文にも書けます。
定理１の注意
使うことができる数字2,3,4,5,6,7,8,9のうちで、3から8までの数から2つを決めて省くと、先手必勝の場合と後手必勝の場合は元の問題と違ったものになる。
「定理１の注意」から言えること
ならば…
使う数字の中から、2つ以上取り去っても先手必勝の場合と後手必勝の場合が変化しない問題を作ってみた。
定理２
使うことができる数字が３,4,5,6,7,8,９のとき４,５,６,７,８を全て省いて、3と9のみを使うことにしても先手必勝と後手必勝の場合は変わらない
数学的理論
これまでの話で、私たちが行った研究はほぼ説明できているのですが、これから数学的な理論を使って今回の研究を説明します。
N-PositionsとP-Positionsとは
先ほど、少し登場しましたが、２つの言葉には以下の意味があります。
N-Positions 次のプレイヤーが勝てるポジション ＝先手必勝
P-Positions 次のプレイヤーが負けるポジション ＝後手必勝
先行研究によると
先手必勝のN-PositionsはN1 $ N_1 \cup N_2 \cup N_3 $となります。
N1 ={1,2,3}
N2 ={7,8,9,…,55}
N3 ={112,113,114,…,999}
後手必勝(先手必負)のP-Positionsは $ P_1 \cup P_2 $ となります。
P1={4,5,6}
P2={56,57,58,…111}
研究結果
定理１
仮に {2,3,4,5,6,7,8,9}の中から1つ数字を抜いて残った数字で掛ける。そのとき、N-positions とP-positions は元のゲームと同じになる。
定理２
1.プレイヤーが {3,4,5,6,7,8,9} を掛けるとき
2.プレイヤーが{3,9} を掛けるとき
上記の2つの場合のN-positionsとP-positions は同じになる。
Grundy数の紹介
Grundy数 G(n)を各数に対して定義していく。
n≥1000に対してG(n)=0
ん？Grundy数ってなんだぁ？？？
Grundy数とは
各nに対しては、行き先にない最小の負でない整数をG(n)とする。
(….ん？ますますわからん….)
Grundy数を定義してみよう
（ついていけなければ、質問してくださいね）
１.P-position(s)（=行き先）を0と定義します。
そのため、四角の中に0と記入します。
2.では以下の緑色の部分に入る数字はなんでしょう？
ヒント:Grundy数は行き先にない最小の負でない整数でしたよね。
28~55のは、２倍すると56~111になりますよね。
28×2=56 55×2=110
この場合、「56~111」が行き先です。Grundy数は行き先にない最小の負でない整数です。ですので、行き先の四角（マス）には「０」と書きましたよね。行き先に０があるので、「行き先にない最小の負でない整数」は1になります。
＜負でない整数＞
0,1,2,3….
0は行き先にあるので、行き先にない最小の負でない整数は1です。
3.では下の緑に入るのは？
14~27は2倍すると28~55になりますね。3.4倍以上すると56~111にもなります
14×2=28
27×3=81
＜負でない整数＞
0,1,2,3….
行き先に0と１があります。
よって、行き先にない最小の負でない整数は2です。
４.では最後に下の緑に入るのは？
解説は省略しますが、3になりますよね。
まとめると、
こうなりますね。
再度ですが、
定理
Grundy数が0であることは、P-positionであるための必要十分条件
先手必勝のNポジションからPポジションへの行き方
Multiplying to 1000の場合2,3,4,5,6,7,8,9を全て使うとこうなります。
Multiplying to 1000の変形の場合3,4,5,6,7,8,9を使うと、
最後に 〜研究に使用したソフト〜
Wolfram Mathematica
設定を変えながら後手必勝の条件を調べることができる
本研究の教育的意義
問題を与えられて、それを変形し計算機(Mathematica)で先手、後手必勝の場合を探し、それを証明するということ。
出典
ここまで読んでいただき、ありがとうございました。
寺本 雅治, 坂本 悠輔, 種村 圭依人, 宮寺 良平, 福井 昌則, Multiplying to 1000 とその変形, ゲーム学会第17回合同研究会, 2019, 香川.
コメント