|
図のような立方体があって、最初に点Aにある点Pは1回の移動で隣の点に移る。
11回の移動の後、点Pが点Gにある経路は何通り? 解答
図のように、立方体をかいて地道に経路の数を順に求めると、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回少ない、 と、いうことを示しています。 *わたしゃ試行錯誤の結果...^^;...
0:(000)-1:(100,010,001)-2(101,110,011)-3:(111)
つまり...0→1, 1→(0,2), 2→(1,3), 3→2 の動きしかない... 0-1-(0,2)-((1),(1,3))-((0,2),((0,2),2))...4回目までの点の位置...
f(4)=0(3^2+3*2^2)+2(3^2*2+3*2^3+3^2*2) =0(21)+2(60) (0,2)から2回目に(0,2) になる... g(2)=0(0(3),2(6))+2(0(2),2(7))...なので... f(6)=(0(21)(0(3),2(6))+2(60)(0(2),2(7)) =(0(63+120)+2(126+420)) f(8)=0(183)(0(3),2(6))+2(546)(0(2),2(7)) =0(549+1092),2(1098+3822) =0(1641)+2(4920) f(10)=0(1641)(0(3),2(6))+2(4920)(0(2),2(7)) f(10) のときの 2 の場合を求めればいいので... 1641*6+4920*7=44286 |

- >
- Yahoo!サービス
- >
- Yahoo!ブログ
- >
- 練習用


