Hai bài toán bốn màu của Anh và Trung Quốc

[sunshine1104]

Hai bài toán của Anh và Trung Quốc cùng chung chất liệu nhưng khác ở câu hỏi khiến bài của Anh mất cả trăm năm để giải, bài còn lại chỉ cần kiến thức lớp 5 trong 5 phút.

Toán tối ưu là một chuyên ngành Toán học với đặc tính dùng cái "tối thiểu" để xử lý được "tối đa". Một trong các ví dụ tiêu biểu là bài toán 4 màu ra đời cách đây 170 năm và phải mất 124 năm mới được giải quyết trọn vẹn.

Tháng 4/1852, nhà toán học Francis Guthrie phát hiện có thể tô màu bản đồ nước Anh bằng 4 màu. Tháng 10/1852, giáo sư De Morgancủa (Đại học London) đã viết thư cho đồng nghiệp William Hamilton để bàn về bài toán: "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".

Năm 1878, nhà toán học Arthur Cayley đã giới thiệu vấn đề này trước công chúng. Một năm sau, Alfred Kempe là người đầu tiên chứng minh bài toán. Năm 1880, Peter Guthrie Tait đưa thêm một cách chứng minh. Nhưng đến năm 1890, Percy Heawood đã chỉ ra sai lầm trong cách chứng minh của Kempe và năm 1891, Julius Petersen chỉ ra sai lầm trong cách chứng minh của Tait.

Giai đoạn 1960-1970, nhà toán học người Đức Heinrich Heesch đã dùng máy tính để chứng minh. Năm 1976, định lý được chứng minh hoàn toàn bởi Kenneth Appel và Wolfgang Haken tại trường Đại học Illinois với sự trợ giúp 1.000 giờ của máy tính. Sau đó nhà khoa học John A. Koch đã cải tiến thuật toán để giải quyết trọn vẹn bài toán 4 màu sau 124 năm ra đời.

Mặc dù định lý được phát hiện ra trong quá trình tô màu bản đồ, trên thực tế nó rất ít khi được áp dụng vào khoa học vẽ bản đồ. Những người vẽ bản đồ cho rằng họ quan tâm hơn đến việc phối màu bản đồ sao cho đẹp mắt; do vậy việc sử dụng bốn, năm hay nhiều màu hơn không phải là vấn đề đáng bận tâm.

Một cách tiếp cận khác là đếm số khả năng tô 4 màu khác nhau trên một hình vẽ thu hẹp. Năm 2003, một bài toán trồng hoa 4 màu trong đề thi tuyển sinh đại học Gaokao của Trung Quốc có rất ít thí sinh làm được, tuy nhiên có thể hóa giải nó bằng kiến thức lớp 5.

Đề 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"?