Tóm tắt nội dung: Chuyên đề hệ thống hóa lý thuyết và phương pháp giải dạng bài toán tô màu trong Tổ hợp - Xác suất phục vụ ôn thi THPT Qu...
Tóm tắt nội dung: Chuyên đề hệ thống hóa lý thuyết và phương pháp giải dạng bài toán tô màu trong Tổ hợp - Xác suất phục vụ ôn thi THPT Quốc gia và ĐGNL. Nội dung bao gồm kỹ thuật tô màu chu trình, hình chóp, bảng ô vuông kích thước \(2 \times n\) và \(m \times n\), cùng các ví dụ minh họa đếm số cách tô thỏa mãn điều kiện kề nhau khác màu.
A. LÝ THUYẾT VÀ PHƯƠNG PHÁP GIẢI
1. Xác định những cặp phải khác màu
- Tô đỉnh: Hai đỉnh phải khác màu nếu có cạnh nối chúng.
- Tô mặt hoặc tô bản đồ: Hai mặt phải khác màu nếu chung cạnh. Hai vùng phải khác màu nếu chung đường biên.
- Tô ô vuông: Đọc kỹ đề yêu cầu khác màu khi chung cạnh hay cả khi chung đỉnh.
Chú ý: Mỗi vị trí được tô đúng một màu. Các màu đã cho có thể được dùng lại ở những vị trí không bị ràng buộc.
2. Chu trình, hình chóp và các cặp đối diện
- Chu trình: Tô \(n \ge 3\) đỉnh theo vòng kín bằng \(k \ge 2\) màu có \((k - 1)^n + (-1)^n(k - 1)\) cách.
Nếu cắt một cạnh, đường đi còn \(k(k - 1)^{n-1}\) cách tô. Trừ các cách có hai đầu cùng màu để khép vòng. - Hình chóp hoặc vùng trung tâm: Tô đỉnh chóp, mặt đáy hoặc vùng trung tâm trước tùy đề. Các vị trí bao quanh tạo thành một chu trình và chỉ còn \(k - 1\) màu.
- Mặt lập phương và đỉnh bát diện: Chia thành ba cặp đối diện. Hai vị trí cùng cặp có thể cùng màu. Hai vị trí khác cặp luôn phải khác màu. Chọn số cặp dùng hai màu rồi gán các màu phân biệt vào các vị trí hoặc cặp đã gộp.
3. Tô bảng ô vuông
Bảng \(2 \times n\), chỉ xét cạnh chung: Cột đầu có \(k(k - 1)\) cách tô.
Với cột trước đã tô, mỗi ô ở cột mới tránh màu của ô bên trái nó. Trong \((k - 1)^2\) cặp màu, có \(k - 2\) cặp trùng màu.
Vậy mỗi cột mới có \(k^2 - 3k + 3\) cách. Khi đề hỏi màu các ô cụ thể, giữ lại điều kiện đó trong lúc đếm từng cột.
Bảng \(m \times n\), xét cả đỉnh chung: dùng đúng bốn màu cho phép. Mỗi khối \(2 \times 2\) phải có đủ bốn màu.
- Mã hóa bốn màu bằng \((0, 0)\), \((0, 1)\), \((1, 0)\), \((1, 1)\), cộng từng tọa độ theo modulo 2. Trong mỗi khối \(2 \times 2\), tổng bốn mã bằng \((0, 0)\).
- Vì vậy, độ đổi màu ngang chỉ phụ thuộc cặp cột, độ đổi màu dọc chỉ phụ thuộc cặp hàng. Hai loại độ đổi phải khác \((0, 0)\) và không được trùng nhau.
- Có ba độ đổi khác \((0, 0)\). Do hai nhóm dùng các độ đổi rời nhau, ít nhất một nhóm chỉ dùng một giá trị. Đếm hai trường hợp rồi trừ phần trùng, thu được:
\[12(2^{m-1} + 2^{n-1} - 2), \quad m, n \ge 2.\]
Không gian mẫu: Nếu mỗi vị trí chọn độc lập và đều trong \(k\) màu, có \(k^N\) kết quả với \(N\) vị trí. Nếu chọn đều trong các cách tô hợp lệ, mẫu số là số cách tô hợp lệ.
B. VÍ DỤ MINH HỌA
Ví dụ 1 (TME): Cho hình chóp tứ giác \(S.ABCD\) có đáy \(ABCD\) là một hình vuông. Người ta dùng 6 màu sơn khác nhau để sơn 5 đỉnh của hình chóp sao cho mỗi đỉnh được sơn đúng một màu và hai đỉnh bất kỳ được nối với nhau bởi một cạnh của hình chóp thì có màu khác nhau. Hỏi có tất cả bao nhiêu cách sơn màu các đỉnh của hình chóp?
Ví dụ 2 (TME): Người ta sơn ngẫu nhiên 5 đỉnh của hình chóp tứ giác \(S.ABCD\) bằng 6 màu sơn (mỗi đỉnh chọn ngẫu nhiên một trong 6 màu).
Gọi \(P\) là xác suất để việc sơn màu thỏa mãn quy tắc: hai đỉnh bất kỳ nối với nhau bởi một cạnh thì có màu khác nhau. Tính \(T = 6480 \cdot P\).
Ví dụ 3 (TME): Cho một đa giác đều 6 cạnh (lục giác đều) \(A_1A_2A_3A_4A_5A_6\). Người ta dùng 5 màu sắc khác nhau để tô 6 đỉnh của đa giác sao cho hai đỉnh kề nhau bất kỳ (nối bởi một cạnh của lục giác) có màu khác nhau. Hỏi có tất cả bao nhiêu cách tô màu đa giác?
