|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
この問題，問題文が若干あいまいかも知れません。「１４マスすべてを通って」はいいのですが，１度通ったマス目はもう１度は通らない，ですよね。 そうしないと同じマス目を通って無限ループにもなり得るので。まぁ，明らかではあるのですが，明記した方がいいかも。 それもあってか正解率は低いですね。もっともそれ抜きでも，算チャレでも標準的か最近の傾向ではやや難，世の中的には難しい方でしょうか。 私は数学的になってしまいますが漸化式で解きました。図を使い例示すれば小学生にも説明はできるだろうと思います。 というわけで，こんな感じ。 まず，１度通ったマス目はもう１度は通らない，という隠れた条件があります。 そうしないと同じマス目を通って無限ループにもなり得て意味がない場合が可能になってしまうからです。 そこで，以下ではこの条件を大前提として考えます。 横 2 マス，縦 n マスの場合の数を a(n) 通りとします。S からは，右，上，右上，に行けます。 (1) S から右に行く場合 次に行けるのは，左上，上，のいずれかです。 左上に行くときは，縦が n-1 マスになるので a(n-1) 通り， 上に行くときは，縦が n-1 マスで出発位置が左ではなく右になりますが，左右二つの G のどちらをゴールにしてもいいので， 出発位置が左の場合と対称で場合の数は同じ a(n-1) 通りになります。 そこで，結局，この場合は，a(n-1) * 2 通り，です。 (2) S から上に行く場合 次に行けるのは，上，右上，右，右下，のいずれかです。 上，右上，右，に行くときは，１度通ったマスをもう１度通らずに 右下 ＝ S の右 に行き再び上には行けないので，不可。 右下に行くときは，その上 ＝ S の右上 に行くしかなく，これはこの後 (1) の縦 n-1 マスの場合と同じになるので a(n-2) * 2 通りです。 そこで，結局，この場合は，a(n-2) * 2 通り，です。 (3) S から右上に行く場合 次に行けるのは，左上，上，左，下，のいずれかです。 左上，上，左，に行くときは，１度通ったマスをもう１度通らずに 下 ＝ S の右 に行き再び上には行けないので，不可。 下に行くときは，その左上 ＝ S の上 に行くしかなく，これはこの後 (1) の縦 n-1 マスの場合の対称パターンと同じになるので a(n-2) * 2 通りです。 そこで，結局，この場合は，a(n-2) * 2 通り，です。 以上ですべてなので，結局，a(n) = a(n-1) * 2 + a(n-2) * 4，です。 これより，実際に調べて，a(1) = 1，a(2) = a(1) * 2 + 1 + 1 = 4，より，求めるのは a(7) なので， a(3) = a(2) * 2 + a(1) * 4 = 4 * 2 + 1 * 4 = 8 + 4 = 12， a(4) = a(3) * 2 + a(2) * 4 = 12 * 2 + 4 * 4 = 24 + 16 = 40， a(5) = a(4) * 2 + a(3) * 4 = 40 * 2 + 12 * 4 = 80 + 48 = 128， a(6) = a(5) * 2 + a(4) * 4 = 128 * 2 + 40 * 4 = 256 + 160 = 416， a(7) = a(6) * 2 + a(5) * 4 = 416 * 2 + 128 * 4 = 832 + 512 = 1344， そこで，求める場合の数は，1344 通り，になります。 実は，漸化式はあっさりと求まったものの，つまらない計算ミスでしばし首を傾げていたのは，内緒 (^^; |
|
ネコの住む家
11月5日（木） 18:01:38
43871 |