|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
一見して，領域 1 と領域 7 が異なる色か同じ色かで領域 8 の塗り方が変わってくるのが分かります。 そこで，「あー，これは漸化式っぽいな。」ということで，こんな感じになりました。 領域が 2 個の場合：明らかに，3 * 2 = 6 通り。 領域が 3 個の場合：明らかに，3 * 2 * 1 = 6 通り。 領域が 4 個の場合： 領域 1 と領域 3 が異なる色の場合の領域 1 〜 領域 3 の塗り方は，領域が 3 個の場合の塗り方と同じで，6 通り。 領域 1 と領域 3 が同じ色の場合の領域 1 〜 領域 3 の塗り方は，領域が 2 個の場合の塗り方と同じで，6 通り。 (領域 1 と領域 3 とをくっつけてしまえは，領域が 2 個で異なる色で塗り分ける場合になります。) そして，領域 4 に塗る塗り方は，領域 1 と領域 3 が異なる色の場合は 1 通り，領域 1 と領域 3 が同じ色の場合は 2 通り。 そこで，6 + 6 * 2 = 6 + 12 = 18 通り。 領域が 5 個の場合： 領域 1 と領域 4 が異なる色の場合の領域 1 〜 領域 4 の塗り方は，領域が 4 個の場合の塗り方と同じで，18 通り。 領域 1 と領域 4 が同じ色の場合の領域 1 〜 領域 4 の塗り方は，領域が 3 個の場合の塗り方と同じで，6 通り。 そして，領域 5 に塗る塗り方は，領域 1 と領域 4 が異なる色の場合は 1 通り，領域 1 と領域 4 が同じ色の場合は 2 通り。 そこで，18 + 6 * 2 = 18 + 12 = 30 通り。 以下同様で， 領域が 6 個の場合：30 + 18 * 2 = 30 + 36 = 66 通り。 領域が 7 個の場合：66 + 30 * 2 = 66 + 60 = 126 通り。 領域が 8 個の場合：126 + 66 * 2 = 126 + 132 = 258 通り。 そこで，答えは，258 通り になります。 これには 2 色で塗り分ける場合(6 通り)も含まれているのに注意ですね。 なお，数学になりますが，一応，漸化式を書いておくと， 領域 1 と領域 n が異なる色の場合を a(n) 通り，領域 1 と領域 n が同じ色の場合を b(n) 通りとして， a(1) = 0, b(1) = 3 a(n+1) = a(n) + 2 * b(n) b(n+1) = a(n) これを解くと， a(n) = 2^n + 2 * (-1)^n となるようです。 今回の問題は a(8) = 2^8 + 2 * (-1)^8 = 256 + 2 = 258 になります。 |
|
ネコの住む家
12月4日（木） 11:47:02
MAIL:uchi@sco.bekkoame.ne.jp 33411 |