平成１５年４月１５日
[流れ星]
第１１７回数学的な応募問題解答
＜解答募集期間：４月１日〜４月１５日＞
［人生模様］
太郎さんの学校では、離任式が今年から３月の下旬に行われる終業式の中でありました。特に、担任のある場合は
生徒の驚きは大変なものがあります。１９年間在職されて、今年退職される先生の話の中で、「人生には、３つの坂があります。
登り坂、下り坂、あと１つ皆さん、分かりますか？」生徒からは返事のないのを見計らって、「それは まさか の さか です。皆さん、この まさか に出会ったときに 動じることなく、人生を生き抜いてください。」大変ユニークな話でした。
ここで、問題です。
人生の中で、ｎ個の登り坂とｎ個の下り坂に出会ったとします。
そうすると、どんなライフライン（人生模様）ができるでしょうか。
ただし、人生の始まりの地点から、決して下がらないとしてください。
例えば、ｎ＝１場合は、（登り、下り）は良いですが、（下り、登り）は起こらないとします。したがって、１通り。
ｎ＝２場合は、（登り、登り、下り、下り）、（登り、下り、登り、下り）は良いが、
（登り、下り、下り、登り）、（下り、下り、登り、登り）などは起こらないとします。
したがって、２通りのライフライン（人生模様）があることになります。
問題１：ｎ＝３の場合は、何通りのライフライン（人生模様）になるか。
問題２：ｎ＝４の場合は、何通りのライフライン（人生模様）になるか。
問題３：一般に、何通りのライフライン（人生模様）になるか。ｎで示してください。
NO1「H7K」さん 3/31: 21時01分 受信 更新4/15
(微かな記憶を辿り)カタラン数では．
以下，(n,r)=nCrとします．
1. C_3=(6,3)/4=5.
2. C_4=(8,4)/5=14.
3. C_k=(2n,n)/(n+1).
NO2「Kashiwagi」さん 4/03: 08時36分 受信 更新4/15
第117回解答
今、登りを○、下りを×で表すと
問１.
ｎ＝３の場合は○×合計６個のものを並べる順列、ないし、６個の中から３個を選ぶ組み合わせだから、６C３＝２０通りである。
このうち、最初に×のくる組み合わせ１０個と×の連続で○より×の数が先行する組み合わせ５個を引くと、求めるものは５個となる。
問２.
ｎ＝４の場合も同様にして、８C４＝７０通りである。このうち題意に適さない組み合わせは
５６個であるので、求めるものは１４個である。
問３.
ところで、ｎ＝１の場合は２通りのうち１個、ｎ＝２の場合は６通りのうち２個である。
この４つの事例を良く見ると、
求める組み合わせ／全部の組み合わせ＝１／（ｎ＋１）となっている事が分かる。因って、
求める組み合わせ＝全部の組み合わせ／（ｎ＋１）となる。
これより、ｎの場合は
２ｎCｎ／（ｎ＋１）が求めるものである。
＜「Kashiwagi」さんから＞今回の問題の一般解の美しさには感嘆致しました。問題文の事例を分かりにくくしているのはこの解答に至るためだったと気づきました。こ
れは試行錯誤で見つけられたのですか？それとも有名な定理なのですか。
＜水の流れ＞今回は、カタラン数の本質を知っていれば、身近な出来事と結びつけて作問できます。
過去の応募問題で このカタラン数になる応募問題は
「大縄飛び」」
http://www2.ocn.ne.jp/~mizuryu/kadai/kadai36a.html
「正２ｎ角形」
http://www2.ocn.ne.jp/~mizuryu/kadai/kadai44a.html
「机の積み方」
http://www2.ocn.ne.jp/~mizuryu/kadai/kadai59a.html
後、「釣り銭」の問題もあります。
で、ときどき 作問しています。お立ち寄りください。ライフラインとか人生模様なってのは私の飾り言葉にしか過ぎませんけど。
NO3「toru」さん 4/04: 09時34分 受信 更新4/15
第１１７回解答
問題１ 登り：A 下り：BとしてAAABBB、 AABABB、AABBAB、ABAABB、ABABABの５通り。
問題２ 同様にAAAABBBB、AAABABBB、AAABBABB、AAABBBAB、AABAABB、AABABABB、
AABABBAB、AABBAABB、AABBABAB、ABAAABBB、ABAABABB、ABAABBAB、ABABAABB、
ABABABABの１４通り。
問題３ 登り、下りの順に条件がないとすると2nＣn通り。このうち条件に合わないものは、
左から見ていった場合（Bの数）＞（Aの数）となる点が存在する。
A：n個B：n個 計２n個の並びのうち（Bの数）＞（Aの数）となる点があるものの集合をＵとし、
A：n-1個 B：n+1個、計２n個のの並びを集合をＶとする。Ｕから任意の並びuをとり、
初めて（Bの数）＞（Aの数）となった点より後ろのＡとＢを入れ替えて
できた並びをvとすると、uは初めて（Bの数）＞（Aの数）となった点より前では、
（Bの数）＝（Aの数）＋１、それより後ろでは（Ａの数）＝（Bの数）＋１なので、
ここのAとBを入れ替えることでvは Ａ：n-1個 B：n+1個の並びとなり、vはＶの要素である。
さらにu≠u’なら明らかにv≠v’ だから、（Ｕの要素の数）≦（Ｖの要素の数）--?。逆にＶから任意の並びをとっても、必ず（Bの数）＞（Aの数）となる
点が存在し、初めてそうなった点より後ろのAとBを入れ替えることで全く同じ議論で（Ｕの要素の数）≧（Ｖの要素の数）---?が示される。??より
（Ｕの要素の数）＝（Ｖの要素の数）＝2nＣn-1。 これから、求めるライフラインの数は
2nＣn−2nＣn-1=(2n)!／n!n!−(2n)!／(n-1)!(n+1)!=(2n)!／n!(n+1)!=2nCn／(n+1)
これはカタラン数ですね、カタラン数の一般項の求め方はいくつかあるようです。上記は、私のオリジナルでは全然ありませんが、
以前に格子の一点から一点までの最短距離で対角線より下へ出ない、下へ出たものは、そこで折り返して、一対一対応だか
ら、と書いてあるのを読んで何か騙されたような気分になっていたのを、少しアレンジして、もう少し厳密にまた図がなくても分かるように書いたつもりですが、
くどいと言われそうですね。 ペンネーム Toru
NO4「浜田」さん 4/07: 14時58分 受信 更新4/15
次の通り．エクセルのマクロで解きました．GRAPESで調べたところ，６次以下のｎの整式で表す事は出来ないようです．
n 組合せ
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
Option Explicit
Const n_MAX As Integer = 13 '********
Sub Macro1()
Sheets("Sheet1").Select
Dim a(n_MAX * 2) As Integer
Dim n As Integer
For n = 1 To n_MAX
Cells(n, 1).Value = n
Cells(n, 2).Value = 0
Call saiki(n, 1, a())
Next n
End Sub
Sub saiki(ByVal n As
Integer, ByVal m As Integer, ByRef
a() As Integer)
Dim takasa As Integer
Dim b(1) As Integer
Dim j As Integer
a(m) = -1
While a(m) <= 1
takasa = 0
For j = 0 To 1
b(j) = 0
Next j
For j = 1 To m
takasa = takasa + a(j)
If a(j) = -1 Then
b(0) = b(0) + 1
Else
b(1) = b(1) + 1
End If
Next j
If takasa >= 0 And
b(0) <= n And b(1) <= n Then
If m < n * 2 Then
Call saiki(n,
m + 1, a())
Else
Cells(n, 2).Value =
Cells(n, 2).Value + 1
End If
End If
a(m) = a(m) + 2
Wend
End Sub
NO5「UnderBird」さん 4/09:
12時51分 受信 更新4/15
カタラン数についての詳しい解説が次のＨＰにあります。
http://www80.sakura.ne.jp/~aozora/taiwa/node85.html
今回この解説以上の解答は私には無理でしたので、ご紹介（もしかしたらこのＨＰを
知っていらっしゃるかも知れませんが）させていただくのみでお願いします。
＜水の流れ＞そうです。あまり見てはいませんが、このサイトを開いたことはあります。
参考になりますね。でも、あまり研究はしていませんが、
私のサイトでは、以下にあります。
http://www2.ocn.ne.jp/~mizuryu/jyugyo/bokansu3.htm
http://www2.ocn.ne.jp/~mizuryu/jyugyo/suugaku21.html
NO６「中川幸一」さん 4/14:
19時40分 受信 更新4/15
今回は図形を描いたので一太郎で作りました。
問題3の解答をかなり手抜きしてしまいました。
求め方等は他の人がしてくれていると思いますが, もし誰もしていないようでし
たら改めてメールをお送りします。
NO７「午年のうりぼう」さん 4/15: 23時58分 受信 更新4/20
第１１７回数学的な応募問題 ［人生模様］
（解答）
|
ｎ |
１ |
２ |
３ |
４ |
… |
ｎ |
|
|
図１（通り） |
１ |
２ |
５ |
１４ |
… |
Ｎ |
|
|
|
↓×２ |
↓×３ |
↓×４ |
↓×５ |
… |
↓×（ｎ＋１） |
|
|
図２（通り） |
２Ｃ１＝２ |
４Ｃ２＝６ |
６Ｃ３＝２０ |
８Ｃ４＝７０ |
… |
２ｎＣｎ＝ |
表 １
問題文の「人生模様」を図１のように表す。ただし、この「人生模様」は右上または右
下にのみ進めるとする。また、「地下」に潜ることを認めるとすると、「人生模様」は図
２のように表すことができる。ただし、この「人生模様」は右上または右下にのみ進める
とする。ここで、図１中の丸数字はその地点まで行く「人生模様」の数を表している。
表１は、図１と図２との関係をまとめたものである。
問題１．
表１により、５通り。…（答）
問題２．
表１により、１４通り。…（答）
問題３．
表１により、 
…（答）
NO８ 「ＲＡＲＡちゃん」 4/16: １０時４７分 受信 更新4/20
問題１の答え：５とおり
問題２の答え：１９とおり
問題３の考え：
２進数とみなして、
登り＝１、くだり＝０として人生の前半に＋を溜め込まないとつらいらしい。
後半の人生は前半に照らしあわせて、下記のように最低でも１，０が反対のならべかたとそれ以上の数の組み合わせのような気がします。すべてのケースの洗い出しは自力では難しくてできない。
例えば前半１１００なら後半は”００１１”とそれ以上の
|
”０１０１ |
”０１１０ |
”１００１ |
”１０１０ |
”１１００ |
まるで自分のことのように思えて感慨深いです。お邪魔しました。
