2020年(令和2年)一橋大学後期-数学[4] - [別館]球面倶楽部零八式markIISR

2022.10.22記

[4] AとBの二人が，Aを先手として以下のルールで交互に石を取り合うゲームを行う．

ルール
・はじめに $n$ 個の石がある．

・まず先手は $(n-1)$ 個以下の好きな数の石を取る．

・以降は，直前に相手が取った石の数の2倍以下の好きな数の石を取ることを繰り返す．

・最後の石を取ったほうが勝ちとなる．

相手の石の取り方によらず勝てるような石の取り方があるとき「必勝法がある」という．

例えば $n=4$ のとき，まずAが1個取れば，次にBは1個か2個取ることができる．もしBが1個取ったなら，Aは次に2個取ることで勝てる．もしBが2個取ったら，Aは次に1個とることで勝てる．このようにのB石の取り方によらずAは勝てるので，Aに必勝法がある．

(1)　 $n=5$ のとき，AまたはBのどちらに必勝法があるか答えよ．

(2)　 $n=10$ のとき，AまたはBのどちらに必勝法があるか答えよ．

注) 問題文にはないが，パスはできず必ず1個以上の石を取らなければならない（石を0個取るということはしない）

本問のテーマ

2倍取りゲーム
ゼッケンドルフ(Zeckendorf)表示

2022.10.22記
ゼッケンドルフ表示については
2017年(平成29年)九州大学後期-数学(理系)[5] - [別館]球面倶楽部零八式markIISR
にも出題がある．この(1) の2倍で押さえられるところが2倍取りゲームと関係がある．

結果は $n$ がフィボナッチ数列の項であるときには B には必勝法が存在し，それ以外のときには A に必勝法が存在する

数学談話室倍取りゲーム(pdf)

石取りゲームとFibonacci数

あたりを参照すれば良いだろう．

「後手必勝パタンにして相手の番にすることができれば先手必勝になる」ことがポイント．

[解答]
まず，残りの 1/3 以上取ってしまうと次に負けてしまうことに注意する．

$n=2$ のとき，Aは必ず残りの 1/3 以上を取るので負ける，つまり Bに必勝法がある．

$n=3$ のとき，Aは必ず残りの 1/3 以上を取るので負ける，つまり Bに必勝法がある．

$n=4$ のとき，問題文から Aに必勝法がある．

$n=5$ のとき，Bに必勝法がある．
(i) A が2個以上(1/3 以上になる)取ればBが残りを取ればBが勝つ
(ii) A が1個取れば残り4個となり，Bが問題文のAの戦略をとることによりBが勝つ
よって Bに必勝法がある．

$n=6$ のとき，Aは1個取れば残り5個となってBの番となるが，Bは残り全部を一度に取れないので，Aに必勝法がある．

$n=7$ のとき，Aは2個取れば残り5個となってBの番となるが，Bは残り全部を一度に取れないので，Aに必勝法がある．

$n=8$ のとき，Bに必勝法がある．
(i) Aが3個以上取ると 1/3 以上なのでAが負ける．
(ii) Aが2個取るとBは残り6個から1個取って残り5個となってAの番となるのでBには必勝法がある．
(iii) Aが1個取るとB は残り7個から2個取って残り5個となってAの番となるのでBには必勝法がある．
よって必ず Bが勝つことができるので Bに必勝法がある．

$n=9$ のとき，Aは1個取れば残り8個となってBの番となるが，Bは残り全部を一度に取れないので，Aに必勝法がある．

$n=10$ のとき，Aは2個取れば残り8個となってBの番となるが，Bは残り全部を一度に取れないので，Aに必勝法がある．

以上から，(1) Bに必勝法がある，(2) Aに必勝法があるとなる．

$n=11$ のとき，Aは3個取れば残り8個となってBの番となるが，Bは残り全部を一度に取れないので，Aに必勝法がある．

$n=12$ のとき，
（Aは4個取れば残り8個となってBの番となるが，Bは残り全部を一度に取れてしまうので，このような取り方はしない．Aが2個か3個取るとBから残り8個になって戻ってきて負けることになるので）
Aは1個取って残り11個でBの番にする．
するとBが1個取れば10個で戻ってきて2個とれば8個でBの番にできるのでAの勝ち，Bが2個取れば9個で戻ってきて1個とれば8個でBの番にできるのでAの勝ち，となるので Aに必勝法がある．

$n=13$ のとき，
(i) Aが5個以上取ると 1/3 以上なので残り全部Bが取って Aが負ける．
(ii) Aが4個取ると Bが1個取って8個でAの番となるので Aが負ける．
(iii) Aが3個取ると Bが2個取って8個でAの番となるので Aが負ける．
(iv) Aが2個取ると Bが3個取って8個でAの番となるので Aが負ける．
(v) Aが1個取ると Bが残り12個のうち1個取ってAの番となるので， $n=12$ の1個取って相手に渡す戦略によって Aが負ける．
よってBに必勝法がある．

というように続いていく．

[大人の解答]
このゲームにおいてBに必勝法があるのは $n$ がフィボナッチ数列，つまり $F_1=F_2=1$ ， $F_{m+2}=F_{m+1}+F_m$ で定義される数列に登場する2以上の自然数のときに限り，それ以外の場合は Aに必勝法があることを示す．

そのためにまず，任意の自然数はフィボナッチ数列の初項を除く隣り合わない項の和（同じ項は2回以上用いない）で一意に表すことができることを示す．これを Zeckendorf 表示という．

この証明は帰納法で行う． $n=1$ のとき $1=F_2$ である．
$n\leqq k$ の全ての自然数で題意が成立していると仮定する．

$n=k+1$ のとき， $k+1$ 以下の最大の $F_n$ を $F_m$ とおくと $k+1-F_m$ が帰納法の仮定により一意な Zeckendorf 表示をもつが，もしここで $k+1-F_m$ の Zeckendorf 表示に $F_{m-1}$ が含まれているとするとフィボナッチの隣り合う項を用いないことに反するので， $k+1-F_m$ の Zeckendorf 表示に $F_m$ を加えたものは Zeckendorf 表示にならない．そこで $k+1-F_m$ の Zeckendorf 表示には $F_{m-1}$ が含まれないことを示す．

もし $k+1-F_m$ の Zeckendorf 表示には $F_{m-1}$ が含まると仮定すると， $k+1-F_m\geqq F_{m-1}$ つまり $k+1\geqq F_m+F_{m-1}=F_{m+1}$ となり $F_m$ の最大性に反する．よって $k+1$ は $F_m$ と，「 $F_{m-1}$ を含まない Zeckendorf 表示」の和で表すことができるので Zeckendorf 表示をもつ．

また，Zeckendorf 表示においてフィボナッチ数列の隣り合う項が登場しないことから Zeckendorf 表示で登場する項の添字が複数ある場合，その添字が小さいもの2つは $F_{s}+F_{s+t}$ （ $t\geqq 2$ ）となり，この和は
$F_s+F_{s+t}\lt F_{s+t-1}+F_{s+t}=F_{s+t+1}$
と大きい添字の次の項未満となるので，この操作を繰り返すと $F_{m-1}$ から最大となる Zeckendorf 表示をもつ数は $F_{m}$ 未満となる．よって $k+1$ の Zeckendorf 表示は必ず $F_m$ を含まなければならず，よって $k+1-F_m$ の Zeckendorf 表示の一意性から， $k+1$ の Zeckendorf 表示もそれに $F_m$ を加えた一意的となる．

以上から，自然数の Zeckendorf 表示は一意に存在する．

では，このゲームにおいてBに必勝法があるのは $n$ がフィボナッチ数列，つまり $F_1=F_2=1$ ， $F_{m+2}=F_{m+1}+F_m$ で定義される数列に登場する2以上の自然数のときに限り，それ以外の場合は Aに必勝法があることの証明に入る．

まず， $n$ がフィボナッチ数列の項でないとき， $n$ の Zeckendorf 表示は少なくとも2項からなる．このとき A はZeckendorf 表示を構成する最小のフィボナッチ数列個だけ取れば良い．

ここで Zeckendorf 表示で登場する複数項の小さいもの2つを $F_{s}+F_{s+t}$ （ $t\geqq 2$ ）とすると，Aは $F_s$ 個だけとる．すると B は $2F_s$ 個までしか取れないが， $F_{s+t}\geqq F_{s+2}=F_{s+1}+F_s\gt 2F_s$ 　より全て取ることができないので，またAの番が回ってくる．

もしここで Aの番が回ってきたときに後手必勝のフィボナッチ数になっていたと仮定する．このようなことが起こるのは，
Zeckendorf 表示が丁度2個のフィボナッチ数の和
$F_{s}+F_{s+t}$ （ $t\geqq 2$ ）
となっている場合から A が $F_s$ 個取ったあと B が残り $F_{s+t}$ 個からいくつか取って $F_{s+t-1}$ 以下のフィボナッチ数を残す必要がある．これが可能なとき，B は $F_{s+t}-F_{s+t-1}=F_{s+t-2}$ 個以上取っていることになるので，Aは
$F_{s+t-1}$ 以下から $2F_{s+t-2}\gt F_{s+t-1}$ 個まで取ることができるので，全部取れることになるので結局Aが勝つ．

よって次にAの番になったときは，残り全部とれるフィボナッチ数になっているか，フィボナッチ数になっていないかのいずれかである．ここで，Aの番に戻ってきたときに，必ず Zeckendorf 表示の最小のフィボナッチ数だけ取ることができることを示す．Bが $p$ 個取ってフィボナッチ数にせずに Aの番に戻るとき， $p$ のZeckendorf表示に表れる一番小さいフィボナッチ数を $F_v$ とすると，
$F_m-p$ の Zeckendorf 表示には $F_{v+1}$ または $F_{v-1}$ （Zeckendorf表示には $F_1$ は用いないので $v=2$ のときに限り $F_{v=1}=F_2$ とする）のいずれかが登場するが，
$F_{v-1}\lt F_{v+1}\lt 2F_v\leqq 2p$
であるから，Aはフィボナッチ数でない $F_m-p$ （Zeckendorf 表示で2つ以上の項をもつ）の最小のフィボナッチ数だけ必ず取り除くことができるので，必勝法を繰り返すことができる．

よってAの必勝であることがわかる．

次に $n$ がフィボナッチ数（ $F_m$ とする）のとき，Aがいくつか取って後手必勝のフィボナッチ数残してBの番にしようとすると， $F_m-F_{m-1}=F_{m-2}$ 個以上取らなければならないが，その場合，残り $F_{m-1}$ 以下から $2F_{m-2}$ 個まで取れることから全部 B に取られて負けるので，フィボナッチ数残してBの番にすると必ず負ける．よってAがフィボナッチ数ではない数だけ残すことになるので，Bはフィボナッチ数でない場合の先手必勝法を用いることにより，Bが必勝となる．

あまり整理されていない．フィボナッチ数に対して
$2F_{n-2}\lt F_n\lt 3F_{n-2}$
が成立することを使うともう少し洗練した解答になるだろうけど，時間がないなぁ。