答えはわかっているのですが、解き方がわかりません!
自然数nに対し整数を値にとる関数f(n)を次のように定める。 テーブルの上にはn個の碁石が置かれている。2人のプレーヤーAとBが交互に碁石を1個か2個とる。そして最後に碁石をとったプレーヤーが負けである。ゲームはAから始める。Bがいかなるとり方をしても、Aが最良のとり方をすれば勝てるときはf(n)=1とする。逆にAがいかなるとり方をしても、Bが最良のとり方をすれば勝てないときはf(n)=-1とする。それ以外の場合はf(n)=0とする。例えばf(1)=-1, f(2)=1である。
問い f(3) f(4) f(5) を求めよ
20 問い Σ f(n) を求めよ n=1
解答 f(3)=1 f(4)=-1 f(5)=1
20 Σ f(n) =6 n=1
ゲーム理論を使うらしいのですが、1つ1つの場合をかんがえるしかないのでしょうか?法則性や考え方などがありましたらご教授、ご鞭撻のほどよろしくお願いいたします。
|
No.63294 - 2020/02/02(Sun) 12:26:49
| ☆ Re: 2012 慶應 総合政策 第5問1 / IT | | | f(1)=-1,f(2)=1 は、容易に分かります。 自然数nについて、f(n+2)を調べます。 n+2 個から Aが2個とった場合と、1個とった場合を考えると、 f(n)=1かつf(n+1)=1ならば,Aが1個とっても2個とっても、その後Bに必勝法がありますのでf(n+2)=-1、 それ以外の場合は,Aが1個か2個かうまくとればBに必勝法がありませんのでf(n+2)=1であることが分かります。
よって、(f(1),f(2),f(3),....)=(-1,1,1,-1,1,1,-1,...)
f(20) までを使うぐらいならこれで求めればいいとおもいます。
一般の自然数nについてf(n) を求める必要があれば、nを3で割った余りで分類すれば良いです。
|
No.63295 - 2020/02/02(Sun) 13:18:36 |
| ☆ Re: 2012 慶應 総合政策 第5問1 / IT | | | 具体的な戦略は、残りの個数を3で割った余りが1になるようにとる。 ですね。
まず、nを3で割った余りが0のときAは2個とる。余りが2のときは1個とる。 (余りが1のときは、必勝法はないので1個とってBの失敗(残りの数を3で割った余りが1以外になるの)を待つ。)
その後、Bが1個とればAは2個、Bが2個とればAは1個とればいいです。
|
No.63300 - 2020/02/02(Sun) 21:03:17 |
|