ルール説明

「数研部員と勝負!」は, 毎年数学研究部が文化祭に出しているゲームです. ゲームが 3 個あり,それぞれのゲームで 2 連勝したらこのゲームに「勝った」となります. チェスや将棋と同じように, ゲームには「先手」「後手」がおり, それぞれのプレイヤーが交互に手を打ちます. 参加者は「先手」「後手」のどちらを選ぶかを自分で決めることができます. さて, あなたは勝てるかな???

☆☆☆☆☆ GAME PROBLEMS 2018: QUESTIONS ☆☆☆☆☆

GAME #1: サイコロ転がし (難易度:★★)

11 × 11 のマス目があり, (参加者側から見て) 左手前にサイコロがあります. サイコロは最初一番上に 1, 手前に 2, 右側に 3 (or 4?) が書かれています. 先手と後手は交互に, サイコロを右または奥に 1 マス転がします. 先手と後手が 10 回ずつサイコロを転がし終えると, サイコロの位置は右奥になりますが, そのときの上の面に書かれた数が 2, 3, 4, 5 のいずれかならば先手が勝ち, 1, 6 のどちらかならば後手が勝ちます. さて, どちらが勝つことができるでしょうか?

GAME #2: フィボナッチ数と石 (難易度:★★★)

フィボナッチ数は, 小さい順に $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, $89$, $144$, $233$, $\dots$ と続く数です. $\text{(1 個前のフィボナッチ数)} + \text{(2 個前のフィボナッチ数)}$ がこのフィボナッチ数と一致する、という性質があります. 例えば $34 + 55 = 89$ となります.

最初 $140$ 個の石があります. 先手と後手は交互に,「$N$ 個の石を取り除く ($N$ がフィボナッチ数であれば何でもよい)」操作をします. ただし、今ある石の数以上の個数を取り除くことはできません. 石の数を $0$ にした方が勝ちです. さて, どちらが勝つことができるでしょうか?

GAME #3: LIS ゲーム (難易度:★★★★☆)

先手と後手は交互に、左から順に 1 つずつ数を書いていく. ただし, 書く数は $1$ 以上 $13$ 以下の整数でなければならず, 同じ数が 2 回登場するような書き方をしてはならない.

最終的には 13 個の数が左から順に並べられることになる. この状態の LIS (最長増加部分列, Longest Increasing Subsequence) は,「いくつかの数を消したときに、左から右につれて数が大きくなっていくようなもののうち, 最長の長さ」とします. 先手は最終的な LIS を奇数にすれば勝ちで, 後手は偶数にすれば勝ちです. さて、どちらが勝つことができるでしょうか?

☆☆☆☆☆ GAME PROBLEMS 2018: ANSWERS ☆☆☆☆☆

GAME #1: サイコロ転がし

このゲームは後手必勝です. 後手は物真似戦略を使うことができます. 後手は, 先手と同じ向きにサイコロを転がします. そのとき, サイコロの上の面の数字は, 最初のサイコロの下の面の数字と同じになります (例えば最初の上の面が 1 のときこれは 6 になり, 最初の上の面が 6 のときこれは 1 になる). 先手と後手が 10 回ずつサイコロを転がし終えると, 最初から 2 回ごとにサイコロの目は 1→6→1→6→1→6→1→6→1→6→1 と遷移し, 後手はサイコロの目を 1 にすることができます.

GAME #2: フィボナッチ数と石

$N\leq 143$ のとき,「$N$ を $36$ で割った余りが, $34$ ではない 1 の位が $0$ か $4$ の数のとき」に限って後手必勝です. 後手必勝であるのは,「次打った後の石の数が, 全部先手必勝」のときに限ることに注意して考察します. まず $N = 0$ のとき, 明らかに後手必勝です. $N = 1$, $2$, $3$ のとき, 先手は石の数を $0$ にして勝つことができるので, 先手必勝です. $N = 4$ のときは, 石の数をフィボナッチ数だけ減らして, 後手必勝にすることはできません. $N = 5$, $6$, $7$, $9$ のとき, 先手は石の数を $4$ にして後手必勝に持っていくことができるので, 先手必勝です. $N = 8$ のとき, $4$ に減らすことはできないですが, $8$ がフィボナッチ数であることに注意すると, $0$ に減らすことができるので先手必勝です. $N = 10$ のとき, 後手必勝です.

そのまま $0$, $4$, $10$, $14$, $20$, $24$, $30$, $\dots$ と続いていくように感じられますが, 実は $34$ はフィボナッチ数なので $30$ の次の後手必勝の石の数は $36$ になります. $36$ が, $0$ ~ $35$ の「サイクル」にあたる「$0$」となり, 前のサイクルに一切影響を及ぼしません. つまり, $36$, $40$, $46$, $50$, $56$, $60$, $66$, と続きますが, $70$ は「$34$」にあたる数となります. このように考えると, 次は $72$ からスタートする「3 周目のサイクル」になり, この後は $108$ からスタートする「4 周目のサイクル」ができます.

「$N$ を $36$ で割った余り」が, サイクルのどの部分にあたるのかを指し示し, 1 周目のサイクルで後手必勝となっているのは $N$ を $10$ で割った余りが $0$ または $4$ の数となります. したがって, $N = 140$ だから, このゲームは先手必勝となります.

ちなみに, $144$ はフィボナッチ数なので, 5 周目のサイクルは発生しません. $144$ 以上で後手必勝である石の数は, $150$, $160$, $169$, $176$, $186$, $192$, $196$, $202$, $\dots$ と続きます. また, 石の数が奇数で後手必勝である石の数は $169$, $635$, $723$, $791$, $2697$, $3057$, $3067$, $3073$, $3079$, $3089$, $\dots$ と続きます.

GAME #3: LIS ゲーム

長さが $4m+1$ である場合を考えます. まず答えから言うと「先手必勝」です. まず「カウンター」の整数 $c$ を定義します. 最初、$c = 2m$ です. 先手のターンのときは、$c \neq 0$ のとき「まだ使われてない数のうち, $2c$ 番目に大きい数」を書くという戦略を考えます. なので, 先手は最初のターンでは「$2$」と書きます。最初ではないターンでは, 先手が 1 個前に書いた数を $x$, 後手が直前に書いた数を $y$, 先手が書こうとしている数を $z$ として, $x < y < z$ ならば $c$ を $1$ 減らして値を決め直します. 先手が数を書くと $c$ を $1$ 減らします. $c = 0$ の時は、先手は「値が最大のもの」を選びます.

すると, 先手は確実に長さ $2m+1$ の LIS を作ることができます. まず, $c=2m$, $2m-1$, $\dots$, $4$, $3$, $2$, $1$ のときに書かれた数 ($c$ が $1$ 飛ばされる場合は、その直前に後手が書いた数) と, それに加えて「$c = 1$ のときに書かれた数の時点で書かれておらず, これより大きいただ一つの数」が LIS に加わるので, LIS の長さは $2m + 1$ 以上になることが分かります.

また、先手の戦略上, LIS の長さが $2m+2$ 以上になることはありえません. ここで $2m+1$ 個の数を $d_1$, $d_2$, $d_3$, $\dots$, $d_{2m+1}$ としますが, 次の 2 条件を両方満たせば最終的な LIS の長さが $2m + 1$ になります. これを証明していきたいと思います.

条件 1: $d_i$ の場所と $d_j$ の場所の間の後手の書いた数だけで長さ $j - i$ の増加部分列を作れない.

$d_{i+1}$, $d_{i+2}$, $d_{i+3}$, $\dots$, $d_{j-1}$ の中に後手が書いた数があれば目標は達成できないのは, そもそも $j - i$ 個の数がないことより明らかです. そうでなくてもどれか 1 つの場所で $x < y < z$ ($x$, $y$, $z$ の意味は、戦略のところを見てください) になるので, いずれにしろできません.

条件 2: $d_i$ より後の「$d$ には含まれていない数」で、長さ $(2m + 2) - i$ の増加部分列を作れない.

長さ $2m+1$ の LIS が出来上がっていない状態で、後手が「無駄になる手 ($d$ に含まれないようなもの)」を打っても、無駄になる場所を全部消したときの数列の長さが減るだけなので、後手にとって不利となるだけです。なので、最初の $2m+1$ 個の数はすべて $d$ の中に入っているものとします。

まず $d_i \geq 2i - 1$ は, 先手・後手の戦略を考えれば明らかです. $d_i$ より大きく $d$ に含まれている数は $(2m+1)-i$ 個あるので, 含まれていない数は $(2m+1)-i$ 個以下なります. したがって, 条件 2 で作れる増加部分列の最大の長さは $(2m+1)-i$ になります.

したがって, この戦略を使えば先手は必ず LIS の長さを $2m + 1$ にして勝つことができることが証明できました. $13$ は $4m + 1$ ($m = 3$ のとき) として表されるので, この戦略を使えば先手必勝です.

勝負Cによる説明

【勝負1】

最も簡単にすべき問題なので、player-friendly にするために「完全な最適戦略はやらないが、戦略をそこまでばれないように意識する必要は全くない」というのがポイント。天才ではない小学生でも解けるくらいやさしい問題に補正したほうが、楽しみやすさが増えると思ったから。

あなたが先手の場合

先手の場合、自分のターンが終わったときに 1 か 6 が上の面であれば勝てることが証明できる。だから、最初は適当にやって 1 か 6 が上の面であれば必勝戦略に移る、というものでも十分可能だが、もう少しゆるめても (適当にやる回数を増やしても) よさそうな感じではある。上の面が 2, 3, 4, 5 のどれかでありかつ、サイコロの座標が $x \leq 10$ and $y \leq 10$ を満たしていれば、サイコロの上の面を 1 か 6 にすることができるから、$\max(x, y)$ が 5, 6, 7 くらい以降で上の面が初めて 2, 3, 4, 5 になったときに最適戦略に移る、というのがおすすめ。

あなたが後手の場合

「最初から最適戦略をやり続ける」と勝てるが、そうすると面白くないので、1 回くらいは最適戦略以外でやる、という方針になる。とりあえず「$x$, $y$ が両方偶数かつ、上の面が 1 か 6」に来たらあなたは必勝戦略をやることを考える。そのとき、ターニングポイントは 4, 8, 12, 16, 20 ターン目であるが、最初は自分が「相手と逆の方向に行く」戦略でやった場合、20 ターン目までにターニングできる確率は $862/1024=\text{約 }84.2\ \%$、16 ターン目まででも $808/1024=\text{約 }78.9\ \%$ である。すると、相手が「最後の 4 手だけ意識して、あとは適当にやった場合」の相手の勝率は $22.1\ \%$ となり、2 連勝する確率は約 $4.9\ \%$ であることから、この戦法は確率的に OK である (その一方で、相手が前回勝ってたら次は最適戦略でいく、というのもありだが・・・)

【勝負2】

この問題は「$n \leq 143$ のとき、$n \bmod{36} = 0$, $4$, $10$, $14$, $20$, $24$, $30$ のどれかならば後手必勝」という性質を使うので、最適戦略でやってもばれる可能性はかなり少ない。基本的に、「自分が勝っている状態」ならば、相手に「$n ^ \prime \bmod{36} = 0$, $4$, $10$, $14$, $20$, $24$, $30$ のどれか」でわたすことができるから、そのような手のうち 1 つをランダムに選ぶ。自分が後手をやったり失敗したりで「自分が負けている状態」になっているときは、できるだけ石の数を変化させないようにすることが好ましい。また、もう一度 $n \bmod{36} = 0$, $4$, $10$, $14$, $20$, $24$, $30$ の状態にされないようにするには、フィボナッチ数は奇数の方が多いことより、相手に偶数でわたす確率を高くした方がよいかも (自分が負けている状態のとき $n$ は偶数だから、$2$, $8$ を打つ確率を $1$, $3$, $5$ を打つ確率より上げてもよい) が、それはやらなくてもよい。

【勝負3】

自分が先手の場合

これは最適戦略で OK。最適戦略は解説を参照。相手が強そうな人だったらエスパーでばれる可能性がないわけではないので、こういう人には時間稼ぎ (例えば最初の方で相手が $13$ を書いてきたらきたら $12$ を書く、のような意味のない動き) をやるのもありだし、最初の方で値を $1$ 個くらい上下させる (例えば、最初に $1$ や $3$ を書く、など) のもよいが、別に気にしなくてもよい。

自分が後手の場合

「今残ってる数のなかで、$c=6$, $5$, $4$, $3$, $2$, $1$ のとき大きいほうから何番目の数を書くべきか」みたいなのの数列は、先手をやる場合 $12$, $10$, $8$, $6$, $4$, $2$, $1$ となるが、後手をやる場合は最初の相手の手によって変えなければならない。方針として、相手が $2$ 以上の数を書いてきた場合は、LIS の長さを $6$ にする。戦略は、必勝法と同様にやる。(大きいほうから 10, 8, 6, 4, 2, 1 番目、みたいな感じ) ただ、最初相手が $1$ とかで書いてきた場合などは、LIS の長さを $8$ にする。そうすると、相手が負ける確率が上がる。