4888：将棋盤(nxn)の飛車の動かし方...

問題4888(友人問)

n×nの将棋盤がある。ここでは、飛車はその盤上で右または上に好きなだけ進むことが出来る。

このとき、飛車を1の1からnのnまで進める動かし方は9^n通り以下であることを示せ。

（方向を変えるとき以外でも止めてよい）

解答

・わたしの

これは簡単じゃん...?

各点で飛車の動きは上か右にしか行けない...2通り

点はすべてで...上n個と右n個で合計2n個の点を通る...

つまり...2^(2n) < 3^(2n)=9^n

以下じゃなくって...それよりもずっと少ないはず...^^;...?

再考...2012.02.25

2n個の中でスタートとゴール以外の場所で停まる場合も別の動かし方とすると...

上・右それぞれ n個のうちで...1~(n-1)回停まれるので...

(x+x^2+x^3+...+x^(n-1))^(n-1) から...重複を許してx^(n-1) になるとき...

(x+x^2+x^3+...+x^(n-1))^(-1)n を展開して x^(n-1) の係数を求める

同様に...

(y+y^2+y^3+...+y^(n-1))^(n-1) を展開して y^(n-1) の係数を求める

それらの積の２倍でいいはず...?

求め方がまだよくわからない...

再考...2012/02.26

よく考えたら...上、右へのそれぞれ(スタートとゴールを除いた)n-2の点で上/右/停まるの3種類選べる...(3^(n-2))^2...スタート時は2通り...ゴールは1通り

けっきょく...

2*(3^(n-2))^2=2*9^(n-2) < 9^n

でいいのかな...?

・友人からのもの

解法1...

飛車の通り道の各マス目(始点、終点を含めない2n-3個のマス目)における飛車の動き方は次の3通りしかない。

1) 止まらず通過する

2) 止まって右に行く

3) 止まって上に行く

したがって、始点において右に行くのか上に行くのかの2通りあることに注意すると、

2*3^(2n-3) ( < 9^n )通りである。

解法2...

飛車を1の1から kの l まで進める動かし方の個数を f(k,l) とおく。飛車の最後の移動の仕方のよって場合分けをすると、

f(k,l)=f(k,l-1)+...+f(k,l)+f(k-1,l)+...+f(1,l)　・・・(1)

ただし、f(1,l)=1, f(0,＊)=f(＊,0)=0

任意の k,l に対し

f(k,l) ≦ 3^(k+1)・・・(2)

であることを示せば、f(n,n) ≦ 3^(2n) = 9^n となり題意は示される。

k+l による帰納法で示す。

k+l=2 のとき明らかに成り立つ。

k+l < m のとき常に(2) が成り立つとすると、k+l=m のとき (1) 式より

f(k,l) ≦ 2*(3^(m-1)+...+1) = 2*3^(m-1)/(3-1) < 3^m = 3^(k+1)

よって任意の m について (2) が成立。

解法3...

最初、飛車を右に動かしたときの場合の数を2倍する。

(i) 飛車が上に k+1 回、右に k 回向きを変えるとき

いつ向きを変えるかを上と右でわけて考えると、向きを変える場所の取り方は ((n-2)Ck)^2 通りある。向きを変えないでマス目で止まるかどうかも考えると ((n-2)Ck*2^(n-2-k))^2 通りである。

(ii) 飛車が上に k 回、右に k 回向きを変えるとき

(i) と同様に考えて

(n-2)Ck*2^(n-2-k) x (n-2)C*2^(n-2-(k-1))

したがって、求める場合の数は

S(n)=2Σ[0~(n-2)] ((n-2)Ck*2^(n-2-k))^2+2Σ[1~(n-2)] ((n-2)Ck*2^(n-2-k) * (n-2)C(n-1)*2^(n-2-k+1)

≦ 2(Σ [0~(n-2)] ((n-2)Ck*2^(n-2-m))^2　　(展開して比較)

= 2*{(1+2)^(n-2)}^2 ≦ 9^n

解3より...

S(n) > Σ[0~(n-2)] ((n-2)Ck*2^k)^2 ≧ (1/(n-1))*(Σ[0~(n-2)] (n-2)Ck*2^k)^2 = (1/81)*(9^n/(n-1)

(コーシーシュワルツの不等式)

より、S(n) ≦ a^n を満たす最小の a は 9 である。 

[スモークマン]

＞鍵コメさまへ ^^
そっか...^^;
ご指摘グラッチェ...Orz...
再考します〜m(_ _)m〜

[スモークマン]

↑
再考してるけど...いまだわからず...^^;...

[スモークマン]

↑
再考^2...^^;...?

[スモークマン]

＞鍵コメ様へ ^^
等号が成り立つときってのがわかりませんねぇ...^^;...
最短は2回...あとは...2nCn=2n*(2n-1)*...*(2n-n+1)/{n*(n-1)*...*1)
通りになりますよねぇ...?
それらの計算スタートは1、ゴール手前も1、右端と、上の端の場合も1通りしか考えられないけど...計算できない...^^;...
友人からの解答を待ちたいと思います...Orz〜v

[スモークマン]

↑
友人からの解答をアップします ^^