[過去ﾛｸﾞ] 面白い問題おしえて〜な 十四問目 (1001ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
581(3): 2008/09/20(土)16:37 AAS
石の山が一つあり、二人が交互に石を取っていく。
最後に石を取ったほうが勝ちである。
最初の人は一つ以上の石を取る。ただし全部の石を取ることは出来ない。
次からは交互に一つ以上で、前の人が取った数の二倍以下の石を取る。
石の数が n ≧ 4 のとき、先手必勝であることを示せ。
582: 2008/09/20(土)17:50 AAS
>>581
どうみてもn=5で後手必勝なのだが．．．
583(2): 2008/09/21(日)02:59 AAS
>>581
n>4 の場合、残った石の個数をフィボナッチ数に「した」方が勝ちで、「された」方が負け。
正確には、残りがフィボ個の状態で手番を「渡された」プレーヤーは、直後に自分が全部を
取れない限り、負ける。つまり初期値が4以上のフィボ個だったら後手必勝。
略証
f(1)=2, f(2)=3, f(3)=5, ,,, ,f(k)=f(f-1)+f(k-2) とする。
n=f(1)=2, n=f(2)=3のときは主張は正しい。i.e. その時点で手番を持っている方は、
そこで全部取れない場合は負け。n=f(2),f(3),,,,f(k-1) の全てでそうだと仮定する。
さて、現在f(k)個の石が残っていて、プレイヤーAの手番だとする。
これを直近のフィボ数 f(k-1) にした者が勝ち。それにはf(k-2)個の石を取ればよい。
省5
744: 2008/10/10(金)10:15 AAS
>>581 のゲームで「二倍以下」のところを「3倍以下」にしたとき、
後手必勝となるのは最初の石数がどのようなときか？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.027s