Bài toán 55 năm của Graham được giải nhờ phương pháp xác suất

Một giả thuyết toán học tồn tại hơn nửa thế kỷ, được cho là lấy cảm hứng từ nghệ thuật tung hứng, vừa được nhóm nhà toán học trẻ chứng minh trọn vẹn qua bốn bài báo. Điểm chung của lời giải là sức mạnh của tính ngẫu nhiên trong việc tìm ra các cấu trúc ẩn.

Ronald Graham, nhà toán học và cũng là người tung hứng chuyên nghiệp

Khởi nguồn từ những quả bóng tung hứng

Ronald Graham, nhà toán học quá cố, từng là chủ tịch Hội Toán học Hoa Kỳ và đồng thời là chủ tịch Hiệp hội Những người tung hứng Quốc tế. Ông nổi tiếng với những trò biểu diễn khéo léo, theo lời Fan Chung, nhà toán học tại UC San Diego và là vợ ông.

Năm 1971, Graham đặt ra một câu hỏi mà nhiều người nay cho rằng cũng bắt nguồn từ tung hứng. Bài toán như sau: lấy một tập các số nguyên khác nhau, không chứa số 0. Liệu có luôn sắp xếp lại được chúng sao cho khi cộng dồn số thứ nhất với số thứ hai, rồi cộng tiếp số thứ ba, thứ tư… thì mọi tổng riêng phần (partial sum) đều khác nhau?

Trong ngôn ngữ tung hứng, điều này tương đương với việc mỗi quả bóng nằm trên không trong một khoảng thời gian khác nhau, và bạn luôn tìm được thứ tự ném để hai quả bóng không rơi xuống cùng một nhịp — tình huống sẽ làm hỏng màn biểu diễn.

Nếu mọi số đều dương, câu trả lời hiển nhiên là có, vì tổng sẽ tăng dần khi cộng thêm. Nếu tập số có cả dương lẫn âm, câu trả lời cũng đã được biết là có. Nhưng Graham muốn biết điều gì xảy ra khi các số vận hành trong một thế giới hữu hạn — kiểu số học đồng hồ (clock arithmetic), trong đó các số lặp lại sau một số nguyên tố p cho trước.

Ông phỏng đoán rằng câu trả lời vẫn là có, và giả thuyết này tồn tại suốt nhiều thập kỷ mà không ai chứng minh được.

Bốn bài báo, nhiều hướng tiếp cận

Công trình được hoàn thiện qua bốn bài báo. Bài cuối cùng của Lisa Sauermann (Đại học Bonn) và Huy Tuan Pham (Đại học Chicago) công bố tháng 2/2026, chính thức khép lại bài toán.

Trước đó, Alp Müyesser (Đại học Oxford) cùng cố vấn cũ Alexey Pokrovskiy (University College London) xử lý trường hợp tập số gần như chứa mọi số từ 1 đến p. Với tập lớn như vậy, việc dựng một thứ tự hợp lệ rất khó, nhưng bắt đầu từ một thứ tự ngẫu nhiên lại đưa bạn đi được phần lớn chặng đường. Hai người đặt riêng vài số đặc biệt, xáo trộn phần còn lại, rồi chèn số dự phòng vào bất cứ đoạn nào cộng lại bằng 0.

Alp Müyesser quan tâm đến các bài toán cần kết hợp tính ngẫu nhiên với một yếu tố khác

Ở đầu kia, Noah Kravitz và Benjamin Bedert (Oxford) giải trường hợp tập số rất nhỏ so với p, chẳng hạn 100 số trong khi p là 1 tỷ, và công bố kết quả tháng 9/2024. Kravitz sau đó bắt tay với nhóm của Müyesser, và bài báo chung ra tháng 8/2025 xử lý thêm các trường hợp tập số lớn. Giữa hai vùng này vẫn còn khoảng trống: các tập có kích thước trung bình, cỡ bằng một nửa p.

Anti-concentration: chìa khóa cho khoảng trống cuối cùng

Sau một hội nghị tại Đức tháng 9/2025, Pham ở lại Bonn thăm Sauermann vài ngày. Cả hai đều nghe các báo cáo về những nỗ lực bất thành trước đó, và đến cuối ba ngày, họ đã có kế hoạch.

Hướng đi dựa vào anti-concentration — một kỹ thuật khẳng định rằng một sự kiện nào đó có xác suất xảy ra đặc biệt thấp. Kravitz thừa nhận nhóm anh biết cách tiếp cận này có thể thành công nhưng "chưa đủ can đảm để thử thật".

Họ cũng bắt đầu bằng một thứ tự ngẫu nhiên, rồi đưa ra quy trình sửa lỗi: mỗi khi phát hiện một đoạn cộng lại bằng 0, hoán đổi số cuối của đoạn với một số khác. Quy trình thất bại trong ba tình huống — đoạn tổng bằng 0 nằm sát cuối dãy, nhiều đoạn như vậy xuất hiện quá sát nhau, hoặc việc sửa lỗi này lại sinh ra lỗi mới.

Sauermann và Pham dùng phân tích Fourier để chứng minh rằng nhìn chung, khi cộng các tập số ngẫu nhiên, không có tổng nào đặc biệt dễ xuất hiện. Từ đó họ ước lượng xác suất từng sự kiện xấu và chứng minh tổng xác suất của chúng thấp hơn 100%.

Lisa Sauermann và Huy Tuan Pham, đôi bạn quen nhau từ thời ở Stanford

Bài chứng minh dài 27 trang cho thấy không chỉ luôn tồn tại cách sắp xếp thỏa mãn giả thuyết, mà một thứ tự ngẫu nhiên còn có thể được chỉnh sửa để loại bỏ các sự kiện xấu với tỷ lệ thành công ít nhất 90%.

Điều gì vẫn còn bỏ ngỏ

Cả bốn bài báo đều giả định p rất lớn — cỡ 10 mũ 100 — chứ chưa giải quyết trọn vẹn cho mọi giá trị p hữu hạn. Và nếu ai đó muốn dùng kết quả này để dàn dựng một màn tung hứng thực tế thì không khả thi, vì màn biểu diễn tương ứng sẽ dài đến mức vô lý.

Dù vậy, kết quả khẳng định rằng ngay trong những cấu trúc số học hạn chế kỳ lạ, vẫn luôn tồn tại các cấu trúc đẹp. Fan Chung nói: "Để đặt ra một bài toán hay là cả một nghệ thuật. Tôi nghĩ Ron sẽ vô cùng hạnh phúc khi thấy bài toán được giải."

"Đó là sức mạnh của hợp tác, của thế hệ trẻ, của các phương pháp xác suất" — Noga Alon, Đại học Princeton.

Minh họa bài toán sắp xếp lại của Graham

Góc nhìn

Câu chuyện này là ví dụ rõ ràng cho thấy phương pháp xác suất đang trở thành vũ khí tiêu chuẩn để giải những bài toán tổ hợp tưởng như bế tắc. Với kỹ sư và lập trình viên Việt Nam, đây là gợi ý đáng chú ý: nhiều bài toán hằng ngày — từ sắp xếp lịch, phân bổ tài nguyên, đến kiểm thử hệ phân tán — có thể tiếp cận bằng cách chấp nhận ngẫu nhiên hóa rồi sửa lỗi cục bộ thay vì cố dựng lời giải tối ưu từ đầu.

Chi tiết đáng học hỏi thứ hai là cách cộng đồng toán học vận hành: các nhóm làm độc lập, không biết đến kết quả của nhau, rồi ghép các mảnh lại thành lời giải hoàn chỉnh. Với các nhóm nghiên cứu và kỹ thuật nhỏ, việc công bố sớm những kết quả bộ phận có thể giúp người khác nối vào đúng chỗ — đúng như cách bốn bài báo đã khép kín một bài toán 55 năm.