Tính ngẫu nhiên giúp sắp xếp các tổng không trùng nhau thế nào?

Hãy hình dung những quả bóng được tung lên với thời gian bay khác nhau nhưng không quả nào rơi đúng cùng một nhịp. Phỏng đoán do Ronald Graham đặt ra năm 1971 biến trực giác ấy thành một bài toán sắp xếp: liệu có thể xếp các số để những tổng tính từ đầu dãy không bao giờ lặp lại? Câu trả lời, trong trường hợp mô-đun nguyên tố đủ lớn, là có. Điều bất ngờ nằm ở công cụ tìm ra trật tự đó: bắt đầu bằng một thứ tự ngẫu nhiên, rồi sửa những va chạm còn sót lại. [1]

Ngẫu nhiên ở đây không tự động tạo ra đáp án hoàn hảo. Vai trò của nó là phân tán các cấu hình gây lỗi, khiến chúng đủ hiếm và đủ tách biệt để có thể xử lý. Khi các nhà toán học chứng minh xác suất gặp mọi kiểu thất bại vẫn nhỏ hơn 100%, họ đồng thời chứng minh phải tồn tại ít nhất một cách sắp xếp thành công. Đó là cốt lõi của phương pháp xác suất: dùng cơ hội để chứng minh sự tồn tại của một cấu trúc hoàn toàn xác định. [1]

Vì sao tổng từng phần có thể va chạm?

Với một dãy a₁, a₂, a₃..., tổng từng phần lần lượt là a₁, a₁+a₂, a₁+a₂+a₃... Nếu mọi số đều dương trên trục số thông thường, mỗi tổng sau lớn hơn tổng trước nên không thể trùng. Bài toán trở nên khó khi các số sống trong số học tuần hoàn: sau khi đạt một mốc p, kết quả quay lại từ đầu, gần giống kim đồng hồ đi hết một vòng. Với p = 7, chẳng hạn, 3 cộng 4 trở về 0 thay vì tiếp tục thành một vị trí mới. [1]

Hai tổng từng phần trùng nhau khi phần dãy nằm giữa chúng có tổng bằng 0 theo mô-đun p. Vì thế, yêu cầu “mọi tổng khác nhau” có thể đổi thành một yêu cầu dễ quan sát hơn: trong thứ tự đã chọn, không được có đoạn liên tiếp thích hợp nào cộng lại thành 0. Đổi cách nhìn không làm bài toán biến mất, nhưng nó chỉ đúng vị trí cần can thiệp. Thay vì so sánh từng cặp tổng, ta tìm các đoạn gây va chạm. [1]

Tại sao không dựng thứ tự theo một công thức?

Một quy tắc đơn giản như xếp số từ nhỏ đến lớn không kiểm soát được phép cộng tuần hoàn. Một đoạn trông vô hại vẫn có thể quấn qua mốc p và trở về 0. Khó khăn còn thay đổi theo kích thước tập số: tập nhỏ có nhiều vị trí trống trong thế giới mô-đun, còn tập gần phủ kín các số khác 0 lại có rất ít tự do để hoán đổi. Bởi vậy, một công thức cứng dùng chung cho mọi kích thước khó nắm bắt hết các kiểu va chạm. [1]

Có thể hình dung việc xếp lịch cho các hoạt động trên một vòng thời gian lặp lại. Xếp theo độ dài hoạt động chưa chắc ngăn hai thời điểm hoàn tất rơi vào cùng một vị trí trên vòng. Một thứ tự xáo trộn có thể tốt hơn vì nó không dồn các quan hệ đặc biệt vào cùng một vùng. Đây chỉ là phép so sánh để hiểu trực giác: đối tượng của bài toán vẫn là các phần tử và phép cộng trong một hệ mô-đun.

Ngẫu nhiên tạo ra điểm tựa ra sao?

Ở trường hợp tập số có kích thước gần bằng p, Alp Müyesser và Alexey Pokrovskiy giữ riêng một số phần tử được lựa chọn, rồi xáo trộn ngẫu nhiên phần còn lại. Nếu phát hiện một đoạn có tổng bằng 0, họ có thể chèn một phần tử dự phòng để phá vỡ đoạn đó. Thứ tự ban đầu không cần hoàn hảo; nó chỉ cần đưa cấu hình tới trạng thái mà số lỗi còn lại có thể sửa được. Công trình của họ xuất hiện năm 2022 trong một bài báo về một vấn đề tổng quát hơn. [1]

Cách làm này cho thấy hai chức năng khác nhau. Bước ngẫu nhiên phụ trách tạo một bố cục điển hình, tránh việc mọi trở ngại tập trung theo một mẫu đối nghịch được sắp sẵn. Bước có cấu trúc cung cấp “dụng cụ sửa”: các phần tử dự phòng hoặc phép đổi chỗ có mục tiêu. Chỉ xáo trộn thì vẫn có thể thất bại; chỉ sửa theo quy tắc lại khó biết nên bắt đầu từ đâu. Hiệu quả đến từ việc ghép hai bước. [1]

Phản tập trung khép khoảng trống thế nào?

Các kết quả tiếp theo xử lý được những tập rất nhỏ và thêm nhiều trường hợp tập lớn, nhưng vùng kích thước trung bình vẫn chống lại các kỹ thuật cũ. Lisa Sauermann và Huy Tuan Pham giải quyết vùng này bằng phản tập trung. Khái niệm ấy diễn tả việc không một kết quả tổng riêng lẻ nào có xác suất xuất hiện quá cao. Họ dùng phân tích Fourier, công cụ biểu diễn hàm bằng các thành phần dạng sóng, để kiểm soát sự phân bố của các tổng ngẫu nhiên. [1]

Quy trình của họ đổi phần tử cuối trong một đoạn có tổng bằng 0 với một phần tử khác. Ba rủi ro phải được khống chế: đoạn lỗi nằm quá gần cuối nên không còn chỗ đổi; quá nhiều đoạn lỗi tụ lại; hoặc một lần sửa tạo ra lỗi mới về sau. Phản tập trung giúp ước lượng rằng các tình huống này đủ hiếm. Tổng xác suất của những biến cố xấu nhỏ hơn 1, nên có xác suất dương để quy trình tránh được tất cả. Chỉ một khả năng dương cũng đủ kết luận có ít nhất một thứ tự đạt yêu cầu. [1]

Bài toán 55 năm đã được giải đến đâu?

Bài báo cuối của Sauermann và Pham được đăng trực tuyến vào tháng 2/2026. Kết hợp với ba công trình trước, chuỗi kết quả bao phủ mọi kích thước của tập số khi mô-đun nguyên tố p đủ lớn. Chứng minh còn cho thấy ít nhất 90% thứ tự ngẫu nhiên có thể được chỉnh sửa để loại bỏ các biến cố xấu trong khuôn khổ họ xét. Đây không chỉ là tuyên bố rằng đáp án tồn tại, mà còn nói một điểm khởi đầu ngẫu nhiên thường ở khá gần đáp án. [1]

Vẫn còn một giới hạn kỹ thuật: các chứng minh giả định p rất lớn và chưa xác định một ngưỡng cụ thể áp dụng cho mọi p. Vì vậy, thành tựu năm 2026 khép lại phiên bản tiệm cận của phỏng đoán, chứ chưa xử lý riêng từng mô-đun nguyên tố nhỏ. Dẫu vậy, lời giải làm rõ nghịch lý hấp dẫn của bài toán: trong một thế giới hữu hạn, nơi các tổng dễ quay lại điểm cũ, ngẫu nhiên không xóa bỏ cấu trúc. Nó giúp trải các chướng ngại ra để cấu trúc cần tìm lộ diện. [1]