Đăng nhập Đăng ký

ID: 13878

Vận dụng cao (M4)
Cho một đa giác đều có $\displaystyle 20$ đỉnh ( $\displaystyle n \geq 3$ ). Ta dùng $\displaystyle 3$ màu (Xanh, Đỏ, Vàng) để tô màu các đỉnh của đa giác này sao cho hai đỉnh kề nhau luôn có màu khác nhau. Hỏi có bao nhiêu cách tô màu?

`1`
Giải thích đáp án:
Đây là bài toán tô màu đồ thị vòng (Cycle Graph) $\displaystyle C_n$ với $\displaystyle k$ màu.
Gọi $\displaystyle P(n)$ là số cách tô màu đa giác $\displaystyle n$ đỉnh thỏa mãn điều kiện.
Ta có công thức tổng quát (Đa thức sắc số cho đồ thị vòng):
$\displaystyle P(n) = (k-1)^n + (-1)^n \cdot (k-1)$
Áp dụng với $\displaystyle n = 20$ (số đỉnh) và $\displaystyle k = 3$ (số màu):
$\displaystyle P(20) = (3-1)^{20} + (-1)^{20} \cdot (3-1) = 2^{20} + 1 \cdot 2 = 1048576 + 2 = 1048578$

để xem lời giải của câu hỏi này

Câu hỏi cùng chủ đề

Chưa có câu hỏi