Answer for Number of Cases [ t]

TAROSITE.NET: COLUMN | INFO

Answer for Number of Cases

by TARO MATSUMURA @taromatsumura 2004.11.10 00:26

　さて先週の末に思い出して勢いでエントリーした「場合の数」の最短経路の数の問題ですが、このまま放置しておくのも何なので解答編エントリーを書くことにします。メールやメッセンジャーで直接「70と50でしょ」と教えてくれた12人の方、正解です。ありがとうございます、付き合って頂いて。別に何ら難しい問題というわけではないし、凝った解法をするわけではないのです。足し算だから。

・tarosite.net: Number of Cases

　小学生なのでそんな複雑なことをさせるわけでもないし、僕はどちらかというと算数・数学が苦手なので、力業というか、図形的にというか、そういう格好で解答できる算数の問題が好きだった、ただ単にそれだけの話なのだ。多分これから示す解法よりももっと良い答えの求め方があると思うけれど、とりあえず僕が小学校の時にやった解き方をご紹介。

　最短経路を求める、と言う問題なので、まずAから右へ各交点に1、下へ同じく各交点に1と書いていく。つまりそれらの交点へ行く最短の行き方は1通りという事だ。次に左上から順に中の交点を見ていく。1つ前の、A点に近い交点同士の数字を足し算して、その交点に書く。つまり1の点と1の点から交わるところには2、1と2なら3と言った具合だ。

　（1）については単純にこのルールに従って説いていくことで、70と答えが出てくる。

（1）
Baai 2

　（2）の場合は、×印のすぐ右の点へ行く場合、通常なら2と1を足して3だが、2の点からくることはできないため、上の1だけそのままおろしてきて1となる。その後は同じように足し算を続けていくだけだ。そうすると50通りになる。

（2）
Baai 4

　ここまでが前回のエントリーの解答編だ。個々まではまあどんな方法でも説くことができるし、難しい問題ではない。しかし小学校の頃、以下のようなバリエーション違いの問題からいろいろと気づきを得ていたことを思い出した。とても簡単な話なのですが、なにぶん小学生の思考なのでご勘弁を。最後まで読んで怒らないで下さいね。

　例えば×印で通れない箇所が図の中の方の1辺ではなく、図の端の点であったらどうなるか。その場合は以下のようになる。

（3）
Baai 5

　（2）と同じように1カ所通れなかっただけなのだが、（2）の50通りではなく55通りという計算になった。これはいったいどういう事なのか。そのことをもう少しわかりやすくとらえるために、今度は辺ではなく点が使えないという問題にしてみる。つまり点の周りの辺はアクセスできないと言うことになる。これを同様に解いていくと以下のようになる。

（4）
Baai 6

　そしてまた、使えない点が図の端の点であった場合は以下の通りだ。

（5）
Baai 9

　やはりかなりの数字の変化が生まれてくる。

　とまあ個々まで書いてきて自分でもわざとらしいなと思ったんだけれど、つまるところその点が他の何点とつながれているかによって最短経路の数が変化すると言うことだ。こういうのを小学校の頃に興味を持ってたくさん問題をやったというのは、例えその理由が解法で使うのが足し算だけだったからだとしても、なんだか今の自分の糧になっているような気がしてならない。とくにSFCなんかにいたりすると。

　では、最後の問題。これまでと同様にAからBへの最短経路を求めるのですが、×印は使えません。

（6）
Baai 8