SỐ TIỀN LỚN NHẤT KHÔNG THỂ TRẢ, NAY ĐÃ CÓ CẬN TRÊN CHẶT

Hãy tưởng tượng một quầy thu tiền chỉ nhận vài loại đồng xu, với số lượng không giới hạn, và không bao giờ trả lại tiền thừa. Có những số tiền trả được chính xác; có những số không bao giờ trả được. Các nhà toán học gọi các mệnh giá đồng xu là phần tử sinh (generators), và đặt ra một câu hỏi tưởng chừng đơn giản: số tiền lớn nhất không thể trả là bao nhiêu?

Những số tiền không bao giờ trả được

Lấy các số nguyên a₁ < a₂ < … < aₙ không có ước nào chung cho tất cả. Một tổng thu được bằng cách cộng các số này, mỗi số bao nhiêu lần tùy ý, được gọi là “biểu diễn được”. Chỉ có hữu hạn số nguyên là không biểu diễn được; số lớn nhất trong đó là số Frobenius, F. (Nếu một trong các giá trị là 1, mọi số tiền đều trả được và F được quy ước bằng −1.)

Một ví dụ nhỏ: với các đồng xu 3, 4 và 6, bạn có thể trả 3, 4, 6, 7, 8 và mọi số tiền sau đó, nhưng không bao giờ trả được 1, 2 hay 5. Vậy F = 5. Lưu ý rằng 3 và 6 có ước chung; điều quan trọng là không có ước nào chung cho cả ba.

Với hai đồng xu, có một đáp án chính xác, công thức Sylvester: F(a₁, a₂) = a₁a₂ − a₁ − a₂. Với ba đồng xu trở lên, công việc là chặn F: chứng minh rằng nó không thể vượt quá một giá trị nào đó tính từ các đồng xu.

Một thừa số 2 dai dẳng

Paul Erdős và Ronald Graham đã chứng minh, với ba phần tử sinh trở lên:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

Ở đây aₙ là giá trị lớn nhất, aₙ₋₁ là giá trị lớn thứ hai, n là số lượng giá trị, và ⌊ ⌋ nghĩa là làm tròn xuống. Giống như công thức Sylvester, nó liên quan đến hai đồng xu lớn nhất.

Họ cũng ước lượng trường hợp xấu nhất, tức F lớn nhất có thể khi cả n giá trị đều không vượt quá t. Khoảng cách giữa các ước lượng của họ, xấp xỉ một thừa số 2, đã dẫn đến một giả thuyết được ghi nhận là Bài toán Erdős #433. Jacques Dixmier đã giải quyết nó, và còn chứng minh một cận đơn giản hơn, đúng với mọi bộ: F ≤ aₙ²/(n − 1). Thừa số 2 biến mất, nhưng đồng xu lớn thứ hai cũng vậy.

Giữ lại cả hai đồng xu lớn nhất

Lin Chen, Tingwei Hu, Yuchen Mao và Guochuan Zhang, thuộc Trường Khoa học và Công nghệ Máy tính của Đại học Chiết Giang, muốn có cả hai: không có thừa số 2, và vẫn giữ đồng xu lớn thứ hai. Câu trả lời của họ, đúng với mọi bộ gồm hai giá trị trở lên:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

Ở đây ⌈ ⌉ nghĩa là làm tròn lên. So với Erdős và Graham, thừa số 2 đã biến mất, đổi lại phải chia cho n − 1 thay vì n và làm tròn lên. So với Dixmier, cận mới có thể nhỏ hơn đáng kể khi đồng xu lớn thứ hai nhỏ so với đồng xu lớn nhất.

Với ví dụ 3, 4, 6, cận của Erdős và Graham cho 10, cận của Dixmier cho 18, còn cận mới cho 4 × 3 − 6 − 1 = 5, đúng bằng giá trị thật. Không có gì bất ngờ: bộ này thuộc họ các trường hợp cực trị được mô tả dưới đây, vốn được xây dựng để đạt đúng cận; bài báo không đưa ra so sánh nào trên các bộ thông thường.

Phân loại số tiền theo số dư

Chứng minh đi theo con đường của Erdős và Graham. Phân loại mọi số tiền theo số dư khi chia cho đồng xu lớn nhất, aₙ. Một khi một tổng các đồng xu nhỏ hơn đạt được một số dư nào đó, việc thêm các đồng aₙ sẽ đạt được mọi số tiền lớn hơn có cùng số dư. Nhiệm vụ là chỉ ra rằng mọi số dư đều có thể đạt được với chi phí thấp.

Công cụ then chốt là định lý Kneser, về việc một tập các tổng phải lớn đến mức nào. Erdős và Graham dùng nó để chỉ ra rằng các tổng gồm khoảng aₙ/n đồng xu phủ được hơn một nửa số dư, rồi nhân đôi lên để phủ hết. Mỗi đồng xu trong các tổng này có giá trị tối đa là aₙ₋₁, nên nhân đôi số đồng xu thì nhân đôi chi phí: từ đó sinh ra thừa số 2.

Chứng minh mới dùng các tổng gồm ⌈aₙ/(n − 1)⌉ đồng xu. Khi các tổng này bỏ sót một số số dư, định lý Kneser cho biết các số dư bị thiếu không nằm rải rác ngẫu nhiên: chúng tạo thành những họ số dư trọn vẹn, cách đều nhau. Càng thiếu nhiều họ, các đồng xu nhỏ hơn càng phải dồn vào mỗi họ đạt được, nên mỗi họ đó đều chứa vài đồng xu nhỏ, và vài đồng xu bổ sung cần để đạt tới các họ còn thiếu đều rẻ. Tổng chi phí không bao giờ vượt quá ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

Bước đầu tiên đó cho ra cận nhưng chưa có “− 1” ở cuối. Đơn vị cuối cùng đến từ một lập luận riêng, dựa trên một định lý của Scherk và Kemperman về các tổng chỉ có thể tạo thành theo đúng một cách: nó chỉ ra rằng chính số tiền ở ngưỡng biên aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ luôn trả được. Theo phần lời cảm ơn, ban đầu các tác giả chứng minh cận yếu hơn; sau đó GPT-6 đã giúp tìm ra lập luận hạ nó xuống một đơn vị, đồng thời hỗ trợ chứng minh rằng cận này không thể hạ thấp hơn và biên tập phần tiếng Anh. Các tác giả tuyên bố họ chịu trách nhiệm về bản thảo cuối cùng.

Những trường hợp chạm đúng giới hạn

Cận này không thể hạ thấp hơn: với mọi n ≥ 3, các tác giả xây dựng vô số bộ mà F bằng đúng cận đó. Lấy một q ≥ 2 bất kỳ và các giá trị q, 2q, …, (n − 1)q, cộng thêm (n − 2)q + 1. Tất cả trừ một giá trị đều là bội của q, nên chúng không trả được số tiền nào mà riêng q không trả được. Bộ này hoạt động như hai đồng xu, q và (n − 2)q + 1, và công thức Sylvester cho ra một F khớp đúng với cận mới. Với n = 3 và q = 3, công thức này tạo ra chính xác ví dụ 3, 4, 6 ở trên.

Ít đồng xu hơn, trần thấp hơn

Cận này cũng có thể được đọc theo mật độ. Nó áp dụng cho mọi bộ rút gọn gồm i giá trị nhỏ nhất cộng với giá trị lớn nhất, miễn là chúng vẫn không có ước chung. Bỏ bớt đồng xu chỉ có thể khiến việc trả tiền khó hơn, nên một trần đã chứng minh cho bộ rút gọn cũng đúng cho bộ đầy đủ. Điều chi phối kết quả xấp xỉ là aᵢ/i, nghịch đảo của mức độ dày đặc mà i giá trị đầu tiên lấp đầy các số từ 1 đến aᵢ: nhóm dày đặc nhất thắng. Đặc biệt, các tác giả lưu ý, đồng xu lớn thứ hai có thể đơn giản bị gạt sang một bên bất cứ khi nào các đồng xu còn lại vẫn không có ước nào chung cho tất cả.

Bài báo hoàn toàn mang tính lý thuyết: nó không đưa ra con số nào cho thấy cận mới nhỏ hơn bao nhiêu trên các bộ đồng xu thông thường, và tính chặt của nó chỉ được chứng minh cho ba mệnh giá đồng xu trở lên.