|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
う〜む，今回は参った。ずーと 5 色すべて使うのだと思っていました。それでも数え間違いをしたり。 使わない色があってもいいならば，こんな感じで。 (解法1) まず，真ん中の六角形を塗るのに 5 通り。残りの 4 色以下で回りの 6 か所を塗り分ければいいです。 これは，図からして回転して同じとかはあり得ないので，次のようにして容易に漸化式が作れます。 回りが n か所で 4 色以下で塗り分けるのを a(n) 通りとすると，これは， 回りが n-1 か所の場合の二つの色を塗った境界に二つと異なる色を挟む，a(n-1) * 2 通り， 又は 回りが n-2 か所の場合の一つの色を塗った所を二つに分けて異なる色を挟む，a(n-2) * 3 通り， つまり，a(n) = a(n-1) * 2 + a(n-2) * 3，ただし，a(1) = 4，a(2) = 12，a(3) = 24，です。 そこで，a(4) = 24 * 2 + 12 * 3 = 48 + 36 = 84，a(5) = 84 * 2 + 24 * 3 = 168 + 72 = 240， a(6) = 240 * 2 + 84 * 3 = 480 + 252 = 732，となって， 求める場合の数 = a(6) * 5 = 732 * 5 = 3660 通り，になります。 (解法2) この方が分かりやすそう まず，真ん中の六角形を塗るのに 5 通り。残りの 4 色以下で回りの 6 か所を塗り分ければいいです。 これは，回りが n か所で 4 色以下で塗り分けるのを a(n) 通りとすると， 左上隅が 4 通り，その右が 3 通り，さらにその右が 3 通り，．．．，左上隅の左が 3 通り，ですが， これには左上隅と同じ色が含まれてしまっており，これは左上隅との境界を取れば a(n-1) 通りなので， a(n) = 4 * 3^(n-1) - a(n-1)，ただし，a(1) = 4，a(2) = 12，です。そこで， a(3) = 4 * 3^2 - 4 * 3，a(4) = 4 * 3^3 - 4 * 3^2 + 4 * 3，a(5) = 4 * 3^4 - 4 * 3^3 + 4 * 3^2 - 4 * 3， a(6) = 4 * 3^5 - 4 * 3^4 + 4 * 3^3 - 4 * 3^2 + 4 * 3 = 12 * (81 - 27 + 9 - 3 + 1) = 12 * 61 = 732 となって，求める場合の数 = a(6) * 5 = 732 * 5 = 3660 通り，になります。 ちなみに， 5 色全部を使う場合は，次のように考えていました。 まず，真ん中に 5 通り。残りの 4 色全部で回りの 6 か所を塗り分ければいいです。 これは，次の二つの場合しかありません。 3 か所を 1 色で塗る場合 後の 3 か所は異なる色になり，4C1 * 2 * 3! = 48 通り。 2 か所を 1 色で塗る場合 後の 4 か所のうち 2 か所を 1 色で塗り残りの 2 か所は異なる色になります。 このパターンをつまらないミスで数え間違えており苦労したのですが，結局コツコツ調べて， 4C2 * 2 * ((4C2 - 2) * 3 + 5 + 1) * 2! = 6 * 2 * 18 * 2 = 432 通り。 そこで，求める場合の数 = (48 + 432) * 5 = 480 * 5 = 2400 通り，になります。 これで掲示板に入れた，と思ったら，題意を勘違いしていたようで，疲れました。 まぁ，正解扱いになったし，いろいろと考えられたので，結果オーライですね (^^; そうそう，少し疲れたのとちょっと別件があるので， 掲示板を読むのは少し後，多分明日，になると思います。 その間に，漸化式を使わない解法も考えてみようかな。 (解法3) 漸化式を使わず 5 色全部を使う結果を使う解法 5 色全部を使う場合 上記のように 2400 通り。 4 色全部を使う場合 4 色を選ぶのに 5C4 = 5 通り，真ん中に 4 通り。 残りの 3 色全部で回りの 6 か所を塗り分けます。これは，次の二つの場合しかありません。 3 か所を 1 色で塗る場合 後の 3 か所のうち 2 か所を 1 色で塗り残りの 1 か所は残り 1 色で塗ることになります。 3C1 * 2 * 2C1 * 3 * 1 * 1 = 36 通り 2 か所を 1 色で塗る場合 後の 4 か所のうち 2 か所を 1 色で塗り残りの 1 か所は残り 1 色で塗ることになります。 (1 + 2 + 1) * 3! = 24 通り そこで，この場合は (36 + 24) * 4 * 5 = 1200 通り，です。 3 色全部を使う場合 3 色を選ぶのに 5C3 = 10 通り，真ん中に 3 通り。 残りの 2 色全部で回りの 6 か所を塗り分けます。これは，色を交互に塗るだけで 2 通り。 そこで，この場合は 2 * 3 * 10 = 60 通り，です。 2 色以下で塗り分けるのは不可能です。 これより，求める場合の数 = 2400 + 1200 + 60 = 3660 通り，になります。 |
|
ネコの住む家
12月26日（金） 14:20:36
42769 |