Việc không bao giờ cần quá ba palindrome không hề hiển nhiên; nó được chứng minh trong một bài báo dài và phức tạp, và Numberphile có một video giải thích những nét chính của lập luận. Biết cận trên này hữu ích nhưng không bắt buộc để giải bài.

Ngay cả khi không đọc mọi bài trên arXiv cho vui, ta cũng có thể đoán số palindrome cần thiết khó mà lớn: có xấp xỉ \(\sqrt S\) palindrome nhỏ hơn \(S\), nên có xấp xỉ \(S\) cặp palindrome và các cặp này có khả năng biểu diễn \(\Theta(S)\) số nhỏ hơn \(S\). Số bộ ba còn lớn hơn thêm một hệ số \(\sqrt S\), trong khi tổng của chúng đều nhỏ hơn \(3S\); vì thế gần như không còn chỗ để một số trốn khỏi mọi bộ ba, trừ khi rất nhiều bộ ba cho cùng một tổng.

Đầu tiên, kiểm tra \(S\) có phải palindrome hay không. Nếu đúng thì đã xong. Trong phần còn lại giả sử \(S\) không phải palindrome. Việc kiểm tra tốn \(O(\log S)\) bước, một bước cho mỗi chữ số.

Test Set 1

Có phải tổng của hai palindrome?

Chỉ có khoảng \(2\times10^5\) số hạng palindrome không vượt \(10^{10}\); gọi số lượng đó là \(P\). Để kiểm tra \(S\) có phải tổng của hai palindrome, duyệt mọi palindrome \(p<S\) và kiểm tra \(S-p\) có phải palindrome. Thời gian là \(O(P\log S)\).

Chắc chắn là tổng của ba palindrome

Ta biết mọi số là tổng của ba palindrome nên phải tìm được một bộ ba. Thoạt nhìn, mở rộng cách trên sẽ phải xét \(O(P^2)\) cặp và quá chậm. Tuy nhiên, đối với mọi số không vượt \(10^{10}\), luôn có một cách biểu diễn mà một trong ba số hạng không quá 404; ví dụ giá trị 404 là cần cho \(1086412253\). Vì vậy, chỉ cần duyệt các cặp theo thứ tự ưu tiên những bộ ba chứa một giá trị nhỏ, thuật toán sẽ đủ nhanh.

Test Set 2

Có tới \(2\times10^{20}\) palindrome nhỏ hơn \(10^{40}\), nên ngay cả việc duyệt toàn bộ palindrome cũng vô vọng. Ta cần cách nhanh hơn.

Tìm \(S=X+Y\)

Giả sử \(X\ge Y\). Trước hết cố định số chữ số của \(X\) và \(Y\). Số chữ số của \(X\) phải bằng số chữ số của \(S\), hoặc ít hơn đúng một; nếu ít hơn nữa thì \(X+Y<S\).

Trước tiên giả sử \(X\) và \(Y\) có độ dài khác nhau. Khó khăn chính là các số nhớ khi cộng. Chẳng hạn, để tìm hai palindrome có độ dài 10 và 8 với tổng \(2718281828\), chữ số đầu của \(X\) có thể là 1 hoặc 2, tùy có số nhớ vào chữ số cao nhất hay không. Ta thử cả hai. Nếu trước hết giả sử không cần nhớ, chữ số đầu của \(X\) là 2. Xét tổng modulo 10 sẽ xác định chữ số cuối của \(Y\), đồng thời xác định chữ số đầu của \(Y\) vì \(Y\) là palindrome:

  ..........        2........2        2........2

+   ........  ->  +   ........  ->  +   6......6
============      ============      ============
  2718281828        2718281828        2718281828

Sau bước này, phần chữ số chưa biết phải tạo thành một palindrome 9 chữ số cộng một palindrome 7 chữ số, với tổng

Đây là một bài toán con có thể giải đệ quy, lúc này cho phép số 0 ở đầu của các phần bên trong. Khả năng còn lại là có số nhớ tại chữ số cao nhất; khi đó chữ số đầu của \(X\) phải là 1.

Khi độ dài \(X\) và \(Y\) khác nhau, luôn có ít nhất một chữ số chưa biết mà ta xác định được. Nếu hai độ dài bằng nhau thì chưa chắc. Khi đó kết hợp hai quan sát để liệt kê các lựa chọn khả thi cho chữ số đầu và cuối của cả hai số. Thứ nhất, xét tổng modulo 10 để thu hẹp các cặp chữ số. Thứ hai, so sánh số chữ số của \(S\) với độ dài \(X,Y\) để biết tổng hai chữ số cao nhất phải tạo số nhớ hay không. Nếu \(S\) có 5 chữ số còn \(X,Y\) chỉ có 4, tổng cao nhất phải ít nhất 10. Nếu \(S\) và \(X\) dài bằng nhau thì không được tạo thêm chữ số, nên tổng cao nhất không quá 9. Vẫn có thể còn nhiều lựa chọn — tổng 8 có thể là \(0+8,1+7,\ldots,8+0\) — nhưng chọn cặp nào không quan trọng, vì ảnh hưởng duy nhất lên các chữ số khác là bit nhớ. Ngoại lệ duy nhất là phải tránh tạo số 0 ở đầu một số.

Gọi \(D\) là số chữ số của \(S\). Có \(O(D)\) cặp độ dài cho \(X,Y\). Với mỗi cặp, ta quyết định có nhớ hay không ở từng chữ số phía trái của \(S\); tùy cách cài đặt, tốn \(O(2^{D/2}D)\), tổng cộng \(O(2^{D/2}D^2)\). Có thể xác định cả phần “nhô ra” thay vì mỗi lần một chữ số. Trong ví dụ, ta biết ngay hai chữ số đầu là 26 hoặc 27:

  ..........        27......72        27......72

+   ........  ->  +   ........  ->  +   65....56
============      ============      ============
  2718281828        2718281828        2718281828

Nhờ vậy chỉ cần đưa ra \(D/\text{overhang}\) quyết định về số nhớ thay vì \(D/2\); khi phần nhô dài, các phép tính đó không chi phối độ phức tạp. Tổng thời gian giảm còn \(O(2^{D/2}D)\).

Tổng của ba palindrome

Bài báo nói trên mô tả một thuật toán viết mọi số thành tổng của ba palindrome. Dĩ nhiên không nhất thiết phải cài chính thuật toán đó, nhưng bài vẫn yêu cầu tìm ra ba số hạng.

Có \(O(S\sqrt S)\) bộ ba palindrome nhỏ hơn \(S\), nên trung bình mỗi số có \(O(\sqrt S)\) cách biểu diễn bằng bộ ba. Ta có thể chọn ngẫu nhiên một palindrome làm một trong ba giá trị, rồi dùng thuật toán hai-palindrome ở trên để kiểm tra phần còn lại.

Về lý thuyết có thể tồn tại một số chỉ có đúng một cách biểu diễn bằng ba palindrome, nhưng nhóm phân tích không tìm thấy trường hợp nào không có rất nhiều bộ ba. Thực tế, họ không tìm thấy đầu vào nào buộc một trong ba số hạng phải lớn hơn 10801, dù tin rằng nhiều trường hợp như vậy tồn tại.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2019, Chung kết thế giới, bài Won't sum? Must now; kho Google Coding Competitions (Apache-2.0).