327 : 運命の部屋

3つの部屋が自動ドアをへだてて互いにつながっている。

p327_rooms_of_doom.gif

各ドアはセキュリティカードによって操作される。いったん部屋に入るとドアは自動で閉まり、セキュリティカードは二度と使えなくなる。スタート地点にあるカード発行機からカードを無制限に出すことができるが, （スタートの部屋を含む）各部屋には検知機があり、もし 3 枚を超える枚数のカードを持っていたり、カードが床に放置されていることを検知すると、全てのドアは永久的にロックされる。しかし、各部屋には保管ボックスがあり、後で使うために任意の枚数のセキュリティカードを安全に蓄えておくことができる。

単純に部屋を一つずつ通り抜けようとすると、部屋 3 に入った時点で 3 枚のカードを使い切ってしまい、永久に部屋に閉じこめられてしまうことになるだろう。

しかし、保管ボックスを利用すると脱出は可能である。例えば、1枚目のカードを用いて部屋1に入り、保管ボックスにカードを1枚置き、3枚目のカードを使って部屋を出てスタートに戻る。そしてさらに3枚のカードをカード発行機から出せば、1枚を使って部屋1に入り、先ほどボックスに置いたカードを回収する。これで再びカードは3枚になるので、残りの3つのドアを通り抜けることができる。このやり方だと、計6枚のセキュリティカードを使って3つの部屋を通り抜けることができる。

最大3枚のカードを持てるとき、計123枚のセキュリティカードを用いれば6つの部屋を通り抜けることが可能である。

一度に持つことができるカードの最大の枚数を$C$とする。

通り抜ける部屋の数を$R$とする。

一度に持てるカードの枚数が最大$C$枚のときに、$R$個の部屋を通り抜けるのにカード発行機から出す必要のあるカードの最小数を$M(C,R)$とする。

たとえば、$M(3,6)=123, M(4,6)=23$である。 また、$3 \leq C \leq 4$に対し$\sum M(C,6)=146$である。

$3 \leq C \leq 10$に対し$\sum M(C,10)=10382$である。

$3 \leq C \leq 40$に対し$\sum M(C,30)$を求めよ。