MathLabs

第5問

nn を正の整数とする。(n+1)×n(n+1)\times n 型に並んだ n(n+1)n(n+1) 個の部屋がある。隣り合う二部屋の間には扉が一つある。扉の部分集合を選んで施錠し、次を満たす二部屋 SS、GG が存在するようにする方法の数を求めよ。 (i) SS は第 1 行、GG は第 (n+1)(n+1) 行にある。 (ii) 施錠されていない扉のみを使って SS から GG に到達できる。
ステップ 5/5: 自由な扉を戻して仕上げる
前のステップ次のステップ
answer=2 n2+(n−1)2−1⋅22(n−1)=22n2−2\text{answer}=2^{\,n^2+(n-1)^2-1}\cdot 2^{2(n-1)}=2^{2n^2-2}
詳しい解説

G\mathcal{G} の辺上の到達可能な施錠のしかた 2 n2+(n−1)2−12^{\,n^2+(n-1)^2-1} 通りそれぞれは、第 1 行と最終行の内部の扉の施錠のしかた 22(n−1)2^{2(n-1)} 通り（ステップ1）と自由に組み合わせられる。なぜならそれらの扉は AA と BB が連結かどうかに影響しないからである。これにより、第 1 行のある部屋から最終行のある部屋に到達できるように扉を施錠する方法は合計で 22n2−22^{2n^2-2} 通りとなる。