NGƯỜI CHẠY CÔ ĐƠN CUỐI CÙNG CŨNG CÓ THÊM KHOẢNG TRỐNG

Hãy tưởng tượng một đường đua hình tròn dài một vòng. Vài người chạy xuất phát từ cùng một điểm vào cùng một thời điểm, mỗi người với một tốc độ không đổi của riêng mình, tất cả đều khác nhau. Giả thuyết người chạy cô đơn (lonely runner conjecture) nói rằng mỗi người chạy, vào một lúc nào đó, sẽ thấy mình đơn độc: cách tất cả những người khác ít nhất 1/(n + 1) vòng, khi tổng cộng có n + 1 người chạy.

Bài toán này còn cũ hơn cả cái tên của nó. Theo Xiyu Hu (Đại học Viện Hàn lâm Khoa học Trung Quốc) và Yifan Jing (Đại học Bang Ohio), nó bắt nguồn từ luận án tiến sĩ năm 1965 của Jörg Wills về xấp xỉ các số bằng phân số. Cusick đưa ra một phiên bản tương đương dưới dạng các tầm nhìn bị chướng ngại vật che khuất; những người chạy xuất hiện sau đó, với một cách phát biểu lại của Goddyn. Từ đó nó được liên hệ với quỹ đạo bi-a, tô màu đồ thị và các dòng chảy trong những cấu trúc trừu tượng gọi là matroid.

Đo sự cô đơn

Các nhà toán học thường cố định một người chạy và xét tốc độ của những người khác so với người đó: một tập V gồm n số nguyên dương khác nhau. Tại thời điểm t, một người chạy có tốc độ v ở vị trí vt quanh đường đua, và khoảng cách của người đó tới điểm xuất phát được viết là ∥vt∥ — khoảng cách từ vt đến số nguyên gần nhất. Độ cô đơn cực đại của V là

ML(V) = max theo t của min theo v thuộc V của ∥vt∥

Thời điểm tốt nhất, được đánh giá theo người chạy gần nhất. Giả thuyết khẳng định ML(V) ≥ 1/(n + 1), và cận này là chặt: với các tốc độ 1, 2, …, n, độ cô đơn cực đại đúng bằng 1/(n + 1). Chẳng hạn, với hai người chạy ở tốc độ 1 và 2, người chạy cố định có thể cách cả hai tối đa một phần ba vòng — tại thời điểm 1/3.

Một nửa dễ dàng

Một nửa câu trả lời có được khá dễ. Những thời điểm một người chạy nhất định ở trong phạm vi δ quanh điểm xuất phát chiếm một tỉ lệ 2δ của thời gian. Với n người chạy, nếu 2nδ nhỏ hơn 1, các cửa sổ thời gian này không thể phủ kín mọi thứ, nên có một thời điểm nằm ngoài tất cả. Cho δ tăng đến giới hạn, ta được

ML(V) ≥ 1/(2n)

Con số đó gần bằng một nửa những gì giả thuyết dự đoán. Vượt qua nó hóa ra rất gian nan. Các tác giả liệt kê lịch sử: suốt nhiều thập kỷ, chỉ có những cải thiện cỡ 1/n²; rồi những cải tiến của Perarnau và Serra, của Terence Tao năm 2018, của Benjamin Bedert năm 2025. Nhưng tất cả đều chung một điểm yếu: so với 1/(2n), phần cải thiện tiến về không khi số người chạy tăng lên.

Một phần cải thiện không phai

Định lý mới thay đổi điều đó:

ML(V) > (1 + c)/(2n)

với một hằng số cố định c > 0 và mọi tập gồm n ≥ 2 tốc độ. Phần biên dư nay là một tỉ lệ không đổi của cận dễ, bất kể có bao nhiêu người chạy. Hằng số này tường minh nhưng không được tính ra trong bài báo, và các tác giả không cố gắng tối ưu nó. Nó chưa đạt đến 1/(n + 1) như giả thuyết; đó là phần cải thiện đầu tiên không tan biến.

Chứng minh xét cách các “cửa sổ nguy hiểm” của những người chạy khác nhau chồng lên nhau. Một số chồng lên nhau vì có chung tâm — những người chạy có tốc độ chung ước số cùng chạm điểm xuất phát một lúc. Số khác chồng lên nhau ở các tâm khác nhau. Với loại thứ nhất, các tác giả tinh chỉnh một lập luận về các ước chung lớn của Green và Walker. Với loại thứ hai, họ chứng minh một bất đẳng thức hình học mới: khi các cửa sổ được nới rộng quanh tâm của chúng, phần chồng lấn phải tăng nhanh hơn tỉ lệ thuận. Đằng nào thì phần thời gian không bị phủ cũng không thể co lại về không.

Thêm vào đó, kết quả này cải thiện một cận dưới cho “bài toán bộ đồ ngủ” (pyjama problem): cần bao nhiêu bản sao đã xoay và kéo giãn của một họa tiết sọc để phủ kín mặt phẳng.

Ai làm gì

Bài báo có một tuyên bố rõ ràng về việc sử dụng AI. Chiến lược và khung lập luận là của chính các tác giả. ChatGPT 6 Pro và ChatGPT 6 Astra chủ yếu được dùng để kiểm tra lập luận, biến các chứng minh không chính thức thành chứng minh chặt chẽ và khám phá các tinh chỉnh. Pro đã gợi ý đưa vào các tổng theo ước chung, và sau đó sửa “một vài lỗ hổng nhỏ” trong phiên bản đầu của chứng minh bất đẳng thức then chốt. Các chứng minh cuối cùng do các tác giả viết. Nhận định của họ về các công cụ rất chính xác: “các mô hình không thể tự mình cải thiện cận của bài toán người chạy cô đơn.”

Sáu mươi năm sau Wills, sự cô đơn mà mỗi người chạy được bảo đảm, lần đầu tiên, có một biên dư không mất đi.