薬品格納クイズ(解答)
「プログラマの数学」はまだ読んでないんですけど、この問題は「縦２マスの薬品箱(以下「棚」)」が6つ並んでいる」というくりかえし構造を見抜くところ がキーになっているのでしょう。全体を一度に考えようとするとわけがわからなくなりますが、棚ごとに考えれば一度に考えるのは4マスで済みますから。
というわけでまず一つ目の棚に薬品を入れてみます。 薬品を配置できるパターンはAA、AB、BAの3通りですね。
次に、1つ目の棚の隣に2つ目の棚を設置して、その中に薬品を入れます。このとき、手前の棚がAAならば薬品Bの発火を気にせずにAA、 AB、BAの3通り並べられますが、ABの時はBAとAA、BAの場合はABとAAの2通りしか並べられません。ややこしい。全部足すと7通り。整理する と、AAが3通り、ABが2通り、BAが2通り。 (ここで対称性を考えるとABとBAをまとめてしまえるんですけれども、それは問題を解く上で本質的じゃないテクニックなので保留)
次に3つ目の棚を置いて考えます。薬品Bが隣り合うことだけが問題なので、棚1の中がどういう配置だったかはもう気にしなくていんだな… と気づきます。考えるのは棚2の中身だけ。棚2がAAになっていればAA、AB、BAの3通り、ABの時はBAとAAの2通り、BAの場合はABとAAの 2通り。これは棚2の中身を並べたときに考えたことと似てますね。 棚2の中身がAAであるような(棚2までの)並べ方は3通りでした。これを略してAA2と表記することにしましょう。そうすると棚3の中身がAAであるよ うな並べ方(AA3)は、棚2がAAかABかBAの時に隣にAAと並べた並べ方で全てなので
AA3 = AA2 + AB2 + BA2となります。同様に、棚3の中身がABであるような並べ方は棚2がAAかBAの時に隣にABと並べた並べ方で全てなので…と考えていくと
AB3 = AA2 + BA2 BA3 = AA2 + AB2となります。今は棚2と棚3でやりましたが、今回の問題では一般的に棚kと棚k+1についてこの関係が成り立ちます。 もうここまでくれば、棚6つくらいなら手計算でも簡単に答えが求まりますね。AA1 = 1, AB1 = BA1 = 1なので、AA2 = 3, AB2 = BA2 = 2で、 AA3 = 7, AB3 = BA3 = 5…と。
ちなみに最後の棚がABかBAかによって配置の個数に差が出るはずがない(対称だから)ということに気がついていればABk = BAkなので式はもっと簡単になって
A(k+1) = A(k) + B(k) B(k+1) = 2*A(k) + B(k)となりますね。僕がやったのはこのタイプで、Pythonを使って
>>> def f((a, b)): return (a+b, 2*a+b) >>> (1, 2) (1, 2) >>> f(_) (3, 4) >>> f(_) (7, 10) >>> f(_) (17, 24) >>> f(_) (41, 58) >>> f(_) (99, 140)こんな感じで、答えは99+140=239、となります。(あってるかな？)
棚の個数が6じゃなくて、一般にkの場合はどうなるか、という話も書こうかと思ったけれども、それはまたの機会に…。