Question

某市A有四个郊县B、C、D、E．（如图）现有5种颜色，若要使每相邻的两块涂不同颜色，且每块只涂一种颜色，问有多少种不同的涂色方法？

Answer

根据题意，分析可得符合题意的涂色至少要3种颜色，分3种情况讨论：①用5种颜色涂，②用4种颜色涂，③有3种颜色涂，由排列公式计算可得每种情况的涂色方法数目，进而由分类计数原理，计算可得答案．
【解析】
根据题意，A、B、C三个区域两两相邻，则符合题意的涂色至少要3种颜色，
分3种情况讨论：
①用5种颜色涂，有A55=120种涂色方法，
②用4种颜色涂，必须是A、B、C颜色互不相同，D或E用第四种颜色，最后一个区域与所对的区域同色，
则有C54•C41•C21•C32•A22=240种涂色方法，
③有3种颜色涂，必须是A、B、C颜色互不相同，D与B颜色相同，C与E颜色相同，
则有C53•A33=60种涂色方法，
由分类计数原理，共有不同的涂色方法120+240+60=420种．
答：不同的涂色方法有420种．