-
356
重要 例題 16 塗り分けの問題 (1) 積の法則
***
00000
A
B
ある領域が,右の図のように6つの区画に分けられている。境界
を接している区画は異なる色で塗ることにして,赤・青・黄・白の
4色以内で領域を塗り分ける方法は何通りあるか。〔類 東北学院大]
基本7
D
F
指針 塗り分けの問題では、まず特別な領域 (多くの領域と隣り合う,同色が可能)に着
目するとよい。 この問題では,最も多くの領域と隣り合うCDでもよい)に着目し
C→A→B→D→E→F
の順に塗っていくことを考える。
A, B, D, E の4つの
域と隣り合うCから
り始める。
DE F
C→A→B→D→E→F
解答の順に塗る。
C→A→Bの塗り方は
4P3=24 (通り)
この塗り方に対し,D,E,F の
塗り方は2通りずつある。
よって、 塗り分ける方法は全部
で 24×2×2×2=192(通り)
C→A→B→D→E→F
4 × 3 × 2 × 2 × 2 × 2
...Cの色を除く
B 2.CとAの色を除く
F 2…DとEの色を除く
E 2.CとDの色を除く
2.CとBの色を除く
注意 上の解答では, 積の法則を使って解いたが, 右のように
樹形図を利用してもよい。 なお, 右の樹形図は,Cが赤,
Aが青, Bが黄で塗られているときのものである。
黄
青
・白<
白く
青
4色すべてを用いる場合の塗り分け方
上の例題では,「4色以内」で領域を塗り分ける方法を考えたが,「4色すべてを用いて」
検討
り分ける方法を考えてみよう。
この領域を塗り分けるには、最低でも3色が必要であるから
(4色すべてを用いる塗り分け方) = (4色以内の塗り分け方) (3色を用いる塗り分け方
により求められる。
ここで, 3色で塗り分ける方法の数を調べると
[C, F] → [A, D]→[B,E] ([] は同じ色で塗る領域)の順に塗る方法は
3P3=6(通り)
4色から3色を選ぶ (=使わない1色を選ぶ) 方法は
ゆえに
6×4=24 (通り)
4通り
よって, 4色すべてを用いる塗り分け方は 192-24=168 (通り)
練習 右の図の A, B, C, D, E 各領域を色分けしたい。隣り合った
③ 16 領域には異なる色を用いて塗り分けるとき, 塗り分け方はそれ
ぞれ何通りか。
(1)4色以内で塗り分ける。
(2) 3色で塗り分ける。
(3) 4色すべてを用いて塗り分ける。
A
B
C
DE
[類 広島修道大] p.358 EXliv