Bài toán tô màu mặt phẳng
Giả sử bạn có một tấm giấy vô cùng lớn (các nhà toán học ví nó như là một mặt phẳng). Bạn cũng có một số màu sắc khác nhau. Mục tiêu của bạn là tô màu mỗi điểm trên mặt phẳng bằng cách sử dụng màu sắc có sẵn. Tức là, mỗi điểm phải được tô bởi một và chỉ một màu sắc.
Bạn có thể tô màu mặt phẳng sao cho hai điểm bất kì cách nhau đúng 1 cm thì có màu sắc khác nhau không?
Không quá khó khăn để chứng minh rằng bạn không thể tô mặt phẳng theo cách này chỉ với 3 màu sắc (hoặc ít hơn), và có thể thực hiện được với 7 màu sắc (hoặc nhiều hơn). Nhưng không ai biết liệu có thể làm điều đó với 4, 5 hoặc 6 màu hay không. Vấn đề này được gọi là lý thuyết Ramsey
Tô màu mặt phẳng với ba màu sắc
Ta giải quyết trường hợp này bằng phương pháp phản chứng - có nghĩa là, chúng ta giả sử ngược lại, và sau đó tìm thấy một mâu thuẫn.
Thật vậy, giả sử chúng ta có thể tô màu mặt phẳng với màu đỏ, xanh dương và xanh lá cây chẳng hạn, sao cho không có hai điểm cùng màu cách nhau 1cm. Khi đó cho bất kỳ tam giác đều có cạnh 1cm, cả ba đỉnh phải được tô màu sắc khác nhau, và nếu chúng ta vẽ một hình thoi từ hai hình tam giác như vậy, các đỉnh ở hai đầu của đường chéo lớn phải được sơn cùng màu với nhau - màu đỏ chẳng hạn.
Bây giờ tưởng tượng rằng hình thoi quay xung quanh một trong các đỉnh màu đỏ của nó. Đỉnh đối diện vạch ra một đường tròn, tất cả các điểm trên đường tròn này là màu đỏ. Nhưng trên vòng tròn này có cặp điểm cách nhau 1cm, đó là một mâu thuẫn.
Tô mặt phẳng với bảy màu sắc
Hình ảnh dưới đây cho thấy một phần cách tô màu mặt phẳng với 7 màu, như vậy mà không có hai điểm nào có khoảng cách 1cm mà cùng màu.
Đường kính của mỗi hình lục giác (khoảng cách lớn nhất giữa hai điểm của nó) là 9mm. Ranh giới của hình lục giác đã được tô màu đen, tuy nhiên, điều này chỉ để các bạn dễ nhìn. Tất cả các cạnh của hình lục giác đều cùng màu với bên trong nó.
Như vậy, cần ít nhất 4 màu và nhiều nhất 7 màu để giải quyết bài toán này. Theo bạn, cần bao nhiêu màu là đủ? 4, 5, 6 hay 7?
