Ba cách giải cho một bài toán đếm số cách tô màu đa giác

Bài này lấy trong một “đề kiểm tra chất lượng” môn toán.

Đề. Xét đa giác đều $A_1A_2..A_8$ tâm O. Chúng ta tô màu các miền tam giác $OA_iA_{i+1}$ ( $1 \leq i \leq 8, A_9 \equiv A_1$ ) bằng 4 màu khác nhau sao cho hai miền tam giác kề nhau được tô bởi 2 màu khác nhau. Hỏi có bao nhiêu cách tô màu như vậy?

Ở đây sẽ ghi lại ba cách giải, lần lượt theo thứ tự: một của đáp án, một của thằng bạn, và cuối cùng là cách giải của mình. Sau đó sẽ đến phần tổng quát và mở rộng bài toán. Nhưng trước hết sẽ là cách giải sai của mình (và một vài đứa khác) khi làm bài này trong 180 phút chính thức:

– Công đoạn 1: Tô ô $OA_1A_2$ có 4 cách

– Công đoạn 2 đến công đoạn 8: Tô 7 ô còn lại, mỗi ô 3 cách.

Như vậy theo quy tắc nhân có $4.3^7$ cách tô.

Sai chỗ nào ? Dĩ nhiên, nếu 7 ô này nằm trên một băng giấy thẳng thì cách giải trên ok, vấn đề ở chỗ ô thứ 8 và ô thứ 1 lại liền nhau, như vậy số cách tô ở ô thứ 8 không đơn giản là 3 cách.

Cách xử lý của đề: Hãy gọi số cách tô màu cho 8-giác với 4 màu như đề là P(8,4). Nếu làm như trên thì có số cách tô $4.3^7$ . Tuy nhiên chúng ta phải trừ đi số cách tô sai, khi miền tam giác $OA_8A_1$ và $OA_1A_2$ có màu giống nhau. Đối với mỗi cách tô sai, ta xem miền $OA_8A_2$ như một miền tam giác (bỏ qua đỉnh $A_1$ ), như vậy một cách tô sai này tương ứng với một cách tô đúng của đa giác 7 miền, tô bằng 4 màu.

Vậy công thức truy hồi là

$P(8,4)=4.3^7-P(7,4)=4.3^7-(4.3^6-P(6,4))=...=4(3^7-3^6+3^5-3^4+3^3)-P(3,4)$ .

Ở đây P(3,4) dễ dàng tính được, bằng 24 cách. Vậy số cách tô là 6564.

Cách giải thứ 2: Ta không đi theo thứ tự lần lượt từ ô thứ 1 đến ô thứ 8 nữa mà sẽ tô theo thứ tự như sau

B1. Tô ô 1

B2. Tô ô 2 và 8

B3. Tô ô 3 và 7

B4. Tô ô 4 và 6

B5. Tô ô 5.

Số cách tô ở mỗi bước có thể thấy qua đồ thị sau

Các mũi tên xuất phát từ cùng 1 nốt: mũi tên bên trái chỉ số trường hợp mà tại bước đó, 2 ô được tô giống màu nhau, mũi tên bên phải chỉ số trường hợp 2 ô tô khác màu nhau

Như vậy ta có tổng số cách tô là 4.(3.(3.(3.3+6.2)+6.(2.3+7.2))+ 6.(2.(3.3+6.2)+7.(2.3+7.2)))=6564

* Ai có thể tổng quát bài toán theo hướng này ? Help me !

Cách của mình. Trở lại với cách tô tuần tự từ ô 1 đến ô 8. Vấn đề xảy ra ở ô thứ 8. Giả sử ô 1 được tô màu a chẳng hạn, vậy thì nếu ô 7 cũng được tô màu a thì ô thứ 8 có đến 3 cách tô, nếu ô 7 được tô màu khác a, thì ô 8 chỉ có 2 cách tô. Xem sơ đồ sau

Ta thấy, nếu gọi số nốt (a) ở B7 là $a_7$ thì tổng số nốt (b), (c), (d) là $bcd_7=3^6-a_7$ . Và kết quả của bài toán (cũng là số nốt ở B8) là $3.a_7+2.bcd_7$ . Ta có dãy số $(a_n)$ với $a_1=1$ và $a_{n+1}=3^{n-1}-a_n$ . Từ đây suy ra $a_7=183$ .

Suy ra số cách tô là $4(3.183+2.(3^6-183))=6564$

Bài toán tổng quát: Xét đa giác đều $A_1A_2..A_m$ tâm O. Chúng ta tô màu các miền tam giác $OA_iA_{i+1}$ ( $1 \leq i \leq m, A_{m+1} \equiv A_1$ ) bằng n màu khác nhau sao cho hai miền tam giác kề nhau được tô bởi 2 màu khác nhau. Hỏi có bao nhiêu cách tô màu như vậy?

Tổng quát theo cách 1: Dãy số $P(m,n)=n.(n-1)^{m-1}-P(m-1,n)$ với cơ sở $P(2,n)=n(n-1)$

Giải dãy số trên ta được $P(m,n)=(-1)^m(n-1)+(n-1)^m (1)$

Tổng quát theo cách 3: Tổng số cách tô là $n(n-1)a_{m-1}+n(n-2)((n-1)^{m-2}-a_{m-1})$ Với $a_1=1$ , $a_{n+1}=(n-1)^{n-1}-a_n$ .

Giải dãy trên ta được tổng số cách tô giống như công thức (1) ở trên

Mở rộng: Bằng các biến đổi trong công thức dãy tính số lượng các nốt ở mỗi bước như cách 3, có thể đưa ra một bài toán mở rộng như sau: Xét đa giác đều $A_1A_2..A_6$ tâm O. Chúng ta tô màu các miền tam giác $OA_iA_{i+1}$ ( $1 \leq i \leq 6, A_{7} \equiv A_1$ ) bằng 6 màu khác nhau: $c_1$ , $c_2$ , $c_3$ , $c_4$ , $c_5$ , $c_6$ , sao cho hai màu $c_1$ và $c_2$ không được tô cạnh nhau, hai màu $c_3$ và $c_4$ , hai màu $c_5$ và $c_6$ cũng không được tô cạnh nhau . Hỏi có bao nhiêu cách tô màu như vậy?