[答442] 立方体の辺上の移動

[答442] 立方体の辺上の移動


　図のような立方体があって、最初に点Ａにある点Ｐは１回の移動で隣の点に移る。

　11回の移動の後、点Ｐが点Ｇにある経路は何通り？


[解答1] 反車(hensha)さんの解答より

　図のように、立方体をかいて地道に経路の数を順に求めると、44286 通りです。


[解答2]

　2k回の移動で、点Ｐが点Ａにある経路をA_k通り、点Ｃ(Ｆ,Ｈでも同じ)にある経路をC_k通り、とすると、

　A₁＝3, C₁＝2 ，A_k+1＝3A_k＋6C_k ……(1) ，C_k+1＝2A_k＋7C_k ……(2)

　(1),(2)より、A_k+1＋3C_k+1＝9(A_k＋3C_k) ，A_k＋3C_k＝(A₁＋3C₁)･9^k-1 ，A_k＋3C_k＝3^2k ……(3)

　(1),(2)より、A_k+1－C_k+1＝A_k－C_k ，A_k－C_k＝A₁－C₁ ，A_k－C_k＝1 ……(4)

　(3),(4)より、A_k＝(3^2k＋3)/4, C_k＝(3^2k－1)/4 です。

　ｎ(偶数)回の移動で、

　点Ｐが点Ａにある経路は、(3ⁿ＋3)/4 通り 、

　点Ｃ(Ｆ,Ｈでも同じ)にある経路は、(3ⁿ－1)/4 通り、

　ｎ(奇数)回の移動で、

　点Ｐが点Ｇにある経路は、3･(3^n-1－1)/4＝(3ⁿ－3)/4 通り、

　点Ｂ(Ｄ,Ｅでも同じ)にある経路は、(3^n-1＋3)/4＋2･(3^n-1－1)/4＝(3ⁿ＋1)/4 通り、

　です。

　本題の場合は、(3ⁿ－3)/4 に n＝11 を代入して、(3¹¹－3)/4＝44286 通りです。


[参考] ｎ回の移動の仕方は、3ⁿ 通りありますが、上の結果は、

　偶数回の移動で行く、Ａ,Ｃ,Ｆ,Ｈのうち、出発点Ａは他より１回多く、

　奇数回の移動で行く、Ｂ,Ｄ,Ｅ,Ｇのうち、出発点より一番遠いＧは他より１回少ない、

　と、いうことを示しています。

.