FC2ブログ

Welcome to my blog

[答470] ルークの移動

ヤドカリ

ヤドカリ



[答470] ルークの移動


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

 いま、図のように A1 の位置にある rook を 右か上だけに動かして H8 に移動する方法は何通り?

 ( A1 から H8 へは、最少で 2手、最多で 14手 かけて移動することにになります。)


[解答1]

 B1,C1,D1,E1,F1,G1,H1 への移動は途中の各マスで止まるか止まらないかの2通りですので、

 移動の仕方は 1,2,4,8,16,32,64 通り、A2 ~ A8 への移動も同じで、この数を書き込みます。

 B2 への移動は B1,A2 からの移動だから、この数を加えて書き込みます。

 C2 への移動は C1,A2,B2 からの移動だから、この数を加えて書き込みます。

 D2 への移動は D1,A2,B2,C2 からの移動だから、この数を加えて書き込みます。

 同様にして、E2,F2,G2,H2 に何通りかを書き込み、B3 ~ B8 への移動も同じで、この数を書き込みます。

 以下、同様に、

 C3 ~ H3 ,C4 ~ C8 ,D4 ~ H4 ,D5 ~ D8 ,E5 ~ H5 ,E6 ~ E8 ,F6 ~ H6 ,F7 ~ F8 ,……

 と、H8 まで書き込めば、動かす方法は 470010 通りであることが分かります。


[解答2]

 まず、途中で止まる行を 2,3,4,5,6,7 から m個、途中で止まる列を B,C,D,E,F,G から n個

 を選び、上へ m+1 回,右へ n+1 回の移動で、H8 に達することになります。

 従って、6m6nm+n+2m+1 (0≦m≦6,0≦n≦6) の総和を求めることになります。

 m+n+2m+1 は、選んだ m+n 個と x,y を付加したものから m+1 個を選ぶ場合の数です。

 例えば、2,3,4,5,B,C,D,x,y からは5個を選ぶことになりますが、

 (1) 2,3,4,5,6,7 から (3,4)、 B,C,D,E,F,G から (B,D) のように同数個を選んで

   残り 2,5,6,7,C,E,F,G から 2,5,C を選ぶと、2,3,4,5,B,C,D を選んだことになり、

   行は 3,4 以外を、列は B,D を 書き出せば、2,5,B,D 、これに x,y のうちどちらかを加えれば、

   x,y のうち1つだけを含む5個の選び方になります。

 (2) 2,3,4,5,6,7 から (3,4)、 B,C,D,E,F,G から (D) のように行を1個多く選んで

   残り 2,5,6,7,B,C,E,F,G から 2,5,B,C を選ぶと、2,3,4,5,B,C,D を選んだことになり、

   行は 3,4 以外を、列は D を 書き出せば、2,5,D 、これに x,y の両方を加えれば、

   x,y の両方を含む5個の選び方になります。

 (3) 2,3,4,5,6,7 から (4)、 B,C,D,E,F,G から (B,D) のように列を1個多く選んで

   残り 2,3,5,6,7,C,E,F,G から 2,3,5,C を選ぶと、2,3,4,5,B,C,D を選んだことになり、

   行は 4 以外を、列は B,D を 書き出せば、2,3,5,B,D 、

   これは、x,y のどちらも含まない5個の選び方になります。

 (1)のように行と列から同数個選び、残りから任意に選ぶような選び方は、6k6k・212-2k (0≦k≦6) 通りで、

  (2x+1)6 の展開式における x6-k の係数は 6k・26-k 、(2+x)6 の展開式における xk の係数は 6k・26-k

  よって、 {(2x+1)(2+x)}6 の展開式における x6 の係数になります。

 (2)のように行を1個多く選び、残りから任意に選ぶような選び方は、6k+16k・211-2k (0≦k≦5) 通りで、

  (2x+1)6 の展開式における x5-k の係数は 6k+1・25-k 、(2+x)6 の展開式における xk の係数は 6k・26-k

  よって、 {(2x+1)(2+x)}6 の展開式における x5 の係数になります。

 (3)のように列を1個多く選び、残りから任意に選ぶような選び方は、6k+16k・211-2k (0≦k≦5) 通りで、

  (2)と同数です。

 従って、(2x2+5x+2)6 の展開式における x6 の係数と x5 の係数の和の2倍が答です。

 展開したときの一般項は {6!/(a!b!c!)}・(2x2)a(5x)b・2c (a+b+c=6) だから、

 x の指数は 2a+b=5,6 で、係数は {6!/(a!b!c!)}・2a・5b・2c

 (a,b,c)=(0,5,1),(1,3,2),(2,1,3),(0,6,0),(1,4,1),(2,2,2),(3,0,3) 、

 {6!/(a!b!c!)}・2a・5b・2c=37500,60000,9600,15625,75000,36000,1280 となり、

 その和の2倍は 2(37500+60000+9600+15625+75000+36000+1280)=470010 です。


[参考]

 f(x)=(2x2+5x+2)n の xn+1,xn-1 の係数を bn ,xn の係数を an-bn とします。

 f(x) の xn+1 の係数は bn ,xn の係数は an-bn で、

 f'(x) の xn の係数は (n+1)bn ,xn-1 の係数は n(an-bn) です。

 また、f'(x)=n(2x2+5x+2)n-1(4x+5) で、

 (2x2+5x+2)n-1 の xn,xn-2 の係数は bn-1 ,xn-1 の係数は an-1-bn-1 だから、

 xn の係数は n{4(an-1-bn-1)+5bn-1} ,xn-1 の係数は n{4bn-1+5(an-1-bn-1)} です。

 よって、(n+1)bn=n(4an-1+bn-1) ……(1) 、n(an-bn)=n(5an-1-bn-1) ……(2) 、

 (2)より、an-5an-1=bn-bn-1

 (1)+(2) より、nan+bn=9nan-1 従って、(n-1)an-1+bn-1=9(n-1)an-2

 辺々減じて、nan-(n-1)an-1+(an-5an-1)=9nan-1-9(n-1)an-2

 an={(10n+4)an-1-9(n-1)an-2}/(n+1) になります。

 n×n の盤の左下隅から右上隅への移動の仕方を Rn 通りとすれば、Rn=2an-2 になります。

 R2=2a0=2 ,Rn+2=2an=2{(10n+4)an-1-9(n-1)an-2}/(n+1)={(10n+4)Rn+1-9(n-1)Rn}/(n+1) 、

 この漸化式で順に計算すると、

 R3=14R2/2=14 ,R4=(24R3-9R2)/3=106 ,R5=(34R4-18R3)/4=838 ,R6=(44R5-27R4)/5=6802 ,

 R7=(54R6-36R5)/6=56190 ,R8=(64R7-45R6)/7=470010 が答になります。

.

スポンサーサイト



Comments 20

There are no comments yet.
ひとりしずか  
No title

キイロツリフネソウでしょうか・・

綺麗な色です
形も変わっていますね~
吊り下がっているのが面白い・・

ナイス!

uch*n*an  
No title

この問題は,最初題意を勘違いしており,
題意を理解した後も計算式はすぐにできたものの計算が大変で苦労しました。
実際,かなり面倒な問題だったようですね。
私の解法は二つ。
(解法1)は,[解答2]の C 三つの積の総和までは同じでしたが,後は単純に和を計算しました。
(解法2)は,[解答1]と同じでした。
[解答2]の C の積の総和は,いかにも何か多項式のべき乗の係数で書けそうと思ったものの,
どのみち計算は大変そうだし,じっくり考える時間もなかったのでやめてしまったのですが,
やはりうまく書けたのですね。しかも,それから漸化式も導けるとは。
今は時間がないので,後でじっくり読んでみます。

Yasuko  
No title

☆*。:゚*コンニヾ(*゚∀゚*)ノチワァ.゚。+*☆
今日のお花は、なんでしょう?
分かりませんわ^_^;

少し朝夕、暑さもましになってきたように(/ω・\)チラッ

ナイス!3個目デス

tsuyoshik1942  
No title

最初はプログラムを組み解きました。
その後、「確実な方法」とのコメントから「解答1」に気づきました。
そして、次に、2回から14回までの回数ごとの通り数を求めそれを総計し、同じ数値を得ました。この回数ごとの値の求め方は、きちんと整理が出来てませんでしたが、3個のCの積で「解答2」の枕部分と同じでした。
いずれにしろ、自分には「解答1」が確実で且つ時間的にも最良でした。

ところで、今70の手習いでチェスを始めました。初歩のうちは、上達が自覚でき楽しいです。

樹☆  
No title

こんにちは。
可愛い花ですね。君の名は?

朝夕少し涼しくなってきました。体調に気をつけてくださいね。チェックメイト。。笑
ナイスです。

スモークマン  
No title

グーテンターク ^^
解答1に気づけたものの...計算大変...何度も間違いました...^^;
何か上手い方法があるのかと...対角線上の数列を調べるも登録されてないし...とほほで...上3桁で半分安堵できるも...違ってたらサイドの計算は放棄しようと思ってたのでラッキーチャチャチャ♪

ニリンソウ  
No title

キツリフネね、山へ出かけたのでしょうか
初秋の花ですね。

ナイス

ヤドカリ  
No title

古い人さん、早速のコメントとナイス!を有難う御座います。
仰る通り、この花はキツリフネです。
赤紫のと色で感じが違いますね。

ヤドカリ  
No title

アキチャンさん、早速のコメントとナイス!を有難う御座います。
写真では見にくいですが、花が吊られている独特の形をしています。
黄色は目立ちますね。

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!を有難う御座います。
仰る通り、この花はキツリフネです。
ツリフネソウが鳳仙花のように種がはじけるのも面白いですね。

ヤドカリ  
No title

uch*n*anさん、早速のコメントを有難う御座います。
[解答2][参考]を作るのに時間がかかりましたが、うまく漸化式が導けました。
今まででいちばん長い解答だと思います。
それに、添え字や指数を使うときのタグのため、
5000字の制限に悩まされました。
ごゆっくりご覧ください。

ヤドカリ  
No title

yasukoさん、早速のコメントとナイス!を有難う御座います。
このキツリフネは花の文化園で見ました。
少し暑さがましになってきたので、また、行こうと思います。

ヤドカリ  
No title

tsuyoshik1942さん、コメントを有難う御座います。
[解答1]が確実ですね。
でも、[解答2][参考]を考えるのは充実していました。
ところで、チェスもいいですね。
将棋に比べて盤が狭いのに動きが激しいので、慣れないと大変だと思います。

ヤドカリ  
No title

樹ちゃん、コメントとナイス!を有難う御座います。
花はキツリフネです。
チェックメイトよりブログメイトが大切ですね。

ヤドカリ  
No title

スモークマンさん、コメントを有難う御座います。
対角線上の数列が、オンライン整数列大辞典に載っています。
uch*n*anさんと ftt*m*28さんからご指摘がありました。

ヤドカリ  
No title

ニリンソウさん、コメントとナイス!を有難う御座います。
8月に金剛山でも見ましたが、旨く撮れませんでしたので、諦めていましたが、
先日、花の文化園で出会うことができました。

スモークマン  
No title

グーテンアーベント ^^
載ってますねぇ ^^;
「Number of ways to move a chess rook from the lower left corner to square (n,n), with the rook moving only up or right.」...

わたしゃ...最初は計算の狂ったでたらめな数字を入力してたのかも...
なはっ...^^;;...Orz~

ヤドカリ  
No title

スモークマンさん、報告を有難う御座いました。

uch*n*an  
No title

[解答2]と[参考]を読みました。一応は理解できたと思います。
しかし,[解答2]の(1)~(3)は難しい。確かにこうすればよさそうなのは分かりますが,
ヒントなしではとても私には思い付きそうにないです。よく思い付かれましたね。さすが!
ただ,もう少し分かりやすい方法はないものかなぁ...
とはいえ,大変勉強になりました。詳しい記述をありがとうございます。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
> ただ,もう少し分かりやすい方法はないものかなぁ...
私もそう思っていろいろ考えましたが、これが精一杯です。
少しでも簡単に解釈できる方法があればご教示下さい。
貴殿に、「よく思い付かれましたね。さすが!」と言われれば、
時間をかけて考えた甲斐があったというものです。