15: Đó là đáp án cho một bài toán cực kỳ phức tạp vừa được giải bởi một nhóm hai người tại Đại học Carnegie Mellon (CMU). Thông thường, các bài toán lớn, phức tạp và khó giải đều có đáp án cồng kềnh và gần như khó hiểu với người ngoài ngành. Nhưng không phải trường hợp này.
Bài toán, ban đầu được đặt ra vào năm 2008, như sau: Nếu bạn có một mạng lưới ô vuông vô hạn - giống như một tờ giấy kẻ ô vuông mở rộng vô tận - và bạn muốn lấp đầy nó bằng những con số sao “khoảng cách taxi” của 2 ô số giống nhau gần nhất phải lớn hơn số đó, thì số lượng số khác nhau tối thiểu là bao nhiêu? Ở đây, “khoảng cách taxi” là số ô vuông sắp xếp theo đường thẳng và vuông góc nối 2 ô số giống nhau gần nhất. Đây được gọi là bài toán “tô màu bao bì”.
Ví dụ, hai số 1 không thể ở ngay cạnh nhau, bởi vì “khoảng cách taxi” của chúng sẽ chỉ là một ô vuông. Nhưng chúng có thể nằm chéo nhau, bởi vì “khoảng cách taxi” của chúng sẽ là hai - một sang bên và một lên hoặc xuống. Quy tắc tương tự áp dụng cho tất cả các số khác. Sau đây là video ngắn bằng tiếng Anh giải thích về bài toán, bạn đọc có thể mở phụ đề và chọn dịch để xem.
Bạn có bối rối không? Nếu vậy thì cũng bình thường. Bài toán này đã khiến các nhà toán học hàng đầu phải mất hơn một thập kỷ mới giải quyết được, và nó không thể thực hiện được nếu không có sức mạnh tính toán mạnh mẽ của máy tính và sự sáng tạo.
Theo một bài báo trên Quanta Magazine, bộ đôi đã giải quyết bài toán - sinh viên tốt nghiệp CMU Bernardo Subercaseaux và giáo sư Marijn Heule của CMU - ban đầu đã thu hẹp danh sách các đáp án tiềm năng xuống chỉ còn 13, 14 hoặc 15. Nhưng các đáp án này đã đã được một nhóm khác đạt được vài năm trước đó, và Subercaseaux và Heule muốn có một câu trả lời thực sự chứ không phải một loạt các khả năng. Vì vậy, họ đã sử dụng sức mạnh tính toán mạnh mẽ của máy tính. Ngoài ra, để loại trừ một câu trả lời tiềm năng, họ phải đảm bảo rằng họ đã thử mọi cách kết hợp vị trí của các số.
Thật không may, điều đó mất rất nhiều thời gian để làm, ngay cả đối với một máy tính cực kỳ mạnh mẽ và tiên tiến. Vì vậy, các nhà nghiên cứu cần thêm một chút sáng tạo. Họ phát hiện ra rằng, các câu trả lời đối xứng là như nhau. Phản chiếu toàn bộ lưới sẽ không thay đổi kết quả, nhưng nó sẽ tăng gấp đôi khối lượng công việc mà máy tính phải thực hiện. Vì vậy, họ đã thực hiện quy tắc “không quan tâm đến các kết quả đối xứng” và có thể loại trừ số 13, chỉ giữ lại số 14 và 15.
Nhưng mỗi khi con số được thử nghiệm lớn hơn, quá trình tính toán lại mất nhiều thời gian hơn. Ngay cả khi áp dụng quy tắc “không quan tâm đến các kết quả đối xứng”, việc tính toán để kiểm tra số 14 sẽ mất quá nhiều thời gian để Subercaseaux và Heule hài lòng. Ngoài ra, nhà toán học Alexander Soifer của Đại học Colorado nói với Quanta Magazine rằng bộ đôi này không chỉ muốn giải quyết vấn đề một cách thô bạo mà còn muốn “giải quyết nó theo một cách ấn tượng”.
Cuối cùng, Subercaseaux và Heule nhận ra rằng nếu họ để máy tính xem xét các khối không gian cùng nhau thay vì từng ô vuông riêng lẻ, thì việc tính toán sẽ hiệu quả hơn rất nhiều. Vì vậy, họ chia không gian thành các dấu cộng được tạo từ 5 ô vuông và để máy tính kiểm tra từng dấu cộng để tìm lỗi đỏ thay vì từng ô vuông.
Và chỉ trong chốc lát, máy tính đã chạy thử nghiệm và báo động với số 14. Chỉ để lại 15 làm phương án và đó cũng là đáp án.
Bạn có thể sẽ không bao giờ gặp phải một mạng lưới vô hạn cần được lấp đầy theo những điều kiện rất cụ thể trong cuộc sống thực, nhưng việc giải quyết các bài toán như thế này không phải lúc nào cũng nhằm mục đích tạo ra khám phá có thể áp dụng trong thế giới thực. Đối với Subercaseaux, đó là thắng lợi thực sự đầu tiên trong sự nghiệp nghiên cứu của anh. Và mặc dù đó có thể không phải là kiểu khám phá mà anh dự tính làm đầu tiên trong khi nghiên cứu toán học, nhưng cuối cùng thì anh cũng nhận thấy rằng nó có những phần thưởng trí tuệ của riêng nó.
Subercaseaux cho biết: "Đó không phải là hiểu biết dạng tôi chỉ cần một bảng đen và tôi có thể cho bạn thấy tại sao đó là số 15. Nhưng chúng tôi đã đạt được sự hiểu biết về cách các ràng buộc của một bài toán hoạt động, cách một số 6 ở đây hoặc một số 7 ở đó có thể tốt hơn. Chúng tôi đã đạt được rất nhiều hiểu biết trực quan”.
Theo Popularmechanics
Văn Thiện biên dịch
