平成２１年５月２４日

[流れ星]

　　　　　第２２４回数学的な応募問題解答

　　　　　　＜解答募集期間：５月３日〜５月２４日

［階段の昇降数］

下図のようなｎ段の階段がある。これを昇るにも、降りるにも、1段ずつでも、2段ずつでもよいし、また1段と2段とを混ぜてもよいとすれば、昇って降りる仕方は何通りあるか。

ただし、1昇降の間には各段を少なくとも1回は必ず踏むものとする。

このとき昇って降りる仕方をａ_ｎ（ｎは2以上の自然数）として、次の順序で答えよ。

問１：ｎ＝２，３，４、５のとき、ａ_２，ａ_３，ａ_４，ａ_５の値を

それぞれ求めよ。

問２　ａ_ｎ＋２をａ_ｎ＋１とａ_ｎで表す漸化式を求めよ。

問３　ａ_ｎをｎで表せ。

NO1「uchinyan」 5/03 15時57分受信 更新5/24

第２２４回数学的な応募問題
［階段の昇降数］

床を 0 段目とし，a 段目から b 段目に移動するのを a -> b と書くことにします。

問1：
(1) n = 1
01 : 0 -> 1 -> 0
なので，
a(1) = 1
(2) n = 2
01 : 0 -> 1 -> 2 -> 1 -> 0
02 : 0 -> 1 -> 2 -> 0
03 : 0 -> 2 -> 1 -> 0
0 -> 2 -> 0 は，1 段目を踏んでいないので不可
なので，
a(2) = 3
(3) n = 3
01 : 0 -> 1 -> 2 -> 3 -> 2 -> 1 -> 0
02 : 0 -> 1 -> 2 -> 3 -> 2 -> 0
03 : 0 -> 1 -> 2 -> 3 -> 1 -> 0
04 : 0 -> 1 -> 3 -> 2 -> 1 -> 0
05 : 0 -> 1 -> 3 -> 2 -> 0
06 : 0 -> 2 -> 3 -> 2 -> 1 -> 0
07 : 0 -> 2 -> 3 -> 1 -> 0
なので，
a(3) = 7
(4) n = 4
01 : 0 -> 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0
02 : 0 -> 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 0
03 : 0 -> 1 -> 2 -> 3 -> 4 -> 3 -> 1 -> 0
04 : 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 1 -> 0
05 : 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
06 : 0 -> 1 -> 2 -> 4 -> 3 -> 2 -> 1 -> 0
07 : 0 -> 1 -> 2 -> 4 -> 3 -> 2 -> 0
08 : 0 -> 1 -> 2 -> 4 -> 3 -> 1 -> 0
09 : 0 -> 1 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0
10 : 0 -> 1 -> 3 -> 4 -> 3 -> 2 -> 0
11 : 0 -> 1 -> 3 -> 4 -> 2 -> 1 -> 0
12 : 0 -> 1 -> 3 -> 4 -> 2 -> 0
13 : 0 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0
14 : 0 -> 2 -> 3 -> 4 -> 3 -> 1 -> 0
15 : 0 -> 2 -> 3 -> 4 -> 2 -> 1 -> 0
16 : 0 -> 2 -> 4 -> 3 -> 2 -> 1 -> 0
17 : 0 -> 2 -> 4 -> 3 -> 1 -> 0
なので，
a(4) = 17
(5) n = 5
01 : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
02 : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 0
03 : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 1 -> 0
04 : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 2 -> 1 -> 0
05 : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 2 -> 1 -> 0
06 : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 2 -> 0
07 : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 2 -> 0
08 : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 1 -> 0
09 : 0 -> 1 -> 2 -> 3 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
10 : 0 -> 1 -> 2 -> 3 -> 5 -> 4 -> 3 -> 2 -> 0
11 : 0 -> 1 -> 2 -> 3 -> 5 -> 4 -> 3 -> 1 -> 0
12 : 0 -> 1 -> 2 -> 3 -> 5 -> 4 -> 2 -> 1 -> 0
13 : 0 -> 1 -> 2 -> 3 -> 5 -> 4 -> 2 -> 0
14 : 0 -> 1 -> 2 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
15 : 0 -> 1 -> 2 -> 4 -> 5 -> 4 -> 3 -> 2 -> 0
16 : 0 -> 1 -> 2 -> 4 -> 5 -> 4 -> 3 -> 1 -> 0
17 : 0 -> 1 -> 2 -> 4 -> 5 -> 3 -> 2 -> 1 -> 0
18 : 0 -> 1 -> 2 -> 4 -> 5 -> 3 -> 2 -> 0
19 : 0 -> 1 -> 2 -> 4 -> 5 -> 3 -> 1 -> 0
20 : 0 -> 1 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
21 : 0 -> 1 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 0
22 : 0 -> 1 -> 3 -> 4 -> 5 -> 4 -> 2 -> 1 -> 0
23 : 0 -> 1 -> 3 -> 4 -> 5 -> 3 -> 2 -> 1 -> 0
24 : 0 -> 1 -> 3 -> 4 -> 5 -> 4 -> 2 -> 0
25 : 0 -> 1 -> 3 -> 4 -> 5 -> 3 -> 2 -> 0
26 : 0 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
27 : 0 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 1 -> 0
28 : 0 -> 2 -> 3 -> 4 -> 5 -> 4 -> 2 -> 1 -> 0
29 : 0 -> 2 -> 3 -> 4 -> 5 -> 3 -> 2 -> 1 -> 0
30 : 0 -> 2 -> 3 -> 4 -> 5 -> 3 -> 1 -> 0
31 : 0 -> 1 -> 3 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
32 : 0 -> 1 -> 3 -> 5 -> 4 -> 3 -> 2 -> 0
33 : 0 -> 1 -> 3 -> 5 -> 4 -> 2 -> 1 -> 0
34 : 0 -> 1 -> 3 -> 5 -> 4 -> 2 -> 0
35 : 0 -> 2 -> 3 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
36 : 0 -> 2 -> 3 -> 5 -> 4 -> 3 -> 1 -> 0
37 : 0 -> 2 -> 3 -> 5 -> 4 -> 2 -> 1 -> 0
38 : 0 -> 2 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
39 : 0 -> 2 -> 4 -> 5 -> 4 -> 3 -> 1 -> 0
40 : 0 -> 2 -> 4 -> 5 -> 3 -> 2 -> 1 -> 0
41 : 0 -> 2 -> 4 -> 5 -> 3 -> 1 -> 0
なので，
a(6) = 41

これを，問2：を意識して，漸化式っぽく考えてみます。

5 段目まで昇って降りるのは，
1) 途中 4 段目まで昇って降りる場合は，その後，
4 -> 5 -> 4
なので，a(4) * 1 = a(4) 通り。
2) 途中 3 段目まで昇って降りる場合は，その後，
昇り降りとも 4 段目を経由するのは 1) に含まれるので，それを除いて，
3 -> 4 -> 5 -> 3
3 -> 5 -> 4 -> 3
3 -> 5 -> 3 は 4 段目を踏まないので不可
なので，a(3) * 2 = 2 * a(3) 通り。
3) 途中 2 段目まで昇って降りる場合は，その後，
昇り降りとも 4, 3 段目を経由するのは 1), 2) に含まれるので，それを除いて，
2 -> 3 -> 5 -> 4 -> 2
2 -> 4 -> 5 -> 3 -> 2
しかないので，a(2) * 2 = 2 * a(2) 通り。
4) 途中 1 段目まで昇って降りる場合は，その後，
昇り降りとも 4, 3, 2 段目を経由するのは 1), 2), 3) に含まれるので，それを除いて，
1 -> 2 -> 4 -> 5 -> 3 -> 1
1 -> 3 -> 5 -> 4 -> 2 -> 1
しかないので，a(1) * 2 = 2 * a(1) 通り。
以上ですべてなので，
a(5) = a(4) + 2 * a(3) + 2 * a(2) + 2 * a(1)
になります。
a(4) についても同様のことを考えると，
a(3) 経由：3 -> 4 -> 3
a(2) 経由：2 -> 3 -> 4 -> 2, 2 -> 4 -> 3 -> 2
a(1) 経由：1 -> 2 -> 4 -> 3 -> 1, 1 -> 3 -> 4 -> 2 -> 1
なので，
a(4) = a(3) + 2 * a(2) + 2 * a(1)
です。そこで，
a(5) - a(4) = a(4) + a(3)
a(5) = 2 * a(4) + a(3) = 2 * 17 + 7 = 34 + 7 = 41
になります。確かに，地道に数えたものと一致しています。

問2：
問1；の(5)の後半で考えた方法を一般化します。n = 1, 2, 3,... とします。
n+2 段目まで昇って降りるのは，
1) 途中 n+1 段目まで昇って降りる場合は，その後，
n+1 -> n+2 -> n+1
なので，a(n+1) * 1 = a(n+1) 通り。
2) 途中 n 段目まで昇って降りる場合は，その後，
昇り降りとも n+1 段目を経由するのは 1) に含まれるので，それを除いて，
n -> n+1 -> n+2 -> n
n -> n+2 -> n+1 -> n
n -> n+2 -> n は n+1 段目を踏まないので不可
なので，a(n) * 2 = 2 * a(n) 通り。
3) 途中 k 段目，1 <= k <= n-1，まで昇って降りる場合は，その後，
昇り降りとも n+1, n, ..., k+1 段目のうち同じ段を経由するのは，他の場合に含まれるので，それを除きます。
すると，降りる又は昇るのは 1 段又は 2 段なので，k 〜 n+2 の間で，
・1 段ずつ続けて昇ったり降りたりが起こる場合
・1 段 + 2 段 又は 2 段 + 1 段 が起こる場合
は，昇り降りの往復で，必ず，少なくとも一つ同じ段を経由することが分かるので，
それが k 段目又は n+2 段目で起こる場合以外を除きます。
そこで可能なのは，1 段 + 2 段，2 段 + 1 段 が両端で起こるか，2 段ずつだけで昇る場合だけです。
ただし，段を必ず踏まないといけないので，結局，
・n+2-k が偶数の場合
k -> k+1 -> k+3 -> ...(2 段ずつ)... -> n-1 -> n+1 -> n+2 -> n -> ...(2 段ずつ)... -> k+2 -> k
k -> k+2 -> ...(2 段ずつ)... -> n -> n+2 -> n+1 -> n-1 -> ...(2 段ずつ)... -> k+3 -> k+1 -> k
・n+2-k が奇数の場合
k -> k+1 -> k+3 -> ...(2 段ずつ)... -> n -> n+2 -> n+1 -> n-1 -> ...(2 段ずつ)... -> k+2 -> k
k -> k+2 -> ...(2 段ずつ)... -> n-1 -> n+1 -> n+2 -> n -> ...(2 段ずつ)... -> k+3 -> k+1 -> k
だけです。そこで，a(k) * 2 = 2 * a(k) 通り。
以上ですべてなので，
a(n+2) = a(n+1) + 2 * a(n) + 2 * a(n-1) + ... + 2 * a(2) + 2 * a(1)
になります。同様にして，
a(n+1) = a(n) + 2 * a(n-1) + 2 * a(n-2) + ... + 2 * a(2) + 2 * a(1)
なので，
a(n+2) - a(n+1) = a(n+1) + a(n)
a(n+2) = 2 * a(n+1) + a(n)
になります。ただし，n = 1, 2, 3, ... で，a(1) = 1, a(2) = 3 です。

問3：
a(n+2) = 2 * a(n+1) + a(n), n = 1, 2, 3, ...
a(1) = 1, a(2) = 3
を解けばいいです。少し丁寧にやってみましょう。
よくやるように，
a(n+2) - p * a(n+1) = q * (a(n+1) - p * a(n))
という形に変形することを考えます。これは，
a(n+2) - (p + q) * a(n+1) + pq * a(n) = 0
と書けます。元の漸化式は，
a(n+2) = 2 * a(n+1) + a(n)
a(n+2) - 2 * a(n+1) - a(n) = 0
比較すると，
p + q = 2
pq = -1
となるように，p, q を決めればいいです。
この p, q は，次の t についての二次方程式の解になります。
t^2 - 2t - 1 = 0
t = 1 - sqrt(2), 1 + sqrt(2)
そこで，
p = 1 - sqrt(2), q = 1 + sqrt(2)
とします。この p, q に対して，
a(n+2) - p * a(n+1) = q * (a(n+1) - p * a(n))
a(n+2) - p * a(n+1) = q^n * (a(2) - p * a(1))
a(n+1) - p * a(n) = q^(n-1) * (a(2) - p * a(1))　... (A)
また，
a(n+2) - (p + q) * a(n+1) + pq * a(n) = 0
は，
a(n+2) - q * a(n+1) = p * (a(n+1) - q * a(n))
とも変形できるので，
a(n+2) - q * a(n+1) = p^n * (a(2) - q * a(1))
a(n+1) - q * a(n) = p^(n-1) * (a(2) - q * a(1))　... (B)
そこで，(A) - (B) より，
(q - p) * a(n) = (a(2) - p * a(1)) * q^(n-1) - (a(2) - q * a(1)) * p^(n-1)
q - p = 2 * sqrt(2) not= 0 なので，
a(n) = {(a(2) - p * a(1)) * q^(n-1) - (a(2) - q * a(1)) * p^(n-1)}/(q - p)
p = 1 - sqrt(2), q = 1 + sqt(2), a(1) = 1, a(2) = 3 を代入して，
a(n) = {(3 - (1 - sqrt(2)) * 1) * (1 + sqrt(2))^(n-1) - (3 - (1 + sqrt(2)) * 1) * (1 - sqrt(2))^(n-1)}/((1 + sqrt(2)) - (1 - sqrt(2)))
a(n) = {(2 + sqrt(2)) * (1 + sqrt(2))^(n-1) - (2 - sqrt(2)) * (1 - sqrt(2))^(n-1)}/(2 * sqrt(2))
a(n) = ((1 + sqrt(2))^(n-1) - (1 - sqrt(2))^(n-1))/sqrt(2) + ((1 + (sqrt(2))^(n-1) + (1 - sqrt(2))^(n-1))/2
最後の式は計算が楽になるようにしました。そして，確かに，
a(1) = ((1 + sqrt(2))^0 - (1 - sqrt(2))^0)/sqrt(2) + ((1 + (sqrt(2))^0 + (1 - sqrt(2))^0)/2
= 0 + 2/2
= 1
a(2) = ((1 + sqrt(2))^1 - (1 - sqrt(2))^1)/sqrt(2) + ((1 + (sqrt(2))^1 + (1 - sqrt(2))^1)/2
= 2 + 1
= 3
a(3) = ((1 + sqrt(2))^2 - (1 - sqrt(2))^2)/sqrt(2) + ((1 + (sqrt(2))^2 + (1 - sqrt(2))^2)/2
= 4 + 3
= 7
a(4) = ((1 + sqrt(2))^3 - (1 - sqrt(2))^3)/sqrt(2) + ((1 + (sqrt(2))^3 + (1 - sqrt(2))^3)/2
= 10 + 7
= 17
a(5) = ((1 + sqrt(2))^4 - (1 - sqrt(2))^4)/sqrt(2) + ((1 + (sqrt(2))^4 + (1 - sqrt(2))^4)/2
= 24 + 17
= 41
となって，問1：の結果と一致します。

(感想)
昇るだけ，降るだけならば，フィボナッチ数列になることはよく知られていますが，
昇り降りは初めて見ました。似たような漸化式になるのですね。

NO2「BossF」 5/08 5時33分受信 更新5/24

N段の階段の昇り方（＝降り方）＝ｂｎとするとａｎ＝ｂｎ^2

さてN段に昇るためには、N−1段目から1段昇るか、N-2段目から2段昇るかのいずれかだから

ｂｎ＝ｂｎ-1+ｂｎ-2

以上より以下を得る

問１　ａ２＝4　ａ３＝9　ａ４＝25　ａ５＝64

問２　ａｎ＋２＝{sqrt (ａｎ＋１) +sqrt (ａｎ)}^2

問３ ｛sqrt (ａｎ) }　はfibonacciであるから、ａｎ＝(1/5)[ {(1+√5)/2}^n-{(1-√5)/2}^n]^2

＜水の流れコメント：昇りかまたは降りのとき必ず一度階段を踏んでいきますから、フィボナッチ数列の平方にはなりません。＞

NO3「kashiwagi」 5/11 12時22分受信

「kashiwagi」 5/22 22時16分受信 更新5/24

224回解答

問1.

今、一段昇りを1、2段昇りを2と表すと

�@ ｎ＝2のときは、昇り方1-2と2の2種類。そして降り方も同じ2種類。

但し、昇りも降りも2、2とすると1は踏まない事になるのでa₂ = 2×2-1＝3、

�A ｎ＝3のときは、昇り方1-2-3、2-3および1-3の3種類。そして降り方も同じ3種類。

但し、昇りも降りも2-3および1-3の場合は1と2を踏まないのでa₃= 3×3-2＝7

以上の考え方を踏襲し、ｎの個数を増やして考えると以下の様になる。

a₂ = 2×2-1＝3

a₃= 3×3-2＝7

a₄ = 5×5-8＝17

a₅=8×8-23＝41

a₆=13×13-70＝99

問2.

　問1の結果を良く見ると、

　　　　　　　　　　　　　　　　　となっていることが分かる。

問3.

今、方程式の2根をα、β（β≧α）とすると

α+β＝2、αβ＝-1であるから問2の結果を使い

　・・・・・・・・・・�@　となる。これより変形して

　

即ち、数列は公比βの等比数列であるから

　・・・・・・�A　となる。

　　・・・・・・�B　となる。

ここで�Aおよび�Bにa₂ ＝3、a₃　＝7を代入し、ｎを一段下げ、

　・・・・・・�C　を得る。

ここで、αとβの値を求めると、　、であるから、これらより　となる。

以　　　上．　

NO4「kasama」 5/21 15時15分受信 更新5/24

問1

昇降方法を洗い出すと、下表のようになります。

n	昇降方法	an
2	1 1 -1 -1	3
	1 1 -2
	2 -1 -1
3	1 1 1 -1 -1 -1	7
	1 1 1 -1 -2
	1 1 1 -2 -1
	1 2 -1 -1 -1
	1 2 -1 -2
	2 1 -1 -1 -1
	2 1 -2 -1
4	1 1 1 1 -1 -1 -1 -1	17
	1 1 1 1 -1 -1 -2
	1 1 1 1 -1 -2 -1
	1 1 1 1 -2 -1 -1
	1 1 1 1 -2 -2
	1 1 2 -1 -1 -1 -1
	1 1 2 -1 -1 -2
	1 1 2 -1 -2 -1
	1 2 1 -1 -1 -1 -1
	1 2 1 -1 -1 -2
	1 2 1 -2 -1 -1
	1 2 1 -2 -2
	2 1 1 -1 -1 -1 -1
	2 1 1 -1 -2 -1
	2 1 1 -2 -1 -1
	2 2 -1 -1 -1 -1
	2 2 -1 -2 -1

n	昇降方法	an
5	1 1 1 1 1 -1 -1 -1 -1 -1	41
	1 1 1 1 1 -1 -1 -1 -2
	1 1 1 1 1 -1 -1 -2 -1
	1 1 1 1 1 -1 -2 -1 -1
	1 1 1 1 1 -1 -2 -2
	1 1 1 1 1 -2 -1 -1 -1
	1 1 1 1 1 -2 -1 -2
	1 1 1 1 1 -2 -2 -1
	1 1 1 2 -1 -1 -1 -1 -1
	1 1 1 2 -1 -1 -1 -2
	1 1 1 2 -1 -1 -2 -1
	1 1 1 2 -1 -2 -1 -1
	1 1 1 2 -1 -2 -2
	1 1 2 1 -1 -1 -1 -1 -1
	1 1 2 1 -1 -1 -1 -2
	1 1 2 1 -1 -1 -2 -1
	1 1 2 1 -2 -1 -1 -1
	1 1 2 1 -2 -1 -2
	1 1 2 1 -2 -2 -1
	1 2 1 1 -1 -1 -1 -1 -1
	1 2 1 1 -1 -1 -1 -2
	1 2 1 1 -1 -2 -1 -1
	1 2 1 1 -1 -2 -2
	1 2 1 1 -2 -1 -1 -1
	1 2 1 1 -2 -1 -2
	1 2 2 -1 -1 -1 -1 -1
	1 2 2 -1 -1 -1 -2

n	昇降方法	an
5	1 2 2 -1 -2 -1 -1	41
	1 2 2 -1 -2 -2
	2 1 1 1 -1 -1 -1 -1 -1
	2 1 1 1 -1 -1 -2 -1
	2 1 1 1 -1 -2 -1 -1
	2 1 1 1 -2 -1 -1 -1
	2 1 1 1 -2 -2 -1
	2 1 2 -1 -1 -1 -1 -1
	2 1 2 -1 -1 -2 -1
	2 1 2 -1 -2 -1 -1
	2 2 1 -1 -1 -1 -1 -1
	2 2 1 -1 -1 -2 -1
	2 2 1 -2 -1 -1 -1
	2 2 1 -2 -2 -1

問2

n、n+1、n+2段目の昇り降りをパターン別けして図示すると、次のようになります。

ケースA		n+1段目を昇り降りの両方で踏む場合
ケースB		n+1段目を昇りで踏み、降りで踏まない場合
ケースC		n+1段目を降りで踏み、昇りで踏まない場合

ケースB、Cを組み合わせた昇り降りはないので、n段目⇔n+2段目の場合数はa_nです。そして、n+1段目⇔n+2段目の場合数はケースAの場合数a_n+1とケースB、Cの場合数a_n+1の和2a_n+1です。したがって、

　a_n+2 = 2a_n+1 + a_n

です。

問3

問2の差分方程式を解けばよい。その特性方程式は解をλとすると、

　λ² - 2λ - 1 = 0

です。これを解くとλ=1±√2なので一般解は、

　a_n = c₁(1-√2) + c₂(1+√2)

と表すことができます。ここで、a₁=1、a₂=3の初期条件を与えると、c₁=c₂=1/2だから、

　a_n = {(1-√2)ⁿ+(1+√2)ⁿ}/2

です。

＜コメント：今回はフィボナッチ数列に似た階段の昇り降りの問題ですね。
いろんなアプローチがあると思いますが、階段の昇り降りを３種類にパターン分けして考えました。

それほど高度な数学の知識がなくとも取り組める手軽さがいいと思います。＞

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。