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ẽ địa đồ, ô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ác quốc gia có chung biên giới, tức là màu của các quốc gia có chung biên giới sẽ không giống nhau.

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

Các anh em của ông liền hỏi nhà toán học Môcan, Môcan thừa nhận là ông ta 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 có thể tô một quốc gia nào đó ví dụ màu đỏ, sau đó bạn tô các quốc gia lân cận bằng các màu khác và theo “nguyên tắc bốn màu” bạn sẽ thấy quốc gia có biên giới chung sẽ có màu khác nhau, không giống nhau.

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

Như vậy có thể thấy bản đồ bốn màu tưởng như đơn giản, mà chứng minh thì lại rất khó. Sau này bài toán bản đồ bốn màu cùng với định lí lớn Fecma (Fermat) và bài toán Gôn bach (Goldbach) được xem là ba bài toán khó lớn của thời cận đại.

Năm 1879, Kenpu 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 Haut (Hawood) chỉ ra rằng, cách chứng minh của Kenpu có chỗ không chặt chẽ, nên cách chứng minh đương nhiên không được chấp nhận. Haut đã ứng dụng phương pháp của Kenpu và chứng minh được rằng, cần có năm màu thì có thể tô được bản đồ thế giới để cho các quốc gia có biên giới chung không bị 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 Kenpu để nghiên cứu giải bài toán bốn màu và đã thu được nhiều thành tựu. Người ta chứng minh là để giải bài toán này ta không chỉ nghĩ đến một tấm bản đồ đã vẽ sẵn mà phải nghĩ để vẽ ra vô số tấm bản đồ. Để kiểm nghiệm số lớn bản đồ như vậy quả là một việc có khối lượng lớn quá sức người và khó thực hiện được.

Vào 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 11 năm liên tục mới tìm được kết luận.

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

Vào năm 1976, hai nhà toán học Hoa Kì là Apin (Apeil) và Hakan (Hakan) đã dùng ba máy điện toán khác nhau và đã dùng đến 1200 giờ để hoàn chỉnh việc chứng minh định lí về bài toán bốn màu.

Bài toán bốn màu từ khi đặ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ệ các nhà toán học mới được hoàn thành. Cho đến ngày nay, nhiều nhà khoa học vẫn đang tìm kiếm lời giải bằng tính toán trên mặt giấy.