Giải Bài toán tô màu các hình vuông
I . Bài toán: (Nhiều phụ huynh HS đau đầu )
Zing vn đưa ra bài toán của trang fuzzle: Cho lưới ô vuông 4/4, hãy dùng 5 màu tô hết các ô vuông nhỏ sao cho các ô nhỏ ở hàng ngang, hàng dọc và cả hàng chéo liền nhau mà không trùng màu.
*Đáp án I
*Đáp án II
ô
*Cách giải
- Người ta đã chứng minh rằng: Với điều kiện bài toán trên thì số màu tối thiểu là 5 (nếu 4 mầu thì bớt 1 đk ; xem phần tham khảo);
chỉ có 1 màu cho 4 ô, còn lại 4 màu thì mỗi màu cho 3 ô cộng = 16 ô
- Giả sử ta có 5 màu 1=đỏ; 2=hồng; 3=lam; 4=vàng; 5=lục
Ta sẽ dùng đỏ 4 ô; hồng, lam vàng, lục 3x4 ô
- Chia ô vuông thành 2 phần: Vòng ngoài 12 ô;
Phần lõi có 4 ô như hình bên
- Màu đỏ tô 4 ô: chỉ có các ô vòng ngoài mà không nằm ở đỉnh (đó là A2-C1-D3-B4 hoặc A3-B1-D2-C4)
- 
Cách chọn ô tô màu tiếp theo luôn giống như nước đi quân Mã (trong cờ tướng)
- Tô 4 ô vòng lõi theo 4 màu còn lại, ta có 4 cách chọn
- Từ 4 phương án trên, chọn tiếp cũng theo “nước đi quân Mã” mỗi màu lại có 2 cách đi ,
- Do đó tổng số ta có 4x2x2 = 16 đáp án thỏa mãn
II. Bài toán tham khảo Tô màu bản đồ
Trên các bản đồ, các miền khác nhau (miền ở đây được hiểu là các quốc gia trên bản đồ thế giới hay các tỉnh trong một bản đồ hành chính quốc gia) được tô màu sao cho 2 miền có chung biên giới không trùng màu nhau. Đối với bản đồ có nhiều miền, nếu ta dùng một số lượng lớn màu thì sẽ rất khó phân biệt các miền có màu gần giống nhau, vì thế người ta chỉ dùng một số lượng màu nhất định để tô màu bản đồ. Một bài toán được đặt ra là: có thể dùng ít nhất bao nhiêu màu để tô màu một bản đồ sao cho các miền kề nhau không cùng một màu[2] (tr.593).
Bài toán này dẫn đến định lý bốn màu nổi tiếng và định lý năm màu[3]. Các dạng bài toán tô màu bản đồ có thể áp dụng Thuật toán tô màu Greedy để tìm ra số màu ít nhất để tô cho các miền trên bản đồ.
- Định lý bốn màu (còn gọi là định lý bản đồ bốn màu) phát biểu rằng: đối với bất kỳ mặt phẳng nào được chia thành các vùng phân biệt, chẳng hạn như bản đồ hành chính của một quốc gia, chỉ cần dùng tối đa bốn màu đủ để phân biệt các vùng lân cận với nhau. Hai vùng được coi là lân cận nếu như chúng có chung nhau một đoạn đường biên, không tính chung nhau một điểm.
- Định lý năm màu (còn gọi là định lý bản đồ năm màu): Là một kết quả từ Lý thuyết đồ thị, cụ thể là mọi bản đồ đều có thể tô bằng năm màu sao cho hai nước nằm kề nhau phải được tô bằng hai màu khác nhau.
Mặc dù đây là định lý yếu hơn định lý bốn màu, nhưng cách chứng minh này cũng đóng vai trò quan trọng bởi vì đây là cơ sở bước đầu để thiết lập cách chứng minh trọn vẹn cho định lý bốn màu mà phải kiểm tra bằng chương trình máy tính.
PHH sưu tầm đề & biên soạn bài giải 10 – 10 - 2016
