[答442] 立方体の辺上の移動
[答442] 立方体の辺上の移動
図のような立方体があって、最初に点Aにある点Pは1回の移動で隣の点に移る。
11回の移動の後、点Pが点Gにある経路は何通り?
[解答1] 反車(hensha)さんの解答より
図のように、立方体をかいて地道に経路の数を順に求めると、44286 通りです。
[解答2]
2k回の移動で、点Pが点Aにある経路をAk通り、点C(F,Hでも同じ)にある経路をCk通り、とすると、
A1=3, C1=2 ,Ak+1=3Ak+6Ck ……(1) ,Ck+1=2Ak+7Ck ……(2)
(1),(2)より、Ak+1+3Ck+1=9(Ak+3Ck) ,Ak+3Ck=(A1+3C1)・9k-1 ,Ak+3Ck=32k ……(3)
(1),(2)より、Ak+1-Ck+1=Ak-Ck ,Ak-Ck=A1-C1 ,Ak-Ck=1 ……(4)
(3),(4)より、Ak=(32k+3)/4, Ck=(32k-1)/4 です。
n(偶数)回の移動で、
点Pが点Aにある経路は、(3n+3)/4 通り 、
点C(F,Hでも同じ)にある経路は、(3n-1)/4 通り、
n(奇数)回の移動で、
点Pが点Gにある経路は、3・(3n-1-1)/4=(3n-3)/4 通り、
点B(D,Eでも同じ)にある経路は、(3n-1+3)/4+2・(3n-1-1)/4=(3n+1)/4 通り、
です。
本題の場合は、(3n-3)/4 に n=11 を代入して、(311-3)/4=44286 通りです。
[参考] n回の移動の仕方は、3n 通りありますが、上の結果は、
偶数回の移動で行く、A,C,F,Hのうち、出発点Aは他より1回多く、
奇数回の移動で行く、B,D,E,Gのうち、出発点より一番遠いGは他より1回少ない、
と、いうことを示しています。
.