ホーム >> 組合せ >> $5$ つの領域の塗り分け
hide or visible

問題の説明

組合せ分野の,標準的な塗り分け問題です.この手の問題は一度は解いたことがあるのではないでしょうか.

考え方・ヒント

まず簡単にわかることは,領域は $5$ つなので使う色の種類は $5$ 色以下です.さらに $3$ 色以上必要であることもすぐにわかります.(たとえば,左上と右上を異なる色で塗り分けたとき,真ん中の領域を塗るには $3$ 色目が必要です)
したがって,使う色の種類は $3,4,5$ 色のいずれかなので,それぞれの場合に場合分けして考えるのが自然でしょう.

あとはどの領域から順番に塗っていくかを考えなければいけませんが, 塗り分けの問題では隣接している領域の数が多い領域から塗っていくとうまくいくことが多いです.その方が制約が多くなって,考えるべき状況が制限されやすくなるからです.

解説

使う色の数で場合分けして考えます.

($i$) $5$ 色で塗り分ける場合
領域の数は $5$ つなので,この場合は,それぞれの色はひとつの領域しか塗らないことに注意します.(つまり,一度使った色はもう使いません)
まず,真ん中の領域を塗る色は $10$ 通りあります.そのそれぞれの場合について,右上を塗る色の種類は (まだ選んでない色の) $9$ 通り,そのそれぞれについて,右下を塗る色の種類は $8$ 通り,そのそれぞれについて左下を塗る色の種類は $7$ 通り,そのそれぞれについて左上を塗る色の種類は $6$ 通りあります.よってぜんぶで, $$10\times 9\times 8\times 7\times 6$$ 通りです.

($ii$) $4$ 色で塗り分ける場合
まず,真ん中の領域を塗る色は $10$ 通りあります.それぞれの場合について,右上を塗る色の種類は $9$ 通り,そのそれぞれについて,右下を塗る色の種類は $8$ 通りあります.ここまでは ($i$) と同じです.さてここまでの $3$ 箇所が適当に塗られた状況で,左下を塗る色を考えます.左下は,まだ塗られてない色で塗るか,右上で塗った色と同じ色で塗るかのいずれかの場合があります.
領域の塗り分け
前者の場合は,左下を塗る色の種類が $7$ 通りあり,それぞれの場合について,左上の領域は右下で塗られた色と同じ色で塗るしかないので,自動的に決まります.
また,後者の場合は,左下を塗る色は右上と同じで自動的に決まり,左上を塗る色の種類は (まだ選んでない色の) $7$ 通りあります.
領域の塗り分け
結局,このときの場合の数は $$10\times 9\times 8\times 7\times 2$$ 通りです.

($iii$) $3$ 色で塗り分ける場合
まず,真ん中の領域を塗る色は $10$ 通りあります.それぞれの場合について,右上を塗る色の種類は (まだ選んでない色の) $9$ 通り,そのそれぞれについて,右下を塗る色の種類は $8$ 通りあります.ここまでは ($i$),($ii$) と同じです.さて,ここまでの $3$ 箇所が適当に塗られた状況を考えると,使える色は $3$ 色しかないので,左下は右上と同じ色で,左上は右下と同じ色で塗るしかありません.
領域の塗り分け
つまり,$3$ 箇所の色を選べば自動的に塗り分けが決定します.したがって,このときの場合の数は $$10\times 9\times 8$$ 通りです.

最後に,($i$)〜($iii$) の状況はいずれも同時に起こらず,そのうえすべての起こりうる状況を尽くしているので,求めるべき場合の数は $$10\times 9\times 8\times 7\times 6+10\times 9\times 8\times 7\times 2+10\times 9\times 8$$ $$=720(1+14+42)=41040$$ よって,$\boxed{41040}$ 通りです.


最後の足し算において,それぞれ掛け算を計算してから足すのではなく,分配法則でまとめて計算した方が楽で賢いやり方です.場合分けした時点で,それぞれの場合の数を最終的に足すことは予想できます.したがって,それぞれの場合の数を一回一回計算せずに $10\times 9\times 8\times 7\times 2$ などのようにあえて計算せずにおいておく工夫は重要な戦略です.