|
uchinyan |
|
はい、こんにちは。
今回は、まずは、地道に解いて、漸化式でもできそうだったので、それも考えてみました。 (解法1) 地道な方法です。 まず、明らかに、塗る色は、3色か4色でないとダメです。 ・3色の場合 3色を選ぶのに 4 通り、アを選ぶのに 3 通り、イを選ぶのに 2 通り、は、すぐに分かります。問題はウとオの塗り方です。 同じ色の場合は、アともイとも違う色を塗ることになり 1 * 1 通りで、このとき、エが 2 通り。 異なる色の場合は、エは 1 通りで、オがイと同じ場合は、ウは 2 通り、オがイと違う場合は、ウは 1 通りです。 そこで、4 * 3 * 2 * (1 * 1 * 2 + (1 * 2 * 1 + 1 * 1 * 1)) = 120 通りになります。 ・4色の場合 アを選ぶのに 4 通り、イを選ぶのに 3 通り、は、すぐに分かります。ウとオの塗り方がやはり問題になります。 同じ色の場合は、アともイとも違う色を塗ることになり 2 * 1 通りですが、このとき、エは、4色を使うという条件から 1 通りです。 異なる色の場合は、オがイと同じ場合は、やはり4色を使うという条件からウは 2 通りになり、エが 1 通りで、1 * 2 * 1 通り、 オがイと違う場合は、ウがアと同じときには、やはり4色を使う条件からエが 1 通りで 2 * 1 * 1 通り、 ウがアと違うときには、エが 2 通りで 2 * 1 * 2 通りになります。 そこで、4 * 3 * (2 * 1 * 1 + (1 * 2 * 1 + 2 * 1 * 1 + 2 * 1 * 2)) = 120 通りになります。 以上ですべてなので、120 + 120 = 240 通り。 (解法2) 漸化式を考えます。 一般に、円を、区別する n 個の区画に分けて 4 色で塗り分ける場合の数を a(n) とします。 すると、a(n) は、 n-1 の場合の区画を分ける線のところを切り開いて新たな区画を追加するか、 n-2 の場合の区画の一つの中を二つに切り開いて新たな区画を追加するか、 のいずれかになります。 このとき、どの部分を切り開くかは、対称性により区別する必要はありません。 (要するに、「ア、イ、ウ、エ」に「オ」を追加する場合、「ア、イ、ウ、エ、オ」と「ア、イ、ウ、オ、エ」とは、 単に文字の付け方の差しかなく、二つの区画は同じものです。) 線のところを切り開く場合には両側の色は異なるので 2 通りの、 区画の中を切り開く場合には両側の色は同じなので 3 通りの色の区画を追加できます。 そこで、次の漸化式が成立します。 a(n) = 2 * a(n-1) + 3 * a(n-2) ただし、初期条件が微妙で、n = 1, 2, 3 の場合は、区画の追加が一部しか成立せず、 a(1) = 4, a(2) = 3 * a(1) = 12, a(3) = 2 * a(2) = 24 となります。したがって、先ほどの漸化式は、n >= 4 で成立します。これから、 a(4) = 2 * a(3) + 3 * a(2) = 2 * 24 + 3 * 12 = 48 + 36 = 84 a(5) = 2 * a(4) + 3 * a(3) = 2 * 84 + 3 * 24 = 168 + 72 = 240 となり、240 通りになります。 なお、高校レベル？(多分、普通の高校生にはちょっと難しいかも．．．)ですが、n >= 4 で、 a(n) + a(n-1) = 3 * (a(n-1) + a(n-2)) = ... = 3^(n-3) * (a(3) + a(2)) = 4 * 3^(n-1) a(n) - (-1) * a(n-1) = 4 * 3^(n-1) (-1)^n * a(n) - (-1)^(n-1) * a(n-1) = 4 * (-1)^n * 3^(n-1) より、漸化式は解けて、 a(n) = 3^n + (-1)^n * 3, n >= 4 となります。これと、a(1), a(2), a(3) とを比較すると、 a(1) = 4, a(n) = a(n) = 3^n + (-1)^n * 3, n >= 2 が、一般解になります。 |
|
ネコの住む家
5月19日（木） 14:44:49
MAIL:uchi@sco.bekkoame.ne.jp 25105 |