Thế nào là bài toán bản đồ có bốn màu?

Năm 1852, Côxuri tốt nghiệp đại học ở Luân Đôn. Khi vẽ bản đồ, ông nhận thấy: với một tấm bản đồ, chỉ cần dùng tối đa bốn màu là có thể tô đủ để phân biệt các quốc gia có chung biên giới, tức các quốc gia có chung đường biên sẽ không cùng màu.

Ông liền đặt câu hỏi cho các anh em của mình đang công tác ở trường đại học: liệu có thể chứng minh được điều đó không?

Các anh em của ông hỏi nhà toán học Morgan. Morgan thừa nhận rằng ông không thể phán đoán được đúng sai.

Thoạt nhìn, bài toán bốn màu khá đơn giản. Bạn chỉ cần lấy một tấm bản đồ chưa tô màu và chuẩn bị bốn loại màu. Trước hết, bạn tô một quốc gia nào đó, ví dụ màu đỏ; sau đó tô các quốc gia lân cận bằng các màu khác. Theo “nguyên tắc bốn màu”, bạn sẽ thấy các quốc gia có biên giới chung có màu khác nhau.

Quả thật việc đó có thể thực hiện khá dễ dàng. Tuy nhiên, đó chỉ là kiểm chứng, không phải chứng minh toán học. Vấn đề bản đồ bốn màu được đặt ra như một bài toán là một phán đoán chung, không chỉ nói về một tấm bản đồ cụ thể nào, mà khái quát cho bất kỳ bản đồ nào được vẽ trên giấy. Tấm địa đồ ở đây có thể là bản đồ thực, cũng có thể là bản đồ tưởng tượng, thậm chí kể cả những hình mà người ta chưa từng nghĩ đó là bản đồ. Cũng có người nghĩ đến các tấm bản đồ mà nếu không đủ năm màu thì không thể tô được.

Như vậy có thể thấy, bài toán bản đồ bốn màu tưởng như đơn giản nhưng chứng minh lại rất khó. Về sau, bài toán bốn màu cùng với định lý lớn Fermat và bài toán Goldbach được xem là ba bài toán khó lớn của thời cận đại.

Năm 1879, Kempe tuyên bố đã chứng minh được bài toán bốn màu. Mười một năm sau, nhà toán học Heawood chỉ ra rằng cách chứng minh của Kempe có chỗ không chặt chẽ, nên chứng minh ấy không được chấp nhận. Heawood đã ứng dụng phương pháp của Kempe và chứng minh được rằng chỉ cần năm màu là có thể tô được bản đồ thế giới sao cho các quốc gia có biên giới chung không trùng màu. Bài toán này có tên là “bài toán năm màu”.

Từ đầu thế kỷ XX trở lại đây, nhiều nhà toán học đi theo con đường của Kempe để nghiên cứu bài toán bốn màu và đã thu được nhiều thành tựu. Người ta chứng minh rằng để giải bài toán này, không thể chỉ nghĩ đến một tấm bản đồ đã vẽ sẵn, mà phải nghĩ đến vô số tấm bản đồ có thể vẽ ra. Kiểm nghiệm một số lượng bản đồ lớn như vậy là công việc có khối lượng quá sức người và rất khó thực hiện.

Năm 1970, đã có phương án dùng máy tính điện tử để giải bài toán này, và người ta đã phải tính toán suốt 11 năm mới tìm được kết luận.

Sau năm 1970, nhiều người tiếp tục cải tiến phương án giải bài toán bốn màu. Cùng với tốc độ tính toán của máy điện toán tăng nhanh, khả năng giải bài toán bốn màu bằng máy tính đã mở ra rõ rệt.

Năm 1976, hai nhà toán học Hoa Kỳ là Appel và Haken đã dùng ba máy điện toán khác nhau, mất đến 1200 giờ để hoàn chỉnh chứng minh định lý về bài toán bốn màu.

Bài toán bốn màu từ khi được đặt ra cho đến khi phát triển thành định lý đã trải qua 120 năm làm việc liên tục của nhiều thế hệ nhà toán học mới hoàn thành. Cho đến ngày nay, nhiều nhà khoa học vẫn đang tìm kiếm một lời giải hoàn toàn bằng tính toán trên giấy.