FC2ブログ

Welcome to my blog

[答532] ルークの4回の移動

ヤドカリ

ヤドカリ



[答532] ルークの4回の移動


 チェスのルーク(rook)は、将棋の飛車のように、1手(1回の移動)で、縦横にいくつでも移動できます。

 いま、図のように A1 の位置にある rook が4手の移動で初めて H8 に移動する方法は何通り?


[解答1]

 右の図で、A1 から2手後にどこにあるかによって場合分けします。

 ■のうちの1ヶ所を限定すると、

  A1 から2手後行く方法は2通り、その2手後に H8 に行く方法は2通りの 2・2=4 通り。

 ▲のうちの1ヶ所を限定すると、

  A1 から2手後行く方法は6通り、その2手後に H8 に行く方法は2通りの 6・2=12 通り。

 ▼のうちの1ヶ所を限定すると、

  A1 から2手後行く方法は2通り、その2手後に H8 に行く方法は6通りの 2・6=12 通り。

 ◆のうちの1ヶ所を限定すると、

  A1 から2手後行く方法は6通り、その2手後に H8 に行く方法は6通りの 6・6=36 通り。

 2手後に A1 に戻る方法は 14通り、その2手後に H8 に行く方法は2通りの 14・2=28 通り。

 従って、36・4+12・12+12・12+2・36+28=144+144+144+72+28=532 通りです。


[解答2] uch*n*anさんのコメントより

 n 手で移動する場合の数は,対称性より,A1(もとの位置)を an 通り,▲のマスを bn 通り,◆のマスを cn 通り,

 ▼のマスを dn 通り,■のマスを en 通り,H8(★)を sn 通り,とおけて,次の漸化式を満たします。

 an+1=12bn+2cn ,bn+1=an+5bn+cn+dn+6en ,cn+1=an+6bn+6dn

 dn+1=bn+cn+5dn+6en ,en+1=2bn+2dn+10en ,sn+1=2cn+12dn

 a0=1,b0=c0=d0=e0=0

 そこで,

 a1=0,b1=1,c1=1,d1=0,e1=0,(s1=0)

 a2=14,b2=6,c2=6,d2=2,e2=2,(s2=2)

 a3=84,b3=64,c3=62,d3=34,e3=36,(s3=36)

 s4=532

 つまり,532 通り,になります。


[解答3]

 縦の移動、横の移動に分けて考えます。

 縦横の移動が2回ずつの場合、

  縦の移動は 1→○→8 の○に適するのが 2~7 の6通り、

  横の移動も A→○→H の○に適するのが B~G の6通り、

  縦縦横横の並べ方が 4!/(2!・2!)=6 通り、よって、6・6・6=216 通りです。

 縦の移動が3回・横の移動が1回の場合、

  縦の移動は 1→○→○→8 の前の○に適するのは 1以外の7通り、

  後の○に適するのは 前の○と8以外の6通り、ただし前の○が8の場合は1通り増の7通り、

  横の移動は A→H に限定されます。

  縦縦縦横の並べ方が 4!/3!=4 通り、

  よって、(7・6+1)・1・4=172 通りです。

 縦の移動が1回・横の移動が3回の場合も同様に、172 通りです。

 以上のうち、2手後に H8 に行き、その2手後にまた H8 に行く方法は 2・14=28 通りです。

 従って、216+172・2-28=532 通りです。


[参考] たけちゃんさんのコメントより (H8へn手ではじめて至る場合の数)

 途中、H8 に行かずに、

 n手で◆▼のいずれかに至る場合の数を bn ,A1▲■のいずれかに至る場合の数を cn とすれば、

 b0=0 ,c0=1 ,bn+1=6bn+2cn ,cn+1=7bn+12cn です。

 pbn+1+cn+1=(6p+7)bn+(2p+12)cn となり、

 6p+7=p(2p+12) を満たす p の値は p=(-3±√23)/2 で、

 このとき、pbn+1+cn+1=(2p+12)(pbn+cn) になります。

 よって、pbn+cn=(pb0+c0)(2p+12)n=(2p+12)n 、p=(-3±√23)/2 だから、

 {(-3+√23)/2}bn+cn=(9+√23)n ,{(-3-√23)/2}bn+cn=(9-√23)n です。

 辺々減じて、(√23)bn=(9+√23)n-(9-√23)n 、bn={(9+√23)n-(9-√23)n}/√23 です。

 n手ではじめて H8 に至る場合の数は、bn-1={(9+√23)n-1-(9-√23)n-1}/√23 です。

.

スポンサーサイト



Comments 20

There are no comments yet.
uch*n*an  
No title

これは,後戻りなども考慮し数え間違いに注意して地道に数えれば何とかなる問題でした。
ただ,要領よく数えないとこんがらがって難しいかも知れませんね。
私の解法は[解答2]でした。ただ,その前に[解答1]で数えていました。
一般化できないかな,と思って漸化式を組んだのですが,
そのときは a(n) ~ e(n) すべてを求めようとして複雑になり,[解答2]になりました。
たけちゃんさんに先を越されてしまいましたが,私の場合の H8 に行くのは s(n) なので,
これならばその後に解けていて同じ結果になっています。一応,書いておきましょう。
漸化式を解くことに頭が行っていたので,[解答3]は気付きませんでした。
なるほど,この解法もいいですね。ただ,tsuyoshik1942さんのご指摘は正しそう (^^;

uch*n*an  
No title

n 回目で初めて H8 に到達する場合の数 s(n) を求めます。
漸化式は,[解答2]と同じで,
a(n+1) = 12 * b(n) + 2 * c(n)
b(n+1) = a(n) + 5 * b(n) + c(n) + d(n) + 6 * e(n)
c(n+1) = a(n) + 6 * b(n) + 6 * d(n)
d(n+1) = b(n) + c(n) + 5 * d(n) + 6 * e(n)
e(n+1) = 2 * b(n) + 2 * d(n) + 10 * e(n)
s(n+1) = 2 * c(n) + 12 * d(n)
a(0) = 1,b(0) = c(0) = d(0) = e(0) = 0
ただし,s(n) は n >= 1 で意味があり,s(1) = 0,s(2) = 2 です。後は計算だけ。

uch*n*an  
No title

s(n+2)
= 2 * c(n+1) + 12 * d(n+1)
= 2 * (a(n) + 6 * b(n) + 6 * d(n)) + 12 * (b(n) + c(n) + 5 * d(n) + 6 * e(n))
= 2 * a(n) + 24 * b(n) + 12 * c(n) + 72 * d(n) + 72 * e(n)
= 6 * (2 * c(n) + 12 * d(n)) + 2 * a(n) + 24 * b(n) + 72 * e(n)
= 6 * s(n+1)
+ 2 * (12 * b(n-1) + 2 * c(n-1))
+ 24 * (a(n-1) + 5 * b(n-1) + c(n-1) + d(n-1) + 6 * e(n-1))
+ 72 * (2 * b(n-1) + 2 * d(n-1) + 10 * e(n-1))
= 6 * s(n+1) + 24 * a(n-1) + 288 * b(n-1) + 28 * c(n-1) + 168 * d(n-1) + 864 * e(n-1)

uch*n*an  
No title

= 6 * s(n+1)
+ 24 * (a(n-1) + 6 * b(n-1) + 6 * d(n-1)) + 144 * (b(n-1) + c(n-1) + 5 * d(n-1) + 6 * e(n-1))
- 58 * (2 * c(n-1) + 12 * d(n-1))
= 6 * s(n+1) + 12 * (2 * c(n) + 12 * d(n)) - 58 * (2 * c(n-1) + 12 * d(n-1))
= 18 * s(n+1) - 58 * s(n)
s(n+2) - 18 * s(n+1) + 58 * s(n) = 0
ただし,s(1) = 0,s(2) = 2,です。

uch*n*an  
No title

ここで,この3項漸化式は,その一般論により,2次方程式,
x^2 - 18x + 58 = 0
の解,x = 9 ± √23,を使って,p,q を定数として,
s(n) = p * (9 + √23)^(n-1) - q * (9 - √23)^(n-1)
と書けます。そこで,s(1) = 0,s(2) = 2,より,
s(n) = ((9 + √23)^(n-1) - (9 - √23)^(n-1))/√23
になります。

さっちゃんこ  
No title

こんにちは
花キリンが綺麗に咲いていますね
花弁に特徴のある花ですね

ナイス☆

スモークマン  
No title

グーテンターク ^^
以前似た問題があったよな気がする...^^...?
さいしょ、元に戻るのもありと気づけず...^^;
あとは、数えたようなものですが...7-7が続く場合を引いて求めました ^^ Orz~

ヤドカリ  
No title

たけちゃんさん、コメントを有難う御座います。
なるほど、見事な解き方ですね。
漸化式の解き方を添えて、私なりに[参考]としてまとめさせて頂きました。

ヤドカリ  
No title

古い人さん、早速のコメントとナイス!を有難う御座います。
ハナキリンはそれほど華やかな花ではありませんが、味わいがあります。
目立たない所でそっと咲いてくれていても癒されます。

ヤドカリ  
No title

アキチャンさん、早速のコメントとナイス!を有難う御座います。
ハナキリンは単純な形ですが、可愛いですね。
なお、お分かりかと思いますが、問題図はチェス盤のつもりです。

ヤドカリ  
No title

tsuyoshik1942さん、早速のコメントとミスの指摘を有難う御座います。
途中H8に至る場合が縦横2回ずつと勘違いして引いてしまいましたが、
全体から引くように訂正いたしました。

ヤドカリ  
No title

ニリンソウさん、早速のコメントとナイス!を有難う御座います。
割りにたくさん咲いており、背景を気にせず、近づいて撮りました。
おもしろい花ですね。

ヤドカリ  
No title

yasukoさん、早速のコメントとナイス!を有難う御座います。
このハナキリンは花の文化園の温室で撮りました。
サボテンがたくさん植えられている所です。
いつ行っても咲いてくれているのがうれしい花です。

ヤドカリ  
No title

uch*n*anさん、漸化式の解き方を有難う御座います。
貴殿の解答を見て私も解ければいいなと思ったのですが、
文字の多さに嫌気がさしました。
よく解かれたものだと……、驚きです。

ヤドカリ  
No title

さっちゃんこさん、コメントとナイス!を有難う御座います。
ハナキリンの花弁の形は単純でいいですね。
綺麗に咲いていました。

ヤドカリ  
No title

スモークマンさん、コメントを有難う御座います。
> 以前似た問題があったよな気がする...^^...?
http://blogs.yahoo.co.jp/oka_yadokary/31133994.html
のことでしょうか?
手数が決まっていますので、この問題よりは簡単だと思います。

ひとりしずか  
No title

ハナキリン、ピンク色可愛いですね~

ナイス!

ヤドカリ  
No title

ひとりしずかさん、コメントとナイス!を有難う御座います。
ハナキリンの単純な形の花、仰る通り、可愛いです。

樹☆  
No title

そうそう・・このお花です。ふだん見るのは。。
ナイスです。

ヤドカリ  
No title

樹ちゃん、コメントとナイス!を有難う御座います。
こちらがよく見るハナキリンですね。