■

準ひきこもり的大学生活を送っていた

人との関わりを避け、ネットの文章を漫然と眺めるだけの日々。

気がついたら、もともと不得意だった日常会話が更にできなくなっていた。

反射神経も抽象的思考力も記憶力も、すっかり無くなっていた。

焦って本を読んでみた

パソコン以外で文章を読むのは久しぶり。

前頭葉機能とか、ワーキングメモリとか。そんなものが低下しているらしい。

神経衰弱がリハビリに効くという

ひとり用神経衰弱(http://homepage3.nifty.com/puzzlehouse/kg30/kg30.html Javaプラグイン必要)をプレイしてみた。

デフォルトの14枚だと全くうまくいかない。8枚くらいが限界だ。

何度も何度もプレイするうちに、大体同じ回数でゲームが終了することに気づく。

そこで考えたこと。

最も優秀な神経衰弱プレイヤーは

どれだけカードの枚数が増えようと、1度でもめくったカードの数字と場所の組み合わせを決して忘れない。

そんな人が、一人神経衰弱で最悪でもこれだけのターン数あれば1回のゲームを確実に終わらせることができる、

そういうターン数を「最悪ターン数」と呼ぶことにしよう。これを割り出したい。

簡単のため、互いに相異なるn種類の数字が書かれたカード2枚ずつ、

合計2n枚のカードからなる神経衰弱ゲームについて考える。

このときの最悪ターン数をF(n)とする(ただしn≧2)。

まず

n≦2kとなる最小のkについて、

kターン目まで一度たりともカードを取り除くことに成功できなかった場合について考える。

このとき、(k+1)ターン目以降では取り除くことに失敗することはありえない。

kターン目までに引かなかったカードを1枚引けば、

このカードと同じ数が書かれたカードをkターン目までに1回引いており、

その位置と場所をプレイヤーは記憶しているのだから、間違えずにそれを引けばよい。

よって連続で外れ続けるターン数は最も不運な場合でもk(=int((n+1)/2))ターンであり、

その後はnターンでゲームを終了させることが出来る。

このときの合計ターン数はint((n+1)/2)+nだ。

実は

F(n)はint((n+1)/2)+nに一致する。

そのことを数学的帰納法により示す。

n=2のとき

F(2)=3であり、これはint((2+1)/2)+2に一致する。

次に

F(n-1)=int(n/2)+(n-1)となる任意の3以上のnについてF(n)=int((n+1)/2)+nになることを示す。

そのためには以下の二通りの場合について考えれば必要十分だ。

(a)

1≦i≦int((n+1)/2)なるiが存在してiターン目に同じ種類の2枚のカードを引く場合、

この条件下での最悪ターン数はF(n-1)+1に一致する。

iターン目に引いたカードを除いた2(n-1)枚のカードについて

最悪ターン数となるようなカードの引き方を考え、

そのどこかにまぐれ当たりのiターン目を挿入したものが

(a)のときの最悪ターン数となるようなカードの引き方に一致するからだ。

(b)

int((n+1)/2)回までに一回も成功しない場合、

この条件下での最悪ターン数は先に述べた通りint((n+1)/2)+nに一致する。

従って

F(n)はF(n-1)+1(=int(n/2)+n)とint((n+1)/2)+nのうち小さくない方、つまりint((n+1)/2)+nに一致する。

以上の議論より

F(n)=int((n+1)/2)+nが任意の2以上の自然数nについて成立する。

Permalink | 記事への反応(1) | 18:23

ツイートシェア