 pc ( No.7 ) |
- 日時： 2011/11/08 14:47
- 名前： 宇奈月
- nが偶数のときは、前問で考えたように、先手は最悪でも引き分けに持ち込めます。
箱の番号の総計が奇数になる場合は先手必勝です。
総計が偶数になるとき、後手が引き分けに持ち込むことができるのか考えてみます。
nが偶数の場合、m=n/2とすると、番号総計=2m(2m+1)/2=m(2m+1)
mが偶数のときは番号総計も偶数で、mが奇数のときは番号総計も奇数です。
つまり、nが4の倍数であれば総計は偶数、nが4の倍数でない偶数であれば総計は奇数です。
nが4の倍数のとき、m=n/2は偶数です。
このとき、後手は次のように並べれば負けることはありません。
1番からm番の箱を番号順に並べます。
m番の次に2m番の箱を置き、2mからm+1番を番号の降順に並べます。
先手が直前に取った番号より1大きい箱を取ることが可能なら、その箱を取ります。
1小さい箱を取ることが可能なら、その箱を取ります。
どちらも不可能ならどれでもいいので取ることにします。
2m番が残っている間は相手の番号より1大きい番号を取ることが可能です。
後手が取るのは1〜m番の中の偶数番か、m+1〜2m-2番の中の偶数番です。
先手はこれらの箱を取ることはできません。
2m番が取られる前にはm番か2m-1番が取られる必要があります。
mは偶数なので、m番が取られたとすると取ったのは後手です。
1番からm番はすべてどちらかに取られています。
この時点で、後手の獲得点数−先手の獲得点数≧mです。
残りの箱は連番になっていますので、直前の相手の番号との差が1の箱を取り続けることが可能です。
差は1回につき最大1しか縮まりませんので、最悪でも引き分けになります。
2m-1番が取られたとすると、取ったのは先手です。2m-1からm+1番の箱はすべてどちらかにとられています。
後手が2m番を取ると残りの箱はすべて連番になります。
先ほどと同じ論法により、最悪でも引き分けに持ち込めます。
nが奇数の場合
n=2m+1とします。
どちらかの端から順に1,2,3,・・・とNOをつけます。
最初に先手が取るのは奇数NOの箱です。
先手が1個取ったあとは偶数個となります。
後手はそれらの中の偶数NOのすべて、または奇数NOのすべてのどちらかを取ることができます。
偶数NOの合計が最大になるように配置しておき、すべての偶数NOを取ることにします。
先手が取ることになるのは1〜m+1のm+1個です。
先手合計＝(m+1)(m+2)/2
n個の総計＝(2m+1)(2m+2)/2=(2m+1)(m+1)
先手合計×2＜総計のとき後手必勝です。
(m+1)(m+2)＜(m+1)(2m+1)
(m+1)(m-1)＞0よりm＞1
つまり、nが5以上の奇数であれば後手必勝です。
n=1の場合は、明らかに先手必勝。
n=3の場合は、引き分けです。
以上より、
n=1のときは先手必勝
n=3のときは引き分け
nが5以上の奇数のときは後手必勝
nが4の倍数のときは引き分け
nが偶数で4の倍数でないときは先手必勝
|
|
FAQ
RSS