第57問の解答


1.問題 [場合の数・数列

問題図
 左図のような、正四面体頂点Aに今います。

1秒後には、他の3つの頂点のどれかに移動します。

移動のしかたには、特に制限はありません。例えば次の1秒後に再び元の頂点Aに戻ってもかまいません。ただし、同じ場所に止まってはいけません。

このように移動を続けて、7秒後に頂点Aにいるような動き方は何通りあるでしょう?


2.解答例1(長野 美光さん、kuri他

移動できる状況を図で表すと下図のようになります。

参考図1

そこで、n秒後頂点A、頂点B、頂点C、頂点Dに移動できる場合の数をnnnnとします。
すると上図から、
  n+1nnn ・・・ (1)
  n+1nnn ・・・ (2)
  n+1nnn ・・・ (3)
  n+1nnn ・・・ (4)
と表せます。ただし、初期値は0=0=00=00=0です。

これらの式に従って、順次計算していくと下表のよう7=546になります。

 参考図2

 答:546通り

以上


3.解答例2(あれふさん、井合宗太郎さん他

前述の漸化式を加えて、(1)+(2)+(3)+(4)より、
  n+1n+1n+1n+1(annnn)×3
となるので、nnnnは、初項0000で公比がの等比数列となります。従って、nnnnnとなります。

従って、
  an+1n(bnnn)+nn ・・・ (5)
  n+1nn               ・・・ (6)
が得られます。

(6)を用いて、順次計算して、下表のように7=546が求まります。

参考図3


4.解答例3(B2さん他

(5)式を用いて、nの一般式を求めましょう。

(補題)次のような漸化式(線型漸化式といいます)
  n+m+pm-1n+m-1+pm-2n+m-2・・・+p0n=0
 
に対して、
  xm
+pmxm-1+pm-1xm-2・・・+p1=0
 の解をα1、α2、・・・αmとします(重根はないものとします)。
 このとき、
  an=A1α1n-1+A2α2n-1+・・・+Amαmn-1
 
と表すことが出来ます。

 

(方法1)
  
(5)より、
   n+1−1/4×n+1=−(n1/4×n
  を得るので、n1/4×nは、公比−1、初項01/4×0=3/4なる等比数列。
  よって、n1/4×n=3/4×(−1)となり、
   an=1/4×n+3/4×(−1)
  が得られます。

(方法2)
  
(5)より、
   n+2n+1n+1 ・・・ (7)
  (7)−(5)×3より、
   an+2n+1−(n+1n)×3=0
  よって、n+2−2×n+1−3×n=0なる線型漸化式を得る。

  従って補題より、x2−2x−3=0をまず解きます。
  (x−3)×(x+1)=0となり、x=3、x=−1が得られます。
  よって、 n=A1×n+A2×(−1)nを得ます。
  ここで、A1、A2は、
   0=A1+A21=3×A1−A2
  
から、A1=1/4、A2=3/4を得ます。
  
 従って、n=1/4×n+3/4×(−1)となります。

(補題の証明1)m=3とします。
  n+3+p2n+2+p1n+1+p0n=0
 
に対して、x3+p3x2+p2x+p1=0 の解をα1、α2、α3とします。
 このとき、
  bn=A1α1n-1+A2α2n-1+A3α3n-1とします。
 
ただし、A1、A2、A3は、 
 A1+A2+A311α1+A2α2+A3α321α12+A2α22+A3α323
を解いて求めることとします。

 証明は数学的帰納法を用います。
(1)b11、b22、b33は明らか。
(2)n≦k(ただし、k≧3)のとき、bnnが成り立つとします。
  n=k+1のとき、
  bn=A1α1k+A2α2k+A3α3k
   =
1α1k-3×α13+A2α2k-3×α23+A3α3k-3×α33
   =
−A1α1k-3×(p3α12+p2α1+p1)+A2α2k-3×(p3α22+p2α2+p1
     +A3α3k-3×(p3α32+p2α3+p1
   =−p3×(A1α1k-1+A2α2k-1+A3α3k-1)−p2×(A1α1k-2+A2α2k-2+A3α3k-2
     −p1×(A1α1k-3+A2α2k-3+A3α3k-3
   =−p3×k−p2×k-1−p1×k-2
   =−p3×k−p2×k-1−p1×k-2(仮定より)
   =k+1
 よって、n=k+1のときもbnnが成り立つ。

 以上から、数学的帰納法により、全てのnについて、bnnが成り立つ。

(補題の証明2)m=2とします。
n+2+p1n+1+p0n=0に対して、x2+p2x+p1=0 の解をα1、α2とします。
2次方程式の根と係数の関係より、α1+α2=−p2、α1×α2=p1となります。

これから、漸化式を次のように変形します。
  n+2−(α1+α2n+1α1α2n0
  a
n+2α1n+1α2n+1α1n)=0
これは、n+1α1nが公比α2となることを表しているので、
  n+1α1n=C1α2n-1 ・・・(8) と表せます。ただし、C1は定数。
まったく同様にして、
  n+1α2n=C2α1n-1 ・・・(9) と表せます。

(9)−(8)より、
  (α1−α2n=C2α1n-1−C1α2n-1
α1
α2は異なるので、
  n=C2/(α1−α2α1n-1−C1/(α1−α2α2n-1
  A1=C2/(α1−α22=−C1/(α1−α2)とおけば、
  n=A1α1n-1+A2α2n-1 と表せます。

 以上


(参考問題:武田 浩紀さんによる

1秒前と同じ頂点には戻ってはいけないという制限を加えた場合、7秒後に頂点Aにいるような動き方は何通りあるでしょう?

移動できる条件は、下図のように1秒目の状態に影響されます。

参考図3

そこで、1秒前にはBにいて現在Aにいる場合の数をba(n+1)のように表すことにします。
漸化式および初期値は、次の通り。 

ba(n+1)=cb(n)+db(n)
ca(n+1)=bc(n)+dc(n)
da(n+1)=bd(n)+cd(n)
ab(n+1)=ca(n)+da(n)
cb(n+1)=ac(n)+dc(n)
db(n+1)=ad(n)+cd(n)
ac(n+1)=ba(n)+da(n)
bc(n+1)=ab(n)+db(n)
dc(n+1)=ad(n)+bd(n)
ad(n+1)=ba(n)+ca(n)
bd(n+1)=ab(n)+cb(n)
cd(n+1)=ac(n)+bc(n)
ba(1)=0
ca(1)=0
da(1)=0
ab(1)=1
cb(1)=0
db(1)=0
ac(1)=1
bc(1)=0
dc(1)=0
ad(1)=1
bd(1)=0
cd(1)=0

この漸化式に従って順次計算していけば、下表のようになる。

参考図4

よって、(7)=ba(7)+ca(7)+da(7)=18+18+18=54となる。

答:54通り


(参考問題の漸化式から一般項を求める)

上記図より、ba(n)=ca(n)=da(n)(=(n)とおく)、ab(n)=ac(n)=ad(n)(=(n)とおく)、およびそれ以外(すべて等しく(n)とおく)の3種類に分かれます。

これから、(n)、(n)、(n)に関する漸化式、初期値は次の通りになります。

(n+1)=2×(n)  ・・・ (11)
(n+1)=2×(n)  ・・・ (12)
(n+1)=(n)+r(n) ・・・ (13)
(1)=0
(1)=1
(1)=0

(11)より、(n)=1/2×(n+1)、(n+1)=1/2×(n+2)、
(12)より、(n)=2×(n−1)となるので、これらを(13)に代入して
  1/2×(n+2)=2×(n−1)+1/2×(n+1)
nをn+1に置き換え整理して、
  (n+3)−(n+2)−4×(n)=0 を得る。

前述の補題より、まずx3x2−4=0を解きます。
x−2)×(x2x+2)=0となり、x=2、x=(−1±√7)/2が得られます。
α=(−1+√7)/2、β=(−1−√7)/2とおけば、
  (n)=A×n-1+B×αn-1+C×βn-1 が得られます。
A、B、Cは(1)=A+B+C=0、(2)=3A+αB+βC=0、(3)=9A+α2B+β2C=2より、
 A=1/4、B=(−7+5√7)/56、C=(−7−5√7)/56
を得ます。

よって、(n)=3×(n)
=3/4×n-1+3/56×(-7+5√7)×((-1+√7)/2)n-1+3/56×(-7-5√7)×((-1-√7)/2)n-1

    となります。

以上