 nothing ( No.8 ) |
- 日時： 2011/11/14 15:14
- 名前： 宇奈月
- 答えを発表します。
nが偶数の場合には後手必勝であることは前問で示しましたのでnが奇数の場合を考えます。
k=k1のとき先手必勝だとします。
後手は箱を取る回数が最大になる戦略をとったとします。
最後に後手が箱を取る直前には次の条件を満たしていたはずです。
区画1のすべての箱を２つずつペアにして、各ペアの番号の和がすべて等しくなるようにできる---①
その和の値は箱の個数に応じて一意に決まります。
また、このときの箱の個数もk1の値に応じて一意に決まります。
よって、このとき区画2にある箱の番号計k2も一意に決まります。
ということは、k=k2のときも先手必勝でなくてはいけません。
k1>k2ですので、これを繰り返すことによって、先手必勝のkの値の減少列 k1>k2>k3>・・・を作ることができます。
1回毎に区画1の箱の個数は2個ずつ増えますので最終的にn-1個にすることができます。
つまり、最初に先手が箱を一つ移動させた時点で①の条件を満たさなければいけないということです。
その後、後手が取った箱とペアになる箱を取っていけば先手の勝ちです。
各回における区画2の箱番号計は一意に決まりますので、これ以外に必勝手順はありません。
では次に、先手が一回目に箱を移動させた時点で①の条件を満たす場合を考えてみましょう。
n=2m+1とします。
区画1の箱の個数はn-1=2m個です。
ペアがm個できますので、区画1の箱番号計はmの倍数です。
箱番号総計はn(n+1)/2=(2m+1)(2m+2)/2=(2m+1)(m+1)=2m^2+3m+1です。
これはmで割ると1余る数ですので、移動した箱はmで割ると1余る数です。
そのような数は1から2m+1の中には、1,m+1,2m+1の3つしかありません。
どの場合も条件①を満たします。
ペアの箱番号計はそれぞれ、2m+3,2m+2,2m+1です。
先手が箱を移動した回数をtとすると、移動後の区画2の箱番号計は、それぞれ
1+(2m+3)(t-1),m+1+(2m+2)(t-1),2m+1+(2m+1)(t-1)
と表せます。
それぞれA(t),B(t),C(t)とすると、
C(t)-B(t)=m-t+1
B(t)-A(t)=m-t+1
1≦t≦mなので、m-t+1＞0であり、A(t)＜B(t)＜C(t)
A(t+1)-C(t)=2(m+t+1)＞0なので、C(t)＜A(t+1)
よって、A(1)＜B(1)＜C(1)＜A(2)＜B(2)＜C(2)＜・・・＜A(m)＜B(m)＜C(m)
となり、すべての値は異なっています。
k＞nなのでt=1は有り得ません。
2≦t≦mですので、tの取り得る値はm-1個。
各tにつき3個のkが対応しますので、kの値は3(m-1)個です。
m=(n-1)/2より、3(m-1)=3(n-3)/2です。
以上より、nが偶数のときは0個、nが奇数のときは3(n-3)/2個です。
これを一つの式で表すと、3mod(n,2)*(n-3)/2個と書けます。
|
|
FAQ
RSS