Đáp án bài toán tô màu cho ngũ giác

Đề bài: 

Cho một hình ngũ giác ABCDE. Với 3 màu xanh, đỏ, vàng, có bao nhiêu cách tô màu cho 5 cạnh của ngũ giác này sao cho không có hai cạnh liền kề nào trùng màu với nhau?

Hình minh họa

Đáp án: 30 cách tô màu.

- Chọn AB là cạnh đầu tiên để tô màu, ta có 3 cách tô cho cạnh này (vì có 3 màu).

- BC và EA là hai cạnh liền kề với AB nên chúng chẳng thể cùng màu với AB, cơ mà có thể cùng màu với nhau. Ta chia thành hai hoàn cảnh:

Trường hợp 1: Hai cạnh BC và EA cùng màu.

Ta có hai cách tô màu cho BC và EA (chỉ cần màu đó khác màu cạnh AB).

Màu cần tô vào hai cạnh còn lại CD và DE sẽ trừ đi màu đã tô ở BC, EA và chúng cũng khác màu nhau. Từ đó ta có 2 x 2 - 2 = 2 cách tô màu cho hau cạnh này.

Như vậy, số cách tô màu cho cả hình ngũ giác ở hoàn cảnh 1 là 3 x 2 x 2 = 12 cách.

Trường hợp 2: Hai cạnh BC và EA khác màu.

Ta có 2 x 2 - 2 = 2 cách tô màu cho hai cạnh BC và EA (vì có thể tô 2 màu khác màu của AB vào hai cạnh này cơ mà phải trừ đi hoàn cảnh hai cạnh có màu giống nhau ở hoàn cảnh 1).

Cả 3 màu đều có thể tô vào cạnh CD và DE cơ mà màu CD phải khác màu BC nên chỉ có hai màu để tô. DE phải khác màu EA nên cũng chỉ còn hai màu để tô. Hai cặp màu tô cho DE và CD chắc chắn có một màu giống nhau, mà DE và CD kề nhau nên phải trừ đi hoàn cảnh chúng cùng màu nhau. Từ đó suy ra số cách tô CD và DE là 2 x 2 - 1 = 3 cách

Như vậy, số cách để tô màu cho cả hình ngũ giác ở hoàn cảnh 2 là
3 x 2 x 3 = 18 cách.

Cộng hai hoàn cảnh đã xét lại, ta có tổng số cách tô màu cho hình ngũ giác này sao cho thích hợp với điều kiện của tựa đề là 12 + 18 = 30 cách.

Thanh Tâm