『７段の階段』解答

◆山梨県　Footmark さんからの解答。

【問題１】

まず、（条件1）だけで７段の階段を昇る(または降りる)方法を考えてみます。
今、階段のある段まで昇って来たものとすると、その段に来る一歩手前は、１段下か２段下かのいずれかです。

それ故、その段まで昇る方法は、１段下まで、２段下までの、それぞれ昇る方法の合計です。
また、１段目まで、２段目まで、を昇る方法は以下の通りです。

１段目まで昇るのは１通り　：　(１)
２段目まで昇るのは２通り　：　(１＋１),(２)
これは、１段目を１，２段目を２として、
Ｋ段目の数 ＝ (Ｋー１)段目の数 ＋ (Ｋー２)段目の数
で、得られるフィボナッチ数列です。
　１段目まで：　　１通り
　２段目まで：　　２通り
　３段目まで：　　３通り
　４段目まで：　　５通り
　５段目まで：　　８通り
　６段目まで：　１３通り
　７段目まで：　２１通り
降りる方法も同様ですから（条件1）だけで昇る(または降りる)を１回する方法は２１通りあります。
当然、階段の１往復はこのことを２回行うので２１2通りです。

（条件２）を付加させます。

問題の条件より０段目(降りきる)と７段目(昇りきる)は必ず踏みます。
また、ある段を踏まなければその段の１段下と１段上は必ず踏まれます。

求める１往復して全ての段を踏んでいる場合の数は１往復の場合の数から１往復してもどこかの段が踏まれなかった場合の数を引いてやればよい筈です。

これらのことより

　１往復して全ての段を踏んでいる場合の数

＝１往復の場合の数
　−　１往復しても１段目は決して踏まない場合の数
　−　１往復しても２段目は決して踏まない場合の数
　−　１往復しても３段目は決して踏まない場合の数
　−　１往復しても４段目は決して踏まない場合の数
　−　１往復しても５段目は決して踏まない場合の数
　−　１往復しても６段目は決して踏まない場合の数

　＋　１往復しても１段目と３段目は決して踏まない場合の数
　＋　１往復しても１段目と４段目は決して踏まない場合の数
　＋　１往復しても１段目と５段目は決して踏まない場合の数
　＋　１往復しても１段目と６段目は決して踏まない場合の数
　＋　１往復しても２段目と４段目は決して踏まない場合の数
　＋　１往復しても２段目と５段目は決して踏まない場合の数
　＋　１往復しても２段目と６段目は決して踏まない場合の数
　＋　１往復しても３段目と５段目は決して踏まない場合の数
　＋　１往復しても３段目と６段目は決して踏まない場合の数
　＋　１往復しても４段目と６段目は決して踏まない場合の数

　−　１往復しても１段目と３段目と５段目は決して踏まない場合の数
　−　１往復しても１段目と３段目と６段目は決して踏まない場合の数
　−　１往復しても１段目と４段目と６段目は決して踏まない場合の数
　−　１往復しても２段目と４段目と６段目は決して踏まない場合の数

＝212
　−　[82＋(1ｘ5)2＋(2ｘ3)2＋(3ｘ2)2＋(5ｘ1)2＋82]
　＋　(32＋22＋22＋32＋22＋12＋22＋22＋22＋32)
　−　(12＋12＋12＋12)

＝　212-2(82＋52＋62)＋3(32)＋6(22)-3
＝　２３９
【答え】　２３９通り

【問題２】

１番下から昇りきるか１番上から降りきるかのどちらかを１回とすると、一般的にＮ回繰り返して全ての段を踏んでいる場合の数は、【問題１】で得られた最後の式の
　2　を　N　にすれば良いので

　昇りきるか降りきるかの行為をＮ回繰り返して全ての段を踏んでいる場合の数
＝21N-2(8N＋5N＋6N)＋3(3N)＋6(2N)-3
ここで２往復の時は、上式に　Ｎ＝４　を代入すれば得られるので
　２往復して全ての段を踏んでいる場合の数
＝214-2(84＋54＋64)＋3(34)＋6(24)-3
＝　１８２７８３
【答え】　１８２７８３通り

◆愛知県　Y.M.Ojisan さんからの解答。

【問題１】

２３９　とおり

【問題１証明と一般化】

１段または２段づつ移動可能な７段のぼりの場合の数は　「オンボロ階段」などで解説されているように「フィボナッチ数列」で表すことができます。

即ち
　ＦN=ＦN-1+ＦN-2
　Ｆ0=１,Ｆ1=１　より　Ｆ7=２１です。
以下にVisualに証明をして行きますが２１はちょっと多いので６段（１３個とおり）を例にします。

○Ｎ段移動の方法の表現 （１段、２段、１段。。。）というふうにそのまま表現することもできますが、
途中のＮ−１段のうち踏んだところを「０」踏んでないところを「１」で表し、
全体でＮ−１ビットのビットパターンで表すことも可能で、ここではこの方法ないし、これを１０進値化した値で「方法」を表現します。

　この場合、ビットパターンとしては２N-1通りありますが、
当然＞ＦNであり　「１」が２個以上連続するところがある（３段以上登った）パターンが排除されています。

このように考えると、「下り」のパターンも登りと全く同じになり区別する必要がありません。
従って、両方を合せて「Ｎ段移動の方法」と呼ぶことにします。

例）

Ｎ＝６

 　 　 　 　 　 　

５

 　 　 　 　 　 　

４

 　 　 　

踏

 　 　

３

 　 　

踏

 　 　 　

２

 　

踏

 　 　 　 　

１

 　 　 　 　 　 　

０

 　 　 　 　 　 　
　

１

０

０

０

１

＝１７

○記号の定義
（表現が簡潔になるのでかたくるしいですが記号化します）

　Ｎ	：　階段の段数（自然数）

　ＳN	：　Ｎ段の移動の方法の集合。　要素数はＦN　

　＆	：　Ｎ段の移動とＭ段の移動の合成演算。N=Mで登り降り後の状態を求める。
	　　実際にはビットパターンのビット毎の論理積である。ＳN＆ＳM
	　　すなわち、どちらも踏んでないときだけ「１」。

　[＆]	：　直積集合の作製。即ち　ＳN[＆]ＳN　は「登り＋下り」の全方法の集合。

  Exec()	：　直積集合の演算実行後の状態の集合作製。直積で無い場合はそのもの。
	　　一般にExec(ＳN[＆]ＳN)＝ＳN＆ＳN＝ＳN

Count()P	：　直積集合の要素のうち全演算実行後 状態がＰになる要素の個数。
	　　従って、問題１の答えは　Count(Ｓ7[＆]Ｓ7)0
　　　　　　 なお、ＰをはずしたCount()は　ＦN次元行ベクトル
	　　　　：＝( Count()0,Count()#2要素,.., Count()#Fn要素)　とする。

　ＳNq	：  ｑ個のＳN直積集合　＝ＳN[＆]ＳN[＆]ＳN[＆]ＳN…[＆]ＳN
	　　問題２の答えは　Count(Ｓ74)0
＃ｘ	：　下記関係（４）の方法でならべてｘ番目の方法（要素）を表す。＃０：０

○関係

（１）ＳN⊂ＳM　　for Ｎ＜Ｍ
ＳNの要素に対し残り階段を全部踏めばＳMの要素である。
下図参照

（２）ＳN＆ＳM＝Ｓmin(N，M)

ｅ∈ＳN⊂ＳMに対し
ｅ＆ｅ＝ｅ　である。

またＮ＜Ｍとして
ｅ∈ＳN　ｆ∈ＳMに対し
ｅ＆ｆ∈ＳN　である。
上図参照

（３）（ＳN+1−ＳN）＆ＳN＝ＳN-1

ＳN+1の要素の最上位２ビットに着目すると「１１」は無く、
「０１」，「００」 はＳNの要素であるから、
ＳN+1−ＳNの要素は最上位２ビットが「１０」である。
これとＳN要素との＆をとると最上位２ビットが「００」になり、
ＳN-1の要素である。
上図参照

（４）逆に（３）の方法でＳＮの要素を規則的に作製して行くことが可能であり、要素数がフィボナッチ数列であることと等価である。 

（５.1）Count((ＳN+1−ＳN）[＆]ＳN-1)＝Count(ＳN-1[＆]ＳN-1)
（５.2）Count((ＳN+1−ＳN）[＆]ＳN)＝Count(ＳN-1[＆]ＳN)
（３）の証明参照。

○計算

　Ｓ6[＆]Ｓ6 をExec()した個々の結果を下表（＆演算九九表）に示す。
この表から結果が「０」になる要素の数を数えればよく、
ＧN＝Count(ＳN[＆]ＳN)0と置くとき、Ｇ6＝９９であることが分かる。

なお、関係（１）（２）から要素を（４）により並べておけば、得られた九九表の左上
「ＦN×ＦN」の部分は「ＳN[＆]ＳN」の九九表になっており、
Ｇ1〜Ｇ6の値も数えることが出来る｡

　下表を見れば分かる様に
「Ｓ4[＆]Ｓ4」の部分（空色集合）のパターンを
「Ｓ5[＆]Ｓ5」は１個、「Ｓ6[＆]Ｓ6」は３個含み、
「Ｓ5[＆]Ｓ5」の一部分（灰色集合）のパターンを
「Ｓ6[＆]Ｓ6」は２セット含み、その他の部分は「０」を含んでいない｡

従って　Ｇ6＝２Ｇ5＋Ｇ4の関係がある。

これは一般にも正しく
ＧN+1＝２ＧN＋ＧN-1である。

なぜなら、関係（５.1）により空色集合

｛ＳN-1[＆]ＳN-1　と（ＳN+1−ＳN）[＆]ＳN-1とＳN-1[＆]（ＳN+1−ＳN）｝
は同じ個数パターンである。

また（５.2）により空色＋灰色集合

｛ＳN-1[＆]ＳN　と（ＳN+1−ＳN）[＆]ＳNとＳN[＆] ＳN-1とＳN[＆]（ＳN+1−ＳN）｝
も同じ個数パターンである。

また　緑色集合

｛（ＳN+1−ＳN）[＆]（ＳN+1−ＳN）｝
は最上位ビットが「１」同士なので「０」にはならない｡

よって、Ｇ7＝２Ｇ6＋Ｇ5＝２＊９９＋４１＝２３９である。

【問題２】

１８２７８３　通り

【問題２証明と一般化】

次のようなＦN×ＦN行列　NΓ　を作成する。

NΓIJ＝Count(＃J[＆]ＳN)＃I

この行列の要素の意味は　上りに＃J要素選び、下りに全ケースを行った場合に　＃Iの状態が残る組み合わせの数を示す。

従って、一般に「Ｎ段の移動」をｑ回行ったあとの各パターンの組み合わせ数のベクトルＶは、１をＦＮ個並べた列べクトルとNΓを用いて

Ｖ＝Count(ＳNq)＝NΓqｰ1×(1,1,1……,1)t

であり、全段を踏んだ場合の数は「０」に対応するその第一成分であって

Count(ＳNq)0
＝(1,0,0,…,0)×Ｖ
＝(1,0,0,…,0)×NΓqｰ1×(1,1,1…,1)tである。

　具体的にNΓの成分値を求めるには、先の九九表を作成して「０」の数、「＃２」の数。。。。。「＃Ｆｎ」の数を列毎に数え上げて列方向に記入しながら
上三角行列であるNΓを作成するのが簡単である。

　また、数学的には関係（５.1）（５.2）を用いて、初期値は異なるが全部フィボナッチ数列として一般項を表すことができる。
式で書くとややこしく、図で示したほうが分かりやすいので、
下図の7Γの作製方法を参照下さい。
赤以外の手順は単なるコピーで初期値設定に相当します。
また、無いところは基本的に０と考えます。

【計算過程】

×(1,1,1..，1)

U=

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

問題１

U7Γ=

21

13

16

15

10

15

9

12

16

10

12

12

8

13

8

10

9

6

10

6

8

239

U7Γ2=

441

377

416

405

350

405

345

384

416

356

392

384

332

377

322

356

345

298

350

298

332

7681

問題２

U7Γ3=

9261

8749

9136

9045

8560

9045

8541

8928

9136

8632

9012

8928

8450

8749

8264

8632

8541

8082

8560

8082

8450

182783

Γの値作製方法と作製結果


【感想ともっと簡単な証明】

　非常に良い問題ですね。
一見ただのパズルに見えたのですが、取り組んでみると大変数学的な問題だったので、驚いています。
結果的に調子に乗りすぎてかなり遠回りしてしまいました。

　問題２では大きな行列を介在させて解答していますが、Ｎ＝７までの結果（下表）を整理すると、結局、下記の予想漸化式が得られました。
実際これは正しく、問題の見方を文字どおり９０度回転すると、とても簡単に証明ができてしまいます。

ｑ＼Ｎ

1

2

3

4

5

6

7

1

1

1

1

1

1

1

1

2

1

3

7

17

41

99

239

3

1

7

25

109

445

1855

7681

4

1

15

79

593

3905

26943

182783

　以下は簡単な証明から最初に出てくる、殆ど証明アイデアそのものの式(ｑ次元ベクトル計算)です。
具体的なｑ＝２，４についてなら高校生でも容易なので、詳細は譲ります。

ここでCount(ＬM+1q)pはｑ回の「Ｎ段の移動」のうちでＭ＋１段目の踏みつけ状態がｐのビットパターン（ｑビット）であるもののＭ＋１段以下の状態の数です。
従って必要とする解答値は

Count(Ｓ72)0＝Count(Ｌ72)00とCount(Ｓ74)0＝Count(Ｌ74)0000
です。

下記式から、Count(ＳN+14)0＝Count(ＬN+14)0000は Ｎ〜Ｎ−３の場合の数である４項の線形和であることが言えるので、予想漸化式は正しいことが分かります。

もちろんちゃんと展開して計算すれば遠回りしないで係数も直接出るでしょう｡

◆出題者のＣＨＥＣＫ さんからのコメント。

お二方ともお見事正解です。
（本問の第1問は昭和30年頃に金沢大学で出題されたものです）

1つ気になったのはどちらの解答もまずフィボナッチ数列から入っていることです。
別に間違っているわけではないのですが，階段問題だからといっていきなり先に数列を決めて，後から条件を付加していくと，解答が非常に遠回りになる可能性があります。

例えば以下のような基本形の問題を考えてみます。

（例題）
ｎ段の階段を昇るとき，
1度に昇る段数が1段，2段の2種類であるとき，
その昇り方がｆ(ｎ)通りあるとして，ｆ(ｎ)を求めよ。

これぐらい単純な構成であれば，
「ｎ＋2段目の直前にはn＋1段目かｎ段目にいるので
漸化式はｆ(ｎ＋2)＝ｆ(ｎ＋1)＋ｆ(ｎ)である」
として，直接答えに持っていくことが出来ます。

ところが，「7段の階段」問題のように条件が厳しくなった場合，このように漸化式を立てるのは難しくなります。
かといってｆ(ｎ＋2)＝ｆ(ｎ＋1)＋ｆ(ｎ)に条件を付加していくと立てた漸化式そのもの意味が薄くなりがちです。

そこで考え方を変えてみます。
いかなる場合の数の問題も必ず抽象論が存在するはずです。
ですから漸化式に最初から条件を組み込む方法を考えます。
すなわち1対1対応となる事象を考えます。

1段目からｎ段目までの各段を
「踏む･･･A，踏まない･･･B」

によって表すと，A，Bの2文字の順列を考えることになります。
「Bが2つ以上連続して並ぶことがない」という条件を組み込みます。

ここでｎ段目にA，Bがくる場合の数を
それぞれａ(n)，b(n)とすれば

ａ(n＋1)＝ａ(n)＋b(n)，b(n＋1)＝ａ(n)

という連立ニ項間漸化式が成り立ちます。
（片方の数列を消去すればフィボナッチとなる）

このとき，求める場合の数はａ(n)＋b(n)です。

この考え方で「7段の階段」問題を解くとコンパクトな解答ができます。
以下，解答。

【解答】
（問題1のみを一般型で解いています）

1段目からｎ段目までの各段を

昇るときだけ踏む･･･Ａ，
降りるときだけ踏む･･･Ｂ，
両方で踏む･･･Ｃ

と表すことによりＡ，Ｂ，Ｃの順列を考える。
ここでｎ段目にＡ，Ｂ，Ｃがくる場合の数を
それぞれａ(n)，b(n)，c(n)とすると
「Ａ，Ｂのどちらも2つ以上連続して同じものがならぶことはない」ので

ａ(n＋1)＝b(n)＋c(n)，
b(n＋1)＝ａ(n)＋c(n)，
c(n＋1)＝ａ(n)＋b(n)＋c(n)

となる。
ただしａ(2)＝b(2)＝c(2)＝1である。

これにより求める答えはａ(n)＋b(n)＋c(n)である。

なお，この場合1つの漸化式で表すと

c(n＋2)＝2c(n＋1)＋c(n)となり，フィボナッチ数列とは異なったものになります。

要するに階段問題では条件次第で漸化式は様様に変わるのであり，フィボナッチ数列はそのうちの1つに過ぎないということです。
なお問題2も，立てる2項間漸化式は増えますが，対称性から最終的には数列は4つまで減らして解くことができます。

さて，問題1は「1往復」ですが，これは要するに階段を2回昇るのと同じ事です。
そこでｎ段の階段をN回昇る方法がｇ(n,N)通りあるとして一般形を考えてみます。

数列ｆ(n,N)を以下のように定めます。
（Ｃはニ項係数）

ｆ(n,0)＝0，

ｆ(2,1)＝ｆ(2,2)＝･･･＝ｆ(2,N)＝1

ｆ(n＋1,k)＝kＣ0ｆ(n,N−k)＋kＣ1ｆ(n,N−k＋1)＋･･･＋kＣkｆ(n,N)
このときｇ(n,N)＝ｆ(n,0)＋ｆ(n,1)＋･･･＋ｆ(n,N)が成り立ちます。

上で使った条件を最初から組み込む方法と対称性および組み合わせ論から証明が可能です。
これはY.M.Ojisanの解答の一番下にあるものと同じ結果です。

　『７段の階段』へ

　数学の部屋へもどる