Bài toán Frobenius

Định lý Tem thư. Cho a, b là các số nguyên dương nguyên tố cùng nhau. Khi đó

            1) Với mọi n > ab – a – b = n₀, n có thể biểu diễn được dưới dạng

                        n = ax + by với x, y là các số nguyên không âm.

            2) Với mọi k, 0 £ k £ n₀, có đúng một trong hai số k, n₀-k biểu diễn được dưới dạng  ax + by với x, y nguyên không âm.

Kết quả này là của Sylvester. Đây là trường hợp đặc biệt của bài toán Frobenius:

Cho trước n số nguyên dương a₁, a₂, …, a_n với (a₁, a₂, …, a_n) = 1. Tìm số G_n lớn nhất không biểu diễn được dưới dạng  a₁x₁ + … + a_nx_n với x_i Î N.

Số nguyên G_n như vậy luôn tồn tại do điều kiện (a₁, a₂, …, a_n) = 1 và được suy ra từ định lý Schur (định lý khẳng định số nghiệm nguyên không âm của phương trình x = a₁x₁ + … + a_nx_n bằng

Cho đến gần đây, ngay cả trường hợp n=3 vẫn chưa giải được. Có một số người khẳng định rằng họ đã giải được trường hợp n=3. Tuy nhiên, khi xem lời giải của họ thì họ không tìm được công thức cho G₃. Đúng hơn là họ đã đưa ra một thuật toán “đơn giản” để tìm G₃. Thuật toán này được mô tả trên vài trang giấy. Nếu theo nghĩa này thì trường hợp tổng quát cũng có lời giải. Còn công thức cho G_n có lẽ là không tồn tại, ngay cả trong trường hợp n = 3.

Davidson chứng minh được đánh giá chặn dưới cho G₃(a₁, a₂, a₃) như sau:

            G₃(a₁, a₂, a₃) >= căn(a1*a2*a3) - a1 - a2 - a3

Bạn đọc quan tâm đến bài toán Frobenius (còn gọi là Frobenius coin problem) có thể xem thêm tại địa chỉ

[1] http://en.wikipedia.org/wiki/Coin_problem

Bài tập

1. Cho (a, b) = 1. Ngân hàng trung ương Sikinia phát hành chỉ 2 loại tiền a- và b-Kulotnik. Bạn có thể trả được những khoản tiền nào nếu

(a) bạn có thể nhận tiền trả lại       (b) bạn không nhận tiền trả lại

2. Ở Sikinia có ba loại quả cân: 15, 20 và 48 Slotnik. Hỏi có thể cân được những trọng lượng nào nếu dùng cân

            (a) 2 đĩa                                             (b) một đĩa

3. (IMO 1983) Cho a, b, c là các số nguyên dương với (a, b) = (b, c) = (c, a) = 1. Chứng minh rằng 2abc – ab – bc – ca là số nguyên lớn nhất không biểu diễn được dưới dạng xbc + yca + zab với x, y, z là các số nguyên không âm.

4. Với tập hợp A, ký hiệu |A| và s(A) tương ứng là số phần tử và tổng các phần tử của tập hợp A (nếu A = Æ thì |A| = s(A) = 0). Cho S là tập hợp gồm các số nguyên dương sao cho

            a) tồn tại hai phần tử x, y thuộc S với (x, y) = 1.

            b) nếu x, y thuộc S thì x + y thuộc S.

Gọi T là tập hợp tất cả các số không nằm trong S. Chứng minh rằng