|
uchinyan |
|
こんにちは。今回は少し苦労しました。皆さん、すごいですね。
最初見たときは、簡単そうだったのですが、頭の中で考えているうちに図形というかグラフがこんがらがってきて、 地道に、島の数、点の数、が、n=2から積み上げてみよう、と思いました。 基本的に、皆さんも書いていますが、島を点、橋を線で表し、対象となるグラフを考えます。また、グラフを、 (グラフの中の点の総数; 線が1本出ている点の数, 線が2本出ている点の数, 線が3本出ている点の数, ...) で書くことにします。ただし、点が二つの場合の(2;2,0,0,0,...)など、明らかに後ろに0が並ぶ場合には、 (2;2)と書くことにします。 また、このグラフの個数を、f(2;2)などと書くことにします。また、グラフの総数をf(2)などと書きます。 以下、少し長くなります。ご容赦を。 * n=2 の場合 (2;2)だけで、f(2) = f(2;2) = 1通り です。 * n=3 の場合 三つの点のうち、二つを選んでそれにn=2の場合を適用し、三つ目の点をそれにつなげることを考えます。 こうしてできるグラフは、(3;2,1)だけです。これを、 (2;2) -> (3;2,1) と書きます。このとき、点の総数が一つ増え、線が1本出ている点をつなげることになるので、 線が1本出ている点が、元のグラフから一つ減り、新たに一つ増え、線が2本出ている点が一つ増えます。 この規則性は重要です。 グラフの個数は、二つの点を選ぶのに3通り、n=2がf(2;2)通り、つなげるのに2通り、ですが、出来上がったグラフは、 「−−○」の付け方で2通りの重複があることに注意します。この重複の数は、線が1本出ている点の数に対応します。 したがって、 f(3;2,1) = 3 * f(2;2) * 2 * 1/2 = 3 なので、 f(3) = f(3;2,1) = 3通り です。 * n=4 の場合 同様に、n=3のグラフに1点を追加することを考えます。 1本線が出ている点に追加する場合は2通りあって、1本線が出ている点は一つ減り一つ増えて変化なし、 2本線が出ている点は一つ増えます。これを次のように書きます。 (3;2,1) -> (4;2,2) * 2 2本線が出ている点に追加する場合は1通りで、今度は、1本線が出ている点が一つ増え、2本線が出ている点が一つ減り、 3本線が出ている点が一つ増えるので、 (3;2,1) -> (4;3,0,1) * 1 これだけです。 したがって、 f(4;2,2) = 4 * f(3;2,1) * 2 * 1/2 = 12 1/2をかけるのを忘れずに！ f(4;3,0,1) = 4 * f(3;2,1) * 1 * 1/3 = 4 今度は、f(4;3,0,1)なので、線が1本出ている点の数は3で、1/3になります。 結局、 f(4) = f(4;2,2) + f(4;3,0,1) = 16通り * n=5 の場合 同様に計算します。 (4;2,2) -> (5;2,3) * 2 or (5;3,1,1) * 2 (4;3,0,1) -> (5;3,1,1) * 3 or (5;4,0,0,1) * 1 (5;3,1,1)が二箇所から違う重みで現れることに注意です。 したがって、 f(5;2,3) = 5 * f(4;2,2) * 2 * 1/2 = 60 f(5;3,1,1) = 5 * (f(4;2,2) * 2 + f(4;3,0,1) * 3) * 1/3 = 60 f(5;4,0,0,1) = 5 * f(4;3,0,1) * 1 * 1/4 = 5 よって、 f(5) = 60 + 60 + 5 = 125通り これが今回の答えです。 ここまでくると、グラフが、(5;2,3), (5;3,1,1), (5;4,0,0,1)しかないことが分かるので、 皆さんのような解法も可能です。 なお、以上の計算は、更に続けることが可能です。 * n=6 の場合 (5;2,3) -> (6;2,4) * 2 or (6;3,2,1) * 3 (5;3,1,1) -> (6;3,2,1) * 3 or (6;4,0,2) * 1 or (6;4,1,0,1) * 1 (5;4,0,0,1) -> (6;4,1,0,1) * 4 or (6;5,0,0,0,1) * 1 f(6;2,4) = 6 * f(5;2,3) * 2 * 1/2 = 360 f(6;3,2,1) = 6 * (f(5;2,3) * 3 + f(5;3,1,1) * 3) * 1/3 = 720 f(6;4,0,2) = 6 * f(5;3,1,1) * 1 * 1/4 = 90 f(6;4,1,0,1) = 6 * (f(5;3,1,1) * 1 + f(5;4,0,0,1) * 4) * 1/4 = 120 f(6;5,0,0,0,1) = 6 * f(5;4,0,0,1) * 1/5 = 6 f(6) = 360 + 720 + 90 + 120 + 6 = 1296通り * n=7 の場合 (6;2,4) -> (7;2,5) * 2 or (7;3,3,1) * 4 (6;3,2,1) -> (7;3,3,1) * 3 or (7;4,1,2) * 2 or (7;4,2,0,1) * 1 (6;4,0,2) -> (7;4,1,2) * 4 or (7;5,0,1,1) * 2 (6;4,1,0,1) -> (7;4,2,0,1) * 4 or (7;5,0,1,1) * 1 or (7;5,1,0,0,1) * 1 (6;5,0,0,0,1) -> (7;5,1,0,0,1) * 5 or (7;6,0,0,0,0,1) * 1 f(7;2,5) = 7 * f(6;2,4) * 2 * 1/2 = 2520 f(7;3,3,1) = 7 * (f(6;2,4) * 4 + f(6;3,2,1) * 3) * 1/3 = 8400 f(7;4,1,2) = 7 * (f(6;3,2,1) * 2 + f(6;4,0,2) * 4) * 1/4 = 3150 f(7;4,2,0,1) = 7 * (f(6;3,2,1) * 1 + f(6;4,1,0,1) * 4) * 1/4 = 2100 f(7;5,0,1,1) = 7 * (f(6;4,0,2) * 2 + f(6;4,1,0,1) * 1) * 1/5 = 420 f(7;5,1,0,0,1) = 7 * (f(6;4,1,0,1) * 1 + f(6;5,0,0,0,1) * 5) * 1/5 = 210 f(7;6,0,0,0,0,1) = 7 * f(6;5,0,0,0,1) * 1 * 1/6 = 7 f(7) = 2520 + 8400 + 3150 + 2100 + 420 + 210 + 7 = 16807通り ．．． お気づきかどうか．．． f(2) = 1 = 2^0 = 2^(2-2) f(3) = 3 = 3^1 = 3^(3-2) f(4) = 16 = 4^2 = 4^(4-2) f(5) = 125 = 5^3 = 5^(5-2) f(6) = 1296 = 6^4 = 6^(6-2) f(7) = 16807 = 7^5 = 7^(7-2) ... 恐らく、一般に、 f(n) = n^(n-2) です :-) 証明できるかなぁ。上記の方法では、ちょっと難しいか。 P.S. 上記の関係を発見してニンマリだったのですが、まるケンさんの#23207にご指摘がありました。 有名な問題なのですね。きっと。 |
|
7月1日（木） 17:18:37
23215 |