ある領域が,右の図のように6つの区画に分けられている。境界
例題16 塗り分けの問題 (1) …積の法則
重要
319
と接している区画は異なる色で塗ることにして,赤·青·黄 白の
人色以内で領域を塗り分ける方法は何通りあるか。
A
B
C
【類東北学院大]
D
E
基本7
F
や針>塗り分けの問題では,まず特別な領域(多くの領域と隣り合う, 同色が可能)
に着目するとよい。この問題では, 最も多くの領域と隣り合う C(Dでもよい)に着目し
1章
C→A→B→D→E→F
の順に塗っていくことを考える。
3
順
解答
列
『C→A→B→D→E→F
の順に塗る。
C→A→Bの塗り方は
Ps=24(通り)
この塗り方に対し, D, E, F の
塗り方は2通りずつある。
よって,塗り分ける方法は全部
24×2×2×2==192(通り)
C→A→B→D→E→
(A, B, D, E の4つの領域
と隣り合う Cから塗り始
4×3 ×2×2 × 2 ×
める。
D E
青
odp dop
no
白
気
で
青
注意 上の解答では, 積の法則を使って解いたが, 右のように樹形図opD 白O
を利用してもよい。なお, 右の樹形図は, C が赤, Aが青, B
が黄で塗られているときのものである。
8
検討 4色すべてを用いる場合の塗り分け方
上の例題では,「4色以内」で領域を塗り分ける方法を考えたが,「4色すべてを用いて」塗り分け
る方法を考えてみよう。この領域を塗り分けるには,最低でも3色が必要であるから (E)
(4色すべてを用いる塗り分け方)=(4色以内の塗り分け方)-(3色を用いる塗り分け方)
により求められる。ここで, 3色で塗り分ける方法の数を調べると
[C, F]→[A, D]→ [B, E]([ ]は同じ色で塗る領域)の順に塗る方法は sP:=6(通り)
4色から3色を選ぶ(= 使わない1色を選ぶ)方法は(4通り 8+m)
12
ゆえに
×4=24 (通り)
192-24=168 (通り)
よって, 4色すべてを用いる塗り分け方は
車
右の図の A, B, C, D, E各領域を色分けしたい。隣り合っ
©16
A
B
た領域には異なる色を用いて塗り分けるとき, 塗り分け方は
それぞれ何通りか。
(1) 4色以内で塗り分ける。
練習
C
D
E
(2) 3色で塗り分ける。
【類広島修道大] (p.322 EX13
Hいて塗り分ける。
F 赤白 赤 黄 赤 黄 赤 青
F 2…DとFEの色を除く一
E 2…CとDの色を除く
CとBの色を除く一
B 2…CとAの色を除く一
3…Cの色を除く
なるほど！ありがとうございます！