Tại sao tô bản đồ chỉ cần 4 màu?
Khi tô màu bản đồ, có một luật: hai vùng giáp nhau (chung một đoạn đường biên) phải khác màu, để nhìn vào là phân biệt được. Hai vùng chỉ chạm nhau ở một điểm thì được tô cùng màu. Câu hỏi: cần ít nhất bao nhiêu màu để tô được mọi bản đồ?
Câu trả lời là 4 màu. Nghe đơn giản, nhưng các nhà toán học mất 124 năm mới chứng minh được.
3 màu là không đủ
Phần tiêu đề “3 màu là không đủ”Xem bản đồ bên trái: một vùng ở giữa, ba vùng bao quanh.
Bước 1. Ba vùng bao quanh giáp nhau từng đôi một, nên phải có 3 màu khác nhau.
Bước 2. Vùng giữa giáp cả ba vùng đó, nên phải khác cả 3 màu.
Bước 3. Vậy cần màu thứ tư. Có những bản đồ mà 3 màu không đủ.
4 màu thì luôn đủ
Phần tiêu đề “4 màu thì luôn đủ”Bản đồ bên phải có 5 vùng bao quanh một vùng giữa. Năm vùng bao quanh tô xen kẽ được bằng 3 màu, vùng giữa dùng màu thứ tư. Vẫn chỉ 4 màu.
Dù vẽ bản đồ phức tạp đến đâu, với hàng trăm vùng uốn lượn, các nhà toán học đã chứng minh rằng 4 màu luôn đủ. Đó là định lý bốn màu.
124 năm đi tìm chứng minh
Phần tiêu đề “124 năm đi tìm chứng minh”- Năm 1852, một sinh viên người Anh tên Francis Guthrie tô bản đồ các hạt (giống như các tỉnh) của nước Anh và nhận thấy 4 màu là đủ. Anh đoán điều này đúng với mọi bản đồ.
- Nhiều nhà toán học giỏi đã thử chứng minh nhưng thất bại. Có người đưa ra chứng minh, 11 năm sau mới bị phát hiện là sai.
- Năm 1976, hai nhà toán học Kenneth Appel và Wolfgang Haken ở Mỹ cuối cùng cũng chứng minh được. Họ chia bài toán thành gần 2000 trường hợp, rồi dùng máy tính kiểm tra từng trường hợp, mất hơn 1000 giờ chạy máy.
Đây là định lý lớn đầu tiên được chứng minh nhờ máy tính. Lúc đầu nhiều người không chịu, vì không ai kiểm tra lại được bằng tay. Đến năm 2005, chứng minh được kiểm tra lại một lần nữa bằng phần mềm chuyên kiểm tra chứng minh toán học, và mọi người đều công nhận.
Tô màu để xếp lịch thi
Phần tiêu đề “Tô màu để xếp lịch thi”Ý tưởng tô màu được dùng trong rất nhiều việc không liên quan đến bản đồ. Ví dụ, nhà trường cần xếp lịch thi:
Bước 1. Mỗi môn thi là một “vùng”.
Bước 2. Hai môn có chung học sinh dự thi thì coi như “giáp nhau”, không được thi cùng buổi.
Bước 3. Mỗi buổi thi là một “màu”. Tô màu sao cho hai môn giáp nhau khác màu.
Bước 4. Số màu ít nhất chính là số buổi thi ít nhất cần dùng.
Các nhà mạng di động cũng làm tương tự để chọn tần số sóng cho các trạm phát gần nhau, tránh sóng bị nhiễu. Những bài toán kiểu này là một phần của lý thuyết đồ thị, một môn toán quan trọng trong tin học.
Thử tô bản đồ Việt Nam
Phần tiêu đề “Thử tô bản đồ Việt Nam”Các bạn hãy in một bản đồ các tỉnh Việt Nam và thử tô chỉ bằng 4 bút màu, sao cho hai tỉnh giáp nhau khác màu. Định lý bốn màu đảm bảo các bạn sẽ làm được, chỉ cần chịu khó thử!