Đề bài:
Có bao nhiêu cách để trồng 4 loại hoa có 4 màu sắc xanh, đỏ, tím, vàng lên một mảnh đất được chia thành 6 khu 1, 2, 3, 4, 5, 6 như hình vẽ sao cho: "Mỗi khu đất chỉ trồng 1 loại hoa và 2 khu đất có chung nhau một đoạn ranh giới phải trồng 2 loại hoa khác màu nhau"?
Lời giải:
Xét 2 trường hợp sau đây:
Trường hợp 1: Miền 4 và 6 có cùng 1 màu như hình vẽ trong đề bài.
Có 4 cách chọn 1 màu để dùng cho cặp miền (4, 6) giống nhau.
Có 3 x 2 x 1 = 6 cách dùng 3 màu cho 3 miền (1, 2, 3) khác màu (4, 6).
Có 2 cách để chọn màu miền 5 khác màu với miền 1 và cặp (4, 6).
Vậy trường hợp 1 có 4 x 6 x 2 = 48 cách trồng 4 loại hoa cho 6 miền.
Trường hợp 2: Miền 4 và miền 6 khác màu nhau.
Bốn miền (1, 4, 5, 6) có 4 x 3 x 2 x 1 = 24 cách tô 4 màu khác nhau.
Mặt khác miền 2 khác màu với miền 1 và miền 6 nên suy ra:
+ Nếu miền 2 giống màu miền 5 thì miền 3 giống màu miền 6.
+ Nếu miền 2 giống màu miền 4 thì miền 3 giống màu 5 hoặc 6.
Từ đó suy ra có 24 x 3 = 72 cách trồng 4 loại hoa cho 6 miền.
Kết luận:
Từ trường hợp 1 và 2 ta có 48 +72 =120 cách trồng hoa 4 màu.
Bình luận:
Bài toán 4 màu của Trung Quốc nếu không biết phân loại dựa trên ý tưởng then chốt: "Hai miền 4 và 6 khác màu nhau hay có cùng 1 màu như nhau" thì sẽ không thể tìm đúng đáp số.
Trước đó, vào năm 1852, bài toán 4 màu của Anh với nội dung "Mọi bản đồ đều có thể tô bằng 4 màu sao cho hai nước có đường biên giới chung được tô hai màu khác nhau" khiến người giải phải mất 124 năm và 1.000 giờ máy tính mới chứng minh được. Nhưng từ sự tồn tại 1 cách tô màu chuyển sang xác định tất cả cách tô 4 màu cho bản đồ thế giới thì con người sẽ phải "bó tay" nếu không có sự trợ giúp của máy tính. Và ngay cả khi sử dụng lập trình, con người cũng phải mất vài năm mới có thể tìm được tất cả các cách tô 4 màu.
Trần Phương