結城浩
2005年5月1日
以下のように6×2=12個の区画に分かれている薬品箱があります。 ここにA, Bという二種類の薬品を格納します。 ところが、薬品Bは縦や横に隣り合った区画に並べて格納すると発火してしまいます（斜めなら大丈夫。薬品Aは並べても大丈夫）。 このとき、発火しない格納方法は全部で何通りあるでしょうか。
薬品箱
□□□□□□ □□□□□□
発火する格納例
ＡＢＡＢＡＢ ＡＡＢＡＡＢ ＡＢＡＢＢＢ ＡＡＢＡＡＡ
発火しない格納例
ＡＢＡＢＡＢ ＡＡＢＡＡＡ ＡＡＡＡＢＡ ＢＡＡＡＡＡ ＡＡＢＡＡＡ ＢＡＡＡＢＡ
なお、この問題は 『マスター・オブ・場合の数』(p.24)によります。 これはとても楽しい本で、拙著 『プログラマの数学』の中でも何点か参考にさせてもらっています。
結城の解答
縦に、
A B
と並んでいる状態を、 (AB) と表記することにします。またたとえば、
ABA BAA
のように並んでいる状態を、 (AB-BA-AA) と表記することにします。
まずは、列数nが1, 2の場合で数えます。
n=1のときは、以下の3通り。
(AA) (AB) (BA)
n=2のときは、以下の7通り。
(AA-AA) (AA-AB) (AA-BA) (AB-AA) (AB-BA) (BA-AA) (BA-AB)
n=3のときは、以下の17通り。
(AA-AA-AA) (AA-AA-AB) (AA-AA-BA) (AA-AB-AA) (AA-AB-BA) (AA-BA-AA) (AA-BA-AB) (AB-AA-AA) (AB-AA-AB) (AB-AA-BA) (AB-BA-AA) (AB-BA-AB) (BA-AA-AA) (BA-AA-AB) (BA-AA-BA) (BA-AB-AA) (BA-AB-BA)
ここまで作ってくると、次のことがわかります。
n列で、右端がAAになる場合の数をa(n), 右端がABになる場合の数をb(n), 右端がBAになる場合の数をc(n)と置くことにします。 すると、上で調べたことから、次のことがわかります(n >= 1)。
a(1) = 1 b(1) = 1 c(1) = 1 a(n+1) = a(n) + b(n) + c(n) b(n+1) = a(n) + c(n) c(n+1) = a(n) + b(n)
対称性からb(n)=c(n)が成り立ちます。式を整理すると、
a(n+1) = a(n) + 2b(n) b(n+1) = a(n) + b(n)
求める値はa(6) + b(6) + c(6)なので、あとは順番に計算します。
a(6) + b(6) + c(6) = a(6) + 2b(6)
= (a(5) + 2b(5)) + 2(a(5) + b(5))
= 3a(5) + 4b(5)
= 3(a(4) + 2b(4)) + 4(a(4) + b(4))
= 7a(4) + 10b(4)
= 7(a(3) + 2b(3)) + 10(a(3) + b(3))
= 17a(3) + 24b(3)
= 17(a(2) + 2b(2)) + 24(a(2) + b(2))
= 41a(2) + 58b(2)
= 41(a(1) + 2b(1)) + 58(a(1) + b(1))
= 99a(1) + 140b(1)
= 99 + 140
= 239
答え：239通り
以下に、読者さんからの解答から何通か紹介します（すべてではありません）。 順番はほぼ到着順です。 みなさん、ご解答ありがとうございます。
ぞりおさんの答え
はじめまして。 クイズやってみました。
薬品箱の状態を12ビットで表します。 あらかじめ爆発するケースを配列で持っておきます。 0から0xFFFFFFまでの数を、爆発するケースと比較して 判定しました。 答えは239通りでした。
西尾泰和さんの答え
notogawaさんの答え
上下にAA,AB,BAと並ぶパターンをそれぞれα、β、γ、とする
βとγは連続して並ぶことの無い並べ方がここでは適当である
（例えば左から）順番にα、β、γを適当に並べていって
n番目にα、β、γが配置される並べ方の数をそれぞれ
α_n、β_n、γ_nとするとα_1=β_1=γ_1=1で、
α_{n+1}=α_n+β_n+γ_n (αはどの後でもOK)
β_{n+1}=α_n +γ_n (ββは不適当)
γ_{n+1}=α_n+β_n (γγは不適当)
であり、このとき欲しい解はα_6+β_6+γ_6=α_7である
簡単のためS_n=α_n、T_n=β_n+γ_nとするとS_1=1、T_1=2で
S_{n+1}=S_n+T_n
T_{n+1}=2S_n+T_n
となりこれらよりSについての三項間漸化式は
S_{n+2}=2S_{n+1}+S_n (S_1=1, S_2=S_1+T_1=3)
この後S_nの一般項を求めてもいいが
ルートとか出てきてかえって面倒で、
欲しい値はα_7=S_7なので順番に
S_3=2S_2+S_1=7
S_4=2S_3+S_2=17
S_5=2S_4+S_3=41
S_6=2S_5+S_4=99
S_7=2S_6+S_5=239
以上より239通り
ishigakiさんの解答
=comment
こんばんは。何度かPerlクイズなどでメールを差し上げた
石垣です。ぐずぐずしているうちに答えが出てしまいまし
たが、上下左右の反転チェックまで考慮したものはないよ
うでしたので送ってみます。ちなみに上下左右固定したも
のは239通り、反転したものを同一とみなすと66通りでした。
以下、チェックに利用したスクリプトのソースです。
=cut
#!/usr/bin/perl
# ここでは隣接すると発火してしまうＢをどのように
# 置くかだけが問題なので、まずは横の列に注目して、
# Ｂが隣接しない組み合わせを抽出します。ビット演
# 算で１マス分シフトしたとき、ビット積が０になれば
# 隣接したＢはない、と判断できます。
my $col = 6; # 横の列数
my $max = 2 ** $col;
my @row = ();
for(my $ct = 0; $ct < $max; $ct++) {
my $shifted = $ct >> 1;
next if $shifted & $ct;
# ビット演算をクリアした組み合わせを保存
push @row, $ct;
}
# 今度は縦の列について考えます。横の列の場合と同
# 様に、上下のビット積が０になれば隣接したＢはない
# と判断できます。
my $total = 0;
my %exists = ();
foreach my $top (@row) {
foreach my $bottom (@row) {
# 上下のビット積が０でなければ無視します
next if $top & $bottom;
# 以下の五行は参考までに。
# コメントを外すと、上下左右を反転したと
# きに同じ形になる組み合わせを排除します
# next if $exists{ bin($top).bin($bottom) };
# $exists{ bin($top).bin($bottom) } = 1;
# $exists{ bin($bottom).bin($top) } = 1;
# $exists{ rev($top).rev($bottom) } = 1;
# $exists{ rev($bottom).rev($top) } = 1;
$total++;
}
}
print "total: $total\n";
# 以下、サブルーチン
# bin は $col 桁数の２進数を、rev の方は bin で得ら
# れた２進数の左右反転したものを返します。
sub bin { substr(unpack('B16',pack('n',shift)),-1 * $col); }
sub rev { join('',reverse(split('',sprintf('%s',bin(shift))))); }