Bài toán tô màu - hay thi trong kì thi ĐGNL, ĐGTD, THPT quốc gia

1. Có 6 ô xếp thành hàng ngang. Tô bằng 3 màu sao cho hai ô kề nhau khác màu. Có bao nhiêu cách?

Áp dụng công thức:
N = k(k - 1)^(n - 1)

Với k = 3, n = 6:

N = 3 × 2^5 = 96

---

2. Có 8 ô xếp thành hàng ngang. Tô bằng 4 màu sao cho hai ô kề nhau khác màu. Có bao nhiêu cách?

N = 4 × 3^7 = 8748

---

3. Có 5 ô xếp thành vòng tròn. Tô bằng 3 màu sao cho hai ô kề nhau khác màu. Có bao nhiêu cách?

Áp dụng công thức vòng tròn:
N = (k - 1)^n + (-1)^n (k - 1)

Với k = 3, n = 5:

N = 2^5 - 2 = 30

---

4. Có 8 ô xếp thành vòng tròn. Tô bằng 3 màu sao cho hai ô kề nhau khác màu. Có bao nhiêu cách?

N = 2^8 + 2 = 258

---

5. Có 10 ô xếp thành vòng tròn. Tô bằng 4 màu sao cho hai ô kề nhau khác màu. Có bao nhiêu cách?

N = 3^10 + 3 = 59052

---

6. Một dây đèn có 7 bóng thẳng hàng. Mỗi bóng được sơn một trong 5 màu. Hai bóng liên tiếp không được cùng màu. Hỏi có bao nhiêu cách sơn?

N = 5 × 4^6 = 20480

---

7. Một vòng cổ có 9 hạt xếp thành vòng tròn. Mỗi hạt tô bằng một trong 4 màu, hai hạt kề nhau khác màu. Có bao nhiêu cách tô?

N = 3^9 - 3 = 19680

---

8. Một hàng ghế có 12 ghế. Mỗi ghế được phủ một trong 2 màu đỏ, xanh sao cho hai ghế cạnh nhau khác màu. Có bao nhiêu cách?

N = 2 × 1^11 = 2

---

9. Một vòng tròn có 6 vị trí. Tô bằng 2 màu sao cho hai vị trí cạnh nhau khác màu. Có bao nhiêu cách?

N = 1^6 + 1 = 2

---

10. Một vòng tròn có 7 vị trí. Tô bằng 2 màu sao cho hai vị trí cạnh nhau khác màu. Có bao nhiêu cách?

N = 1^7 - 1 = 0

---

11. Có 9 ô xếp thành hàng ngang. Tô bằng 3 màu, trong đó ô đầu tiên đã cố định màu đỏ. Hai ô kề nhau khác màu. Có bao nhiêu cách?

Vì ô đầu đã cố định nên chỉ còn 2 cách cho mỗi ô sau:

N = 2^8 = 256

---

12. Có 8 ô xếp thành vòng tròn, tô bằng 3 màu và ô thứ nhất cố định màu đỏ. Có bao nhiêu cách?

Tổng số cách là:

N = (2^8 + 2) / 3 = 86