SỐ FROBENIUS VÀ ĐỊNH LÍ SYLVESTER

A- Lời mở đầu :  Bài toán đồng xu Frobenius 

Số học thường được ví như là trò chơi của các bộ óc siêu phàm sáng tạo của các nhà toán học . Nhưng cũng có quan niệm : số học bắt nguồn từ nhu cầu giải quyết các bài toán thực tiễn đặt ra cho các nhà toán học . Để minh chứng cho luận điểm này tôi mời bạn  hãy quan sát một ví dụ về dịch vụ đổi tiền và thanh toán tiền  trong ngành ngân hàng:

Ví dụ : Bạn chỉ cò hai loại tiền xu : 3 xu và 5 xu  . Để thanh toán tiền cho khách hàng (đơn vị tính bằng xu và chỉ dùng 2 loại tiền mà bạn có ) chẳng hạn tôi nêu một số trường hợp cụ thể như sau :

Ông A được nhận 16 xu  = 2 đồng 5 xu + 2 đồng 3xu

Bà B  được nhận 19 xu  = 2 đồng 5 xu + 3 đồng 3xu

Anh  C được nhận 41 xu  = 7 đồng 5 xu + 2 đồng 3xu

Nhưng nếu cô D được nhận 7 xu thì bạn sẽ thanh toán bằng cách nào cho cô ấy nhỉ ? Xin thưa : bạn không thể có cách nào để thanh toán cho cô D cả ! Vì sao ư ?  Đó là câu hỏi khó với nhiều bạn và không dễ gì cắt nghĩa ngay . Giải thích điều đó phải dẫn  bạn đến việc chứng minh mệnh đề : Không thể thanh toán 7xu  bắng chỉ 2 loại tiền : 3 xu và 5 xu !.

Từ ví dụ trên  xuất hiện các câu hỏi sau :

Câu hỏi 1: Nếu cần thanh toán m xu cho khách hàng  và chỉ dùng 2 loại tiền : 3 , 5 xu thì có bao nhiêu trường hợp mà bạn không thể thanh toán được ? Số m lớn nhất mà không thể thanh toán được là bao nhiêu ?  Vì sao ?

Câu hỏi 2 : Nếu bạn có 2 loại tiền xu : a xu và b xu , với (a ; b ) = 1  thì số m lớn nhất mà không thể thanh toán được bằng 2 loại tiền xu của bạn có mối liên hệ như thế nào với a , b ?

Câu hỏi 3 :  Bạn cần ít nhất mấy lọai đồng xu để có thể thanh toán hoặc trao đổi mọi nhu cầu của khách hàng ?

Bạn thấy đấy : Chỉ từ một bài toán rất nhỏ trong thực tế đã làm xuất hiện các vấn đề cần giải quyết , Và chính lúc này cần sự nghiên cứu của những người giỏi về số học để giúp bạn trả lời  các câu hỏi đặt ra trên đây  – Và như vậy thì các bạn bắt đầu hiểu và cảm ơn các nhà lí thuyết số  trong toán học rồi đấy !

Tôi xin nói thêm với các bạn : Có rất nhiều bài toán thực tế có bản chất tương tự như ví dụ trên , nó tổng quát hóa như sau : Cho 2 số nguyên dương a , b nguyên tố cùng nhau . Hãy xác định số nguyên dương m lớn nhất sao cho m không biểu diễn được dưới dạng : ax + by với x ; y là 2 số nguyên không âm

■ Bài toán này được nhà toán học Đức Ferdinand Georg Frobenius (1849 – 1917) nêu ra từ thực tiễn bài toán đổi tiền và sau này được tổng quát thành bài toán sau :  

Nhà toán học người Anh Jame JosephSylvester (3 /9/1814 – 15/5/1897)

Hệ quả  :

■ Theo (**) thì Với mọi k, 0 < k < S , thì có đúng một trong hai số k , S-k biểu diễn được dưới dạng  ax + by với x, y nguyên không âm  Và như vậy cùng với S sẽ có ít nhất 2 số nguyên dương không thể biểu diễn được thành dạng ax + by với  với  a ; b là hai số dương (a;b) = 1 và  x ≥ 0 ; y ≥ 0

■ Với mọi số nguyên dương n ≥ (a – 1)(b – 1) ta có  S = n + (S – n)  và  vì S – n  < 0 nên không biểu diễn được  thành dạng ax + by với  với  a ; b là hai số dương (a;b) = 1 và  x ≥ 0 ; y ≥ 0  nên theo bổ đề 2 thì N biểu diễn được thành dạng ax + by với  với  a ; b là hai số dương (a;b) = 1 và  x ≥ 0 ; y ≥ 0 ,  hay nói cách khác : Một số nguyên dương N > S  đều biểu diễn được thành dạng ax + by với  với  a ; b là hai số dương (a;b) = 1 và  x ≥ 0 ; y ≥ 0 => S là số nguyên dương nhỏ nhất không biểu diễn được  thành dạng ax + by với  với  a ; b là hai số dương (a;b) = 1 và  x ≥ 0 ; y ≥ 0

BÀI TẬP ÁP DỤNG :

Bài 1:  Chứng minh rằng phương trình ax + by = m (trong đó a và b là hai số nguyên dương nguyên tố cùnh nhau) luôncó nghiệm nếu m > ab-a-b 
Bài 2: Có ba loại quả cân: 15, 20 và 48 g. 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

Bài 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.

Bài 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 = tập rỗng  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 : s(T) < T^2