・倍数作りゲーム                       DD++ 氏

 100個の枠が左右一列に並んでいて、最初は全て空欄である。まず先手が好きな空欄を
1つ選び、0から9までのいずれかの数字を書き込む。次に後手が好きな空欄を1つ選び、0
から9までのいずれかの数字を書き込む。次に先手が・・・と、空欄が尽きるまで交互に数字
を書き込んでいく。

 後手が最後の空欄を埋めた時、この枠全体を100桁の十進法の整数と考えて、これが11
の倍数になっていれば後手の勝ち、それを防ぐことができれば先手の勝ちとする。

(1)  一番左の枠に0があるときは桁数が100より少ない整数とみなすルールの場合、先手
  必勝か後手必勝か。また、必勝である側の戦略はどのようなものか。

(2)  一番左の枠に0を書き込むのは禁じ手とするルールの場合、先手必勝か後手必勝か。
  また、必勝である側の戦略はどのようなものか。

(3)  後手の勝利条件を11の倍数ではなく13の倍数とした場合、(1)(2)それぞれのルールで
  どのようになるか。

(参考) 倍数の判定 特に、11の倍数の判定 、13の倍数の判定


 GAI さんからのコメントです。(平成30年4月1日付け)

 とりあえず、(2) mod 11 の場合での考察。

 先手が圧倒的に有利だが、絶対とはいかない。最後残り2か所に入れる数を x、y とする。

 ここで、11の倍数になる2組を見つけて位の大きい方をx成分、小さい方をy成分とする。

 見つけたその2組を(x1,y1)、(x2,y2)とし、 x1+y1=x2+y2=s (mod 11) なら先手は位の大き
い方へ、s+1の値を入れる。
(すると後手は最後に0〜9のいずれを入れても全体を11の倍数にはできない。)

 s=10 なら、先手は位の大きい方へは、0 の数字を入れる。

 もし、s=9 なら、後手は先手がどのような値を入れても最後の値を適切に選べば、全体の
100桁の整数を11の倍数にすることが可能なので後手がそれに気付けば後手が勝てる。

 |x1-y1|=|x2-y2| (mod 11) の時、x<y の時は、(x+11)-y=t、x>yの時は、x-y=t とする。

 先手は位の大きい方へt-1の値を入れる。
(すると後手は最後に0〜9のいずれを入れても全体を11の倍数にはできない。)

 もし、t=0 なら、先手がどのような値を入れても最後後手は適当な値で11の倍数にすること
が可能なので後手にも勝利の可能性は残る。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年4月1日付け)

 一手前の相手が書いた数は使えないとかの付加ルールがつくと私にはお手上げですが、
11倍数ゲームでは、100桁でなくとも偶数桁ならば、空欄を「.」で表して、1133..99..7788 とか
77..66..441155..22..99 とか、二桁ごとに区切った枠に書き込む数が常に同じになるようにす
れば後手の必勝のような気がします。

 13倍数ゲームでは、001001 が13の倍数のようですから、967967が13の倍数ですね。する
と後手番にしてみると、左から96桁だけの枠のみを切り出した数が13の倍数にすることは必
ずできるので、右から数えた4桁での勝負ですね。直感では先手になにか手段がありそうな
気がします。うまく詰められません


 DD++さんからのコメントです。(平成30年4月2日付け)

 (1) は、ハンニバル・フォーチュンさんが仰るとおり、「二桁ごとに区切った枠に書き込む数
が常に同じになるようにすれば後手必勝」で正解です。

 では、(2) のように、最高位を0にできない場合はどうでしょうか。後手は同じように攻めると、
先手に下位から順に0を書かれたりすると、最後だけ0を書けずに後手は負けてしまいます。


 らすかるさんからのコメントです。(平成30年4月2日付け)

 (2)は、先手必勝ですね。

 左から奇数桁目を「左桁」、偶数桁目を「右桁」と呼ぶことにします。先手は最初、左から二
つ目の枠に0を書きます。この後先手は、

・後手が左桁に書いたら空いている右桁、右桁に書いたら左端以外で空いている左桁に後
 手と同じ数字を書く
・ただし、後手が左端の枠に数字を書いた直後だけは1少ない数字を書く

のようにすれば先手の勝ちとなります。


 DD++さんからのコメントです。(平成30年4月2日付け)

 らすかるさん、正解です。さて、では13の倍数の場合は?


 らすかるさんからのコメントです。(平成30年4月3日付け)

 完全に証明はしていませんので間違っている可能性もありますが、13の場合は多分、左
端桁が非0という制限があってもなくても先手必勝だと思います。

 左からn番目の桁をd[n]とします。

 d[5]とd[8]、d[6]とd[9]、d[7]とd[10]、d[11]とd[14]、d[12]とd[15]、d[13]とd[16]、・・・、
d[6k+5]とd[6k+8]、d[6k+6]とd[6k+9]、d[6k+7]とd[6k+10]、・・・、d[95]とd[98]、d[96]とd[99]、
d[97]とd[100] そして、d[1]とd[4]

の49組をペアと考えます。1001≡0 (mod13) なので、ペアの2桁に同じ数字を書くと、13で
割った余りは変わりません。

 最初に、先手は、d[2]=4 とします。d[3]に何を書かれても、10d[2]+d[3]≡0 (mod13) に
なりません。

 その後、後手が49組のペアのどこかに数字を書き込んだ場合は、ペアの他方に同じ数字
を書き込みます。

 ただし、左端桁が非0という制限があって、d[4]に0が書き込まれた場合は、d[1]に3を書き
込みます。

 0≦m≦9 のとき、3400+10m≡0 (mod13) になりませんので、d[3]に何を書き込んでも
左4桁が13の倍数になることはありません。

 もし、後手が、d[3]に数字を書き込んだ場合、先手は残りのペアのどこかに、「ペアの他方
に0〜9のどれを書いても、13の倍数にできない数字」を書き込みます。

 ここが未証明なので冒頭に「多分」と書いたのですが、現在13の倍数でない場合は必ずそ
のような数字が存在すると思います。

 後手がそのペアの他方を埋めない間は、同様に後手と同じ数字をペアの他方に書いてい
きます。

 これを続ければ、13の倍数にならないように出来ると思います。


 DD++さんからのコメントです。(平成30年4月3日付け)

 らすかるさん、正解です。

 未証明な部分は、1≦k≦12 のいずれに対しても、x-y≡k (mod13) の解に、0≦x≦9 かつ
10≦y≦12 であるものと 10≦x≦12 かつ 0≦y≦9 であるものが存在することから言えますね。

(補足) d[1] が空欄のまま d[3] を後手が埋めたとき、次に先手(先頭以外どの枠にも必勝
    を崩さない数字が少なくとも1つある)が d[4] を使うと、後手が d[1] を埋めてくれるので、
    先頭がゼロか否かという問題から解放されます。

     こうすれば先手は d[3] より先に d[4] を埋められたときの対応以外、先頭ゼロ問題
    の対応を考えなくてよくなります。

     また、別解として、初手で d[3] に 7 を書き、d[2] を使うより先に d[4] に 0 を書かれ
    た場合は d[1] に 4 を書く作戦もとれます。

     この場合も d[1] が空いたまま d[2] を使われたら次に先手が d[4] を使ってしまえば
    先頭ゼロ問題から解放されます。


 GAI さんからのコメントです。(平成30年4月4日付け)

 らすかるさんの方針で進んでみました。ただし、枠を100個準備するのは多過ぎたので、10
個(原理的には同じ方針が取れると思うので)とし、先手をS,後手をGで表し進んでみました。

(例1)
枠[1 2 3 4 5 6 7 8 9 10]
S:   4
G:   4 5
S:   4 5   6
G:   4 5   6       9
S:   4 5   6 9     9
G:   4 5 1 6 9     9  (ここでもし枠4へ後手が0を入れれば先手は枠1へ3を入れることになる。)
S: 1 4 5 1 6 9     9
G: 1 4 5 1 6 9 7   9
S: 1 4 5 1 6 9 7   9 7
G: 1 4 5 1 6 9 7 8 9 7 ===>13の倍数より後手の勝利


(例2)
枠[1 2 3 4 5 6 7 8 9 10]
S:   4
G:   4 5
S:   4 5   8
G:   4 5   8       9
S:   4 5   8 9     9
G:   4 5 1 8 9     9
S: 1 4 5 1 8 9     9
G: 1 4 5 1 8 9 7   9
S: 1 4 5 1 8 9 7   9 7
G: 1 4 5 1 8 9 7 * 9 7


*には0〜9のいずれを入れても13の倍数にはできない。従って先手の勝利
(尚d(5)=9の値でも可能であった。)

 この時疑問なのが先手がとる、ペア一方(この場合枠5)へ入れる数字(例1では6、例2で
は8)をまだ他の枠に入りきれない時点でどんな値を入れるべきかをどのように選択できる
のか?

 後手が枠3へ入れた数字に従って、ペアの一方へ入れる数字は異なることになるようです
が、これは事前に調べて覚えておく必要があるのでしょうか?試しにコンピュータでの調査
から後手がd[3]へ入れた後の先手がペアの一方に入れるべき数の対応表

[0-->1,2,3] 、[1-->5,6,7] 、[2-->9] 、[3-->0,1,2] 、[4-->4,5,6] 、[5-->8,9]
[6-->0,1] 、[7-->3,4,5] 、[8-->7,8,9] 、[9-->0]

で合っているでしょうか?これを覚えておけばいいのかな?


 moonlight さんからのコメントです。(平成30年4月4日付け)

 これはなかなか楽しい問題ですね。色々と遊べる。素敵や。


 らすかるさんからのコメントです。(平成30年4月4日付け)

 GAIさんの

 後手がd[3]へ入れた後の先手がペアの一方に入れるべき数の対応表

[0-->1,2,3] 、[1-->5,6,7] 、[2-->9] 、[3-->0,1,2] 、[4-->4,5,6] 、[5-->8,9]
[6-->0,1] 、[7-->3,4,5] 、[8-->7,8,9] 、[9-->0]

で合っているでしょうか?これを覚えておけばいいのかな?


で、数字を入れる場所によっても変わりますし、d[2]=4,d[3]=5,d[5]=8,d[8]=3 のように後手が
ペアの片割れにさらに別の数を入れた場合にも値が変わりますので、そのように簡単には
決まりません。

 具体的に値を決める式を作ってみたら、先手が入れるべき数字は

(3×4^m×n+10)%13 、(3×4^m×n+11)%13 、(3×4^m×n+12)%13

の3数のうち9以下のものとなりました。ただし、nは空欄を0とした場合の現在の値、mは数
字を入れようとする場所(右端が1、その左が2、…)です。

 GAIさんが書かれた例では、例えばd[3]=7の場合、先手がd[5](右から6番目の枠)に入れ
るべき数字は、

(3×4^6×0470000000+10)%13 = 3
(3×4^6×0470000000+11)%13 = 4
(3×4^6×0470000000+12)%13 = 5

のように求まります。mは6で割った余り、nは13で割った余りにしてもOKなので、nを13で割っ
た余りさえ暗算できれば何とかなるかも知れません。

 12行×6列の各マスに3つずつ値が入っている表を作れば、上記の計算は省略できますが、
それにしてもnを13で割った余りは必要になりますので簡単ではないですね。


 GAI さんからのコメントです。(平成30年4月5日付け)

 自分も実験していて、色々な所に相手も勝手にランダムな値を埋め込んでくるよな〜、と
頭の中がこんがらがっていました。

 こちらが計画しているように相手が数字をはめ込んでくれれば楽なんですが、これを掴め
る式が欲しいなと思っていたら、なんとこれを見事に解決できる式として上記の式を利用で
きるではありませんか!
(こんな表現の式を今まで思い付きも、見たこともありませんがものの本質を見事に捉えた
表現方法ですね。ほんと感心します。)

 これによると、ゲームの推移により、 (a)45(b)8(c)(d)3(e)(f)

 この後先手が空欄( )に入れるべき数が、

(a)->0,1
(b)->8,9
(c)->5,6,7
(d)->0,1
(e)->2,3,4
(f)->8,9

 更に、ゲームが進行し、 145(b)8(c)(d)36(f) となった後の先手の選択が、

(b)->1,2,3
(c)->7,8,9
(d)->6,7,8
(f)->1,2,3

と、上記のものとはその都度変更したものになっていくのですね。

 いやいや勝つのも大変。(でも必ず勝てる不思議なゲーム。たぶんDD++氏発案のゲーム
でしょうが、この面白さを直感で感じ取れる感性にも驚きです。)


 DD++さんからのコメントです。(平成30年4月5日付け)

 私が想定していた手順はこんなです。らすかるさんのと中身ほぼ同じですが。

 最初に d[2] に 4 を入れて、相手が d[3] に 5 を入れてきたとしましょう。ここで先手は d[4]
を使いたいとします。

 045X000000 の X に一桁入れて(ただし、10や11や12も一桁に押し込めてよいと考える)
13 の倍数にしようと考えると、5 を入れれば13の倍数になることがわかります。

 これは、(d[1],d[4]) が (0,5), (1,6), (2,7), (3,8), (4,9), (5,10), (6,11), (7,12), (8,0), (9,1), (10,2),
(11,3), (12,4) のいずれかで埋まると、あとは後手必勝になってしまうことを意味するので、先
手は d[4] に d[0] が9までに収まっていない 2, 3, 4 のいずれかを書き込めばいいことになり
ます。

 以下同様に繰り返していけばOKです。

 先頭を埋めたいという場合以外はどの枠でも必ず適した数字があり、先手の手番なら必ず
2枠以上空いているので、この手順は最後まで続けられます。

 100桁でやる場合は毎回割り算をするのではなく、今書いた数で余りがどう変化したかを考
える方がいいでしょうね。

 ...言葉足らずでした。これは空欄がペアのとこだけで自分の手番になった場合の話です。
そうじゃない場合は後手が埋めた場所のペアを同じ数字で埋めるの優先です。

 また、d[3] を使われた直後にさっさと d[4] を埋めないと、

 先手 d[2]=4 、後手 d[3]=5 、先手 d[5]=8 、後手 d[4]=0

と進むと、先頭ゼロ禁ルールの場合、先手は d[1]=0 で返せず、面倒なことになります。

 先手 d[2]=4 、後手 d[3]=5 、先手 d[4]=5

としておけば、後手自ら d[1] を埋めてくれる(埋めるまでペア攻撃が終わらない)ので安心し
て続けられます。


 GAI さんからのコメントです。(平成30年4月5日付け)

 ここは、100個埋める枠で考えるとここは先手d[4]=2,3,4になりませんかね?

 結局、mod 13での先手必勝の戦略は(枠が100個の場合=枠が10個の場合に同じ)、
初手d[2]=4を入れ(d[2]=8でもいいような気がします。ただし下の数字はずれてきます。)
後手がd[1]またはd[4]以降d[100]のいずれかに値を任意で入れれば、そのペアになる他方
に同じ値を入れていき、また、d[3]に後手が飛び込んできたら即座にd[4]をd[3]へ入れた後
手の数字(s)に対し、

s:-->先手がd[4]へ入れるべき数
0-->0,1,2
1-->3,4,5
2-->6,7,8
3-->9
4-->0,1
5-->2,3,4
6-->5,6,7
7-->8,9
8-->0
9-->1,2,3

さえしっかり覚えておけば勝てる、でいいのでしょうか?


 DD++さんからのコメントです。(平成30年4月5日付け)

GAIさんへのお返事です。

 100個埋める枠で考えるとここは先手d[4]=2,3,4になりませんかね?

 その通りです。書き間違いでした。

 初手d[2]=4を入れ(d[2]=8でもいいような気がします。

 確かに、8でも大丈夫ですね。d[2]=4 だと、d[3] より前に d[4]=0 とされたときに d[1]=3 と返
せば、最初に d[2]=8 としたのと同じ状況になってセーフ、というのが d[2] に4を選ぶ理由でし
たが、最初に d[2]=8 でも同じような返し方ができますね。

 その次に d[1] にデタラメに入れられたときに、またどこか次を適切に埋めねばなりません。
まあ、d[1] に入れられた数字と同じものを d[10] に入れるとかでしばらくは回避できますが、
いずれ d[3N+1] が全部埋まったときと、d[3N+2] か d[3N] のどっちかが埋まったときと、2回
はちゃんと考えて次を書かないといけません。

 16桁戦くらいで後手に「先手とペアになる場所をさっさと適当に埋める」選択をさせれば理
解できると思います。



                         投稿一覧に戻る