ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN VĂN LỰC MỘT SỐ ƯỚC LƯỢNG CỦA SỐ FROBENIUS LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - NĂM 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN VĂN LỰC MỘT SỐ ƯỚC LƯỢNG CỦA SỐ FROBENIUS LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 01 13 Người hướng dẫn khoa học PGS.TS ĐÀM VĂN NHỈ THÁI NGUYÊN - NĂM 2015 i Mục lục Mở đầu 1 Một vài thuật toán 1.1 Vấn đề Frobenius 1.2 Thuật toán Euclide 1.2.1 Xác định ước chung lớn 1.2.2 Chương trình tìm ước số chung lớn 1.2.3 Giải phương trình ax + by = c 1.3 Thuật toán xác định g(a1 , a2 , a3 ) 1.3.1 Thuật toán Rodseth 1.3.2 Thuật toán Davison 1.3.3 Thuật toán Killingbergtro 1.3.4 Thuật toán Greenberg 1.4 Độ phức tạp phương diện tính số Frobenius 1.4.1 Độ phức tạp 1.4.2 Một vài số chặn chặn số Frobenius 3 6 8 11 12 13 13 14 Số Frobenius 2.1 Số Frobenius cho n = 2, n = 2.1.1 Số Frobenius g(a, b) 2.1.2 Tiếp cận số Frobenius qua hàm sinh 2.1.3 Về Số Frobenius g(a, b, c) 2.1.4 Một vài công thức chặn 2.2 Về Số Frobenius g(a1 , a2 , a3 , a4 ) 2.2.1 Một vài kết g(a1 , a2 , a3 , a4 ) 2.2.2 Một số ví dụ bổ sung 15 15 15 18 20 21 24 24 28 ii Kết luận 31 Tài liệu tham khảo 32 MỞ ĐẦU Số học ln coi nữ hồng Tốn học chứa đựng nhiều vẻ đẹp tư logic Khơng nhiều ngành tốn học khác, Số học tồn nhiều giả thuyết chưa có câu trả lời mà học sinh hiểu với kiến thức trung học sở Quá trình tìm kiếm lời giải cho giả thuyết làm nhiều tư tưởng lớn, nhiều lý thuyết lớn toán học nảy sinh Do Số học mệnh danh nữ hoàng tư nên tốn Số học ln ln xuất giữ vị trí quan trọng kì thi học sinh giỏi quốc gia, quốc tế Số học cầu nối tự nhiên đưa người học tiếp cận với khoa học đại Xuất phát từ toán "đổi tiền", Frobenius đưa giả thiết đầy thú vị Cho tập A = {a1 , a2 , , an } ⊂ N số nguyên dương khác Ta nói rằng, số nguyên m ∈ N tổ hợp nguyên số a1 , a2 , , an tồn số nguyên xi ∈ N, i = 1, 2, , n, để có m = a1 x + a2 x + · · · + an x n Khi ước chúng lớn (a1 , a2 , , an ) = dễ dàng kiểm tra tính hữu hạn tập số nguyên dương không tổ hợp nguyên a1 , a2 , , an Ký n xi |xi ∈ N, i = 1, 2, , n hiệu C(A) = C(A) = N \ C(A) Thông thường, i=1 ta giả thiết < a1 < a2 < · · · < an (a1 , a2 , , an ) = Bởi tập số nguyên dương C(A) hữu hạn nên tồn Số Frobenius g(a1 , , an ) = max C(A) Giải vấn đề Frobenius mô tả tường minh tập C(A) công thức xác định số g(a1 , , an ) Vấn đề Frobenius có xuất xứ từ tốn "đổi tiền." Khi ta có đồng xu mệnh giá a1 , a2 , , an ta khơng thể đổi loại tiền thuộc C(a1 , a2 , , an ) thành đồng xu đổi tất đồng tiền mệnh giá lớn g(a1 , , an ) Trường hợp n = giải trọn vẹn J J Sylvester vào năm 1884 Ông rằng, hai số nguyên dương a1 , a2 thỏa mãn (a1 , a2 ) = số nguyên n (a1 − 1)(a2 − 1) biểu diễn thành dạng n = a1 x + a2 y với hai số nguyên không âm x, y Như vậy, ta có g(a1 , a2 ) = a1 a2 −a1 −a2 Hơn nữa, (a1 − 1)(a2 − 1) Với n = 3, ta có vài ví dụ đặc biệt C(3, 5, 7) = {1, 2, 4} C(7, 8, 10) = {1, 2, 3, 4, 5, 6, 9, 11, 12, 13, 19}, Sylvester |C(a1 , a2 )| = v.v Theo F Aguiló A Miralles báo [On the Frobenius’ Problem of three numbers, EuroComb 2005,317-322], việc giải vấn đề Frobenius cho n toán mở Tuy vậy, vấn đề nhiều người quan tâm Luận văn đặt vấn đề trình bày lại số thuật tốn ước lượng để đánh giá Số Frobenius Luận văn hoàn thành hướng dẫn tận tình PGS.TS Đàm Văn Nhỉ Tác giả xin bày tỏ lòng biết ơn sâu sắc tới Thầy Tôi xin chân thành cảm ơn Ban giám hiệu thầy cô giáo trường Đại học Khoa học - Đại học Thái Nguyên, nhiệt tình giảng dạy, giúp đỡ tơi suốt q trình học tập, nghiên cứu Và cuối cùng, xin gửi lời cảm ơn tới gia đình, bạn bè đồng nghiệp ủng hộ, giúp đỡ suốt thời gian qua Thái Nguyên, ngày 10 tháng năm 2015 Học viên Trần Văn Lực Chương Một vài thuật toán 1.1 Vấn đề Frobenius Giả sử có nhiều vơ hạn đồng tiền xu muốn đổi chúng thành đồng tiền xu Vậy loại tiền đổi được? Ta thấy = 1.5 + 0.7, = 0.5 + 1.7 10 = 2.5 + 0.7, 12 = 1.5 + 1.7 14 = 0.5 + 2.7, 15 = 3.5 + 0.7 17 = 2.5 + 1.7, 19 = 1.5 + 2.7 20 = 4.5 + 0.7, 21 = 0.5 + 3.7 22 = 3.5 + 1.7, 24 = 2.5 + 2.7 25 = 5.5 + 0.7, 26 = 1.5 + 3.7 27 = 4.5 + 1.7, 28 = 0.5 + 4.7 29 = 3.5 + 2.7, 30 = 6.5 + 0.7 dễ dàng rằng, loại tiền 24, 25, 26, 27, 28, đổi thành hai loại xu Đồng 23 xu loại tiền lớn không đổi qua thành loại xu Tổng quát vấn đề sau: Giả sử ta muốn hủy tiền xu cũ để thay đồng xu mệnh giá a1 , a2 , , an xu Những đồng tiền đổi qua đồng xu loại Vấn đề Ferdinand Georg Frobenius (1849-1917) James Joseph Sylvester (1814-1897) quan tâm Đặc biệt, ông quan tâm đến đồng tiền lớn đổi qua lọai xu thường gọi vấn đề đổi tiền xu Frobenius Bây ta trình bày lại tương đối hệ thống vấn đề toán số học Giả sử a1 , a2 , , an số nguyên dương Ký hiệu ước số chung lớn chúng qua (a1 , a2 , , an ) Định nghĩa 1.1.1 Số nguyên dương m gọi tổ hợp nguyên không âm a1 , a2 , , an tồn số nguyên x1 , x2 , n , xn để m có biểu diễn dạng m = x i i=1 Đã từ lâu xuất toán tồn số nguyên dương M để cho m M tổ hợp nguyên không âm a1 , a2 , , an Thực ra, ý tưởng coi kết tất yếu nảy sinh từ định lý Định lý 1.1.2 Cho a1 , a2 , , an số nguyên dương với ước chung lớn (a1 , a2 , , an ) = Khi tồn số nguyên L để cho số nguyên s L tổ hợp nguyên không âm a1 , a2 , , an Chứng minh: Vì (a1 , a2 , , an ) = dựa vào thuật toán Euclide với đồng (a1 , a2 , , an ) = ((a1 , a2 , , an−1 ), an ) nên có số nguyên m1 , m2 , , mn thỏa mãn m1 a1 + m2 a2 + · · · + mn an = Ký hiệu P = m j aj mj −Q = m i mi với i = 1, 2, , n với số nguyên m > F (a1 , a2 , , an ) Hàm L(a1 , a2 , , an ) = F (a1 , a2 , , an ) − a1 − a2 − · · · − an thỏa mãn điều kiện: Phương trình tuyến tính a1 x1 + a2 x2 + · · · + an xn = m có nghiệm nguyên xi với i = 1, 2, , n với số nguyên m L(a1 , a2 , , an ) Ta xét ví dụ C(5, 6), chẳng hạn số nguyên dương = 20 biểu diễn thành 5.4 + 6.0 với 4, ∈ N số nguyên dương b viết thành 5x + 6y với x, y ∈ N Như vậy, số nguyên dương lớn g0 = 19 để phương trình 5x + 6y = g0 với x, y ∈ N không giải Dễ dàng kiểm tra, với L(5, 6) = 20 = 4.5 + 6.0 thỏa mãn điều kiện: Phương trình 5x + 6y = m ln có nghiệm x, y ∈ N với m 20 số F (5, 6) = 20 + 11 = 31 thỏa mãn điều kiện: Phương trình 5x + 6y = m ln có nghiệm x, y ∈ N∗ với m 31, chẳng hạn: 31 = 5.5 + 6.1, 32 = 5.4 + 6.2, 33 = 5.3 + 6.3, 34 = 5.2 + 6.4, 35 = 5.1 + 6.5, 36 = 5.6 + 6.1 Số 30 biểu diễn thành 30 = 5x + 6y với x, y nguyên dương, 5x, 30 chia hết cho 6y phải chia hết cho Như vậy, từ tồn số L ta suy tập số nguyên không âm {0, 1, 2, , L} Để chọn số nguyên dương M thỏa mãn yêu cầu dặt toán xác định số M Vấn đề: Phương pháp chọn M nào? Đặc biệt, việc tìm kiếm cơng thức biểu diễn số M ? Những toán làm nẩy sinh toán, gọi chung Vấn đề Frobenius, việc xác định số tự nhiên lớn không tổ hợp nguyên không âm a1 , a2 , , an ký hiệu qua g(a1 , a2 , , an ) Số gọi số Frobenius Do độ phức tạp toán nên người ta đưa chặn thuật toán để giải vấn đề Chú ý rằng, người ta giả thiết a1 < a2 < · · · < an nhắc đến sơ Frobenius Ví dụ 1.1.5 Một vài số Frobenius dễ dàng xác định g(2, 3) = 1, g(3, 5) = 7, g(4, 5) = 11, g(5, 7) = 23 g(2, 5) = 3, g(3, 7) = 11, g(4, 7) = 17, g(5, 9) = 31 Ví dụ 1.1.6 Xác định số Frobenius g(6, 9, 20) Bài giải: Với ba số nguyên dương (6, 9, 10) ta có g(6, 9, 10) = 43 44 = 1.6 + 2.9 + 2.10, 45 = 0.6 + 5.9 + 0.10 46 = 1.6 + 0.9 + 4.10, 47 = 0.6 + 3.9 + 2.10 48 = 2.6 + 4.9 + 0.10, 49 = 0.6 + 1.9 + 4.10 Bằng phương pháp quy nạp, dễ dàng số nguyên lớn 43 tổ hợp nguyên 6, 9, 10 Ví dụ 1.1.7 Kevin Chen xác định hai số Frobenius sau đây: a−2 + a + (d − 1)(a1 ) − n m2 (n − 1)(mk−1 − nk−1 ) g(mk , mk−1 n, , nk ) = nk−1 (mn − m − n) + m−n g(a, a + d, a + 2d, , a + nd) = 1.2 Thuật toán Euclide Trong chứng minh sử dụng thuật toán Euclide (a1 , a2 , , an ) = ((a1 , a2 , , an−1 ), an ) để xác định ước số chung lớn hai số nguyên Do vậy, trình bày lại thuật toán 1.2.1 Xác định ước chung lớn Cho hai số nguyên a b Vấn đề: Xác định ước số chung lớn (a, b) a b Nếu a|b (a, b) = |a| Nếu b|a (a, b) = |b| 19 (x − 1)(xab − 1) (xa − 1)(xb − 1) Vì nghiệm (xa − 1)(xb − 1) nghiệm (x − 1)(xab − 1) nên f (x) Giả sử hai số nguyên dương a b với (a, b) = Xét hàm f (x) = mọt đa thức dễ dàng f (x) có hệ số nguyên Giả sử ta có phân tích xa − = φk (x) xb − = k|a φh (x), (xem mục: Đa thức chia đường tròn) Bậc h|a đa thức f (x) ab − a − b + hệ tử cao Theo Quy tắc L’Hospital ta nhận f (1) = suy f (x) − chia hết cho x − Do f (x) − đa thức với bậc ab − a − b hệ tử cao x−1 Với i ∈ N ký hiệu r(i) số nghiệm phương trình p(x) = ax + by = i với x, y ∈ N ∞ Khi r(i)xi = (1 + xa + x2a + x3a + · · · )(1 + xb + x2b + x3b + · · · ) i=0 ∞ p(x) = (x 1−x r(i)xi + − 1) i=0 ∞ = x ab ∞ i (1 − r(i))xi r(i)x + i=0 ab−1 i=0 ∞ (1 − r(i))xi + = r(i)xi = i=0 p(x) + f (x) x − Như = (x − 1)(xab − 1) xab − ab ∞ i=0 [r(i − ab) + − r(i)]xi i=ab Vì p(x) đa thức bậc ab−a−b với hệ tử cao nên r(ab−a−b) = r(i) > i > ab − a − b Ta nhận hệ thức g(a, b) = ab − a − b ab−1 Cũng từ p(x) = (1 − r(i))xi + i=0 ∞ [r(i − ab) + − r(i)]xi ta có i=ab r(i) = r(i − ab) + 1, i ab Định lý 2.1.8 [Brown and Shiue] Giả sử hai số nguyên dương a b thỏa mãn (a, b) = Với i ∈ N, ký hiệu r(i) số nghiệm phương trình ax + by = i với x, y ∈ N Nếu i ab − r(i) = r(i) = 1; Cịn i ab r(i) = r(i − ab) + Chứng minh: Ta phải chứng minh két cho i ab−1 Nếu ax+by = i với x, y ∈ N, vơ nghiệm r(i) = Giả sử có ax1 + by1 = i = ax2 + by2 với x1 , x2 , y1 , y2 ∈ N Như a(x1 − x2 ) = b(y2 − y1 ) Do (a, b) = nên b|(x1 − x2 ) Vì i < ab nên x1 , x2 < b Từ suy x1 = x2 y1 = y2 Khi r(i) = 20 Định lý 2.1.9 [Sylvester] Giả sử hai số nguyên dương a b thỏa mãn (a, b) = Khi đó, số số nguyên dương nhỏ g(a, b) không tổ hợp (a − 1)(b − 1) nguyên a b d Chứng minh: Viết lại kết đạt p(x) = (1−r(i))xi với d = ab−a−b i=0 d (1 − r(i)) Do p(1) = Card{i Cho x = ta nhận hệ thức p(1) = i=0 ab − a − b|r(i) = 0} Mặt khác, p(x) = f (x) − đa thức với bậc x−1 ab − a − b hệ tử cao nên theo Quy tắc L’Hospital ta có (a − 1)(b − 1) (a − 1)(b − 1) Tóm lại Card{i ab − a − b|r(i) = 0} = p(1) = 2 Định lý 2.1.10 Giả sử hai số nguyên dương a b thỏa mãn (a, b) = Khi đó, tổng T số nguyên dương nhỏ g(a, b) không tổ hợp nguyên a b T = (a − 1)(b − 1)(2ab − a − b − 1) 12 d Chứng minh: Từ p(x) = (1 − r(i))xi với d = ab − a − b ta suy p (x) = i=0 d i(1 − r(i))xi ta có i=0 d i(1 − r(i)) = p (1) = i ab − a − b|r(i) = i=0 Như vậy, p (1) tổng số nguyên không âm i cho phương trình ax + by = i với x, y ∈ N, vô nghiệm Vận dụng quy tắc L’Hospital ta nhận p (1) = (a − 1)(b − 1)(2ab − a − b − 1) 12 2.1.3 Về Số Frobenius g(a, b, c) Trái với trường hợp xác định số g(a, b) = ab − a − b, việc tìm cơng thức biểu diễn cho g(a, b, c) khó tốn thuộc loại thuật toán thời gian đa thức Trong báo mình, Curtis rằng, việc xác định công thức đơn giản cho g(a, b, c) qua tập hữu hạn đa thức khó làm Điều phát biểu qua định lý đây: Định lý 2.1.11 [Curtis’s Theorem] Ký hiệu A = {(a, b, c) ∈ N3 |a < b < c; a, b số nguyên tố, a, b |c} Khi đó, khơng có đa thức P ∈ C[x, y, z, t] \ {0}, thỏa mãn P (a, b, c, g(a, b, c)) = với (a, b, c) ∈ A 21 Hệ rằng, số g(a, b, c) xác định tập biểu thức suy từ tập hữu hạn đa thức thu hẹp tập A Hệ 2.1.12 Khơng có tập hữu hạn đa thức {h1 , h2 , , hn } thỏa mãn lần chọn cho a, b, c ln có i để hi (a, b, c) = g(a, b, c) n Chứng minh: Đa thức h = (hi (x, y, z) − t) phải triệt tiêu A, mâu thuẫn i=1 theo Định lý 2.1.11 2.1.4 Một vài công thức chặn Một cơng thức chung sau để tính g(a1 , a2 , a3 ) xác định được, khơng biểu diễn qua cơng thức đóng Giả sử L1 , L2 , Ln số nguyên dương nhỏ để cho có số nguyên xij với i, j 3, i = j, thỏa mãn L1 a1 = a2 x12 + a3 x13 L2 a2 = a1 x21 + a3 x23 L3 a3 = a1 x31 + a2 x32 Bằng cách sử dụng Đa thức Hilbert vành phân bậc, ta có Định lý 2.1.13 [G Denham, J L Ramirez Alfonsin] Cho số nguyên dương a1 , a2 , a3 đôi nguyên tố {i, j, k} = {1, 2, 3} Khi ta có số g = g(a1 , a2 , a3 ) xác định theo    max Li + ak xjk , Lj aj + ak xik − g= as xij > với ∀i, j s=1   Lj aj + Li − as xij = s=1 Dù chưa đưa công thức xác định số g(a1 , a2 , a3 ), số nhà tốn học đưa cơng thức chặn cho số g(a1 , a2 , a3 ) qua kết sau Định lý 2.1.14 Cho ba số nguyên dương a1 , a2 , a3 với (a1 , a2 , a3 ) = Khi (1) [Beck] g(a1 , a2 , a3 ) a1 a2 a3 1 1 + + a1 a2 a2 a3 a3 a1 − (a1 − a2 − a3 ) (1) [Vitek] Nếu a1 , a2 , a3 độc lập, có nghĩa: khơng có số biểu diễn qua hai số cịn lại, g(a1 , a2 , a3 ) a1 a3 −1 22 Giả sử a1 , , an ∈ N∗ Ký hiệu L(a1 , , an ) tập tất số tự nhiên biểu diễn thành tổ hợp tuyến tính khơng âm a1 , , an M (a1 , , an ) tập tất số tự nhiên không biểu diễn thành tổ hợp tuyến tính khơng âm a1 , , an Với n = ta đặt l1 = min{l ∈ N∗ |la1 ∈ L(a2 , a3 )} l2 = min{l ∈ N∗ |la2 ∈ L(a3 , a1 )} l3 = min{l ∈ N∗ |la3 ∈ L(a1 , a2 )} Nếu có li = 1, chẳng hạn: l1 = a1 ∈ L(a2 , a3 ) ta có G(a1 , a2 , a3 ) = G(a2 , a3 ) Do ta giả thiết li với i = 1, 2, Bổ đề 2.1.15 Cho số nguyên dương a1 , a2 , a3 đôi nguyên tố Giả sử l1 , l2 , l3 Khi tồn biểu diễn l1 a1 = n12 a2 + n13 a3 , n12 , n13 ∈ N l2 a2 = n21 a1 + n23 a3 , n21 , n23 ∈ N l3 a3 = n31 a1 + n32 a2 , n31 , n32 ∈ N Hơn nữa, khẳng định sau đúng: (i) Biểu diễn li (ii) Các hệ số nij với i = j (iii) l1 = n21 + n31 , l2 = n12 + n32 , l3 = n13 + n23 Chứng minh: Ta có biểu diễn l1 a1 = n12 a2 + n13 a3 , với n12 , n13 ∈ N; l2 a2 = n21 a1 + n23 a3 , với n21 , n23 ∈ N l3 a3 = n31 a1 + n32 a2 , với n31 , n32 ∈ N, theo định nghĩa Bây ta nij i = j Thật vậy, giả sử có cặp i, j để nij = Khơng làm tính chất tổng quát, ta xét chẳng hạn n13 = Khi l1 a1 = n12 a2 Vì (a1 , a2 ) = 1, l1 hết l1 Vậy l1 a2 Vì l3 2, nên a2 chia nên a3 < l3 a3 = n31 a1 + n32 a2 , với n31 , n32 ∈ N, suy a3 ∈ M (a1 , a2 ) Ta có a3 g(a1 , a2 ) − = a1 a2 − a1 − a2 theo Định lý 2.1.2 Vì (a1 , a2 ) = nên có hai số nguyên p, q thỏa mãn pa1 + qa2 = Từ quan hệ a1 a2 − a1 − a2 a3 = a1 a3 p + a2 a3 q = a1 a2 + (a3 p − a2 )a1 + a2 a3 q suy (a3 p−a2 +1)a1 +a2 (a3 q +1) Dễ dàng thấy a3 p−a2 < a3 q < Vì thế, cách thêm bớt a1 a2 , cần thiết, để có biểu diễn a3 = a1 a2 −k1 a1 −k2 a2 23 với số nguyên k1 , k2 Ta có (a2 − k1 )a1 = k2 a2 + a3 Vì k2 a2 − k1 > Vậy a2 − k1 l1 theo định nghĩa l1 nhận l1 < a2 : mâu thuẫn với điều kiện l1 a2 Do nij nên i = j ta có (ii) (iii) Đặt γ1 = l1 − n21 − n31 , γ2 = l2 − n12 − n32 , γ3 = l3 − n13 − n23 Xét γ1 a1 + γ2 a2 + γ3 a3 = (l1 − n21 − n31 )a1 + (l2 − n12 − n32 )a2 + (l3 − n13 − n23 )a3 = (l1 a1 − n12 a2 − n13 a3 ) + (l2 a2 − n21 a1 − n23 a3 ) + (l3 a3 − n31 a1 − n32 a2 ) = Ta nhận tổng γ1 a1 +γ2 a2 +γ3 a3 = Bây ta chứng minh γ1 = γ2 = γ3 = phương pháp phản chứng Giả sử γ1 , γ2 , γ3 không đồng thời Vì a1 , a2 , a3 > nên xảy khả ba số γ1 , γ2 , γ3 dấu Vậy, ta cần xét hai trường hợp sau đây: (i) γ1 > 0, γ2 < 0, γ3 (ii) γ1 > 0, γ2 > 0, γ3 < Xét trường hợp (i): Từ quan hệ γ1 a1 + γ2 a2 + γ3 a3 = ta suy biến đổi (l1 − n21 − n31 )a1 = γ1 a1 = −γ2 a2 − γ3 a3 = (−γ2 )a2 + (−γ3 )a3 > Từ suy (l1 − n21 − n31 )a1 ∈ L(a2 , a3 ) Theo định nghĩa l1 ta có l1 − n21 − n31 l1 với n21 , n31 1, điều xảy Xét trường hợp (ii): Từ quan hệ γ1 a1 + γ2 a2 + γ3 a3 = ta suy biến đổi (n13 + n23 − l3 )a3 = (−γ3 )a3 = γ1 a1 + γ2 a2 Từ suy n13 + n23 − l3 > (n13 + n23 − l3 )a3 ∈ L(a1 , a2 ) Theo định nghĩa l3 ta có n13 + n23 − l3 n23 l3 ; chẳng hạn: n13 l3 hay n13 + n23 2l3 Do n13 l3 l3 Bởi l1 a1 = n12 a2 + n13 a3 l3 a3 = n31 a1 + n32 a2 nên ta có (l1 − n31 )a1 = (n12 + n32 )a2 + (n13 − l3 )a3 ∈ L(a2 , a3 ) Vậy l1 − n31 > l1 − n31 l1 với n31 Từ điều vô lý suy γ1 = γ2 = γ3 = hay l1 = n21 + n31 , l2 = n12 + n32 , l3 = n13 + n23 ta có (iii) Tính biểu diễn li hiển nhiên ta có (i) 24 Bây ta tìm cơng thức tính số Frobenius cho trường hợp n = với ba số nguyên dương a1 , a2 , a3 đôi nguyên tố Trong lưới nguyên Z3 ⊂ R3 với thứ tự từ điển ta coi Z3 tập đỉnh đồ thị định hướng T, cạnh đồ thị T đoạn thẳng với độ dài nối đỉnh lân cận Xét hàm tuyến tính f : R3 → R, (x1 , x2 , x3 ) → a1 x1 + a2 x2 + a3 x3 Hạt nhân Ker f = {(x1 , x2 , x3 )|a1 x1 + a2 x2 + a3 x3 = 0} mặt phẳng R3 phần giao với lưới nguyên L = Z3 ∩ Ker f = {(x1 , x2 , x3 ) ∈ Z3 |a1 x1 + a2 x2 + a3 x3 = 0} gọi lưới Frobenius Dễ thấy rằng, hai số nguyên m1 , m2 thỏa mãn m1 a1 + m2 a2 = e1 = (a2 , −a1 , 0) e2 = (m1 a3 , m2 a3 , −1) sở Ker f Bổ đề 2.1.16 Giả sử hai số nguyên m1 , m2 thỏa mãn m1 a1 + m2 a2 = Khi e1 = (a2 , −a1 , 0) e2 = (m1 a3 , m2 a3 , −1) sở Ker f điểm thuộc L = Z3 ∩ Ker f tổ hợp tuyến tính với hệ số nguyên e1 , e2 Hơn ta cịn có e1 × e2 = (a1 , a2 , a3 ) Chứng minh: Vì e1 , e2 độc lập tuyến tính f (a2 , −a1 , 0) = a1 a2 − a2 a1 = f (m1 a3 , m2 a3 , −1) = a1 m1 a3 + a2 m2 a3 − a3 = nên e1 , e2 sở Ker f Giả sử (a, b, c) ∈ Z3 ∩ Ker f Xét hệ phương trình tuyến tính đây: x(a2 , −a1 , 0) + y(m1 a3 , m2 a3 , −1) = (a, b, c) Giải y = −c ∈ Z x = m2 a − m1 b ∈ Z Mệnh đề 2.1.17 [Blatter] Giả sử ba số nguyên dương a1 , a2 , a3 đôi nguyên tố ký hiệu li , nij định nghĩa thỏa mãn 4li 2, i = 1, 2, Khi ta có G(a1 , a2 , a3 ) = l1 l2 l3 + max{n12 n23 n31 , n21 n13 n32 } − i=1 2.2 2.2.1 Về Số Frobenius g(a1, a2, a3, a4) Một vài kết g(a1 , a2 , a3 , a4 ) Tuy chưa giải vấn đề xác định cụ thể tập C(A) công thức tường minh xác định số Frobenius g(a1 , , an ), nhiều nhà toán học xây dựng 25 thuật toán đưa chặn cho số g(a1 , , an ) Mục trình bày lại số công thức xác định chặn Trước tiên chứng minh lại hai kết A Brauer J E Shockley: On a problem Frobenius, J Reine Angewandte Math 211, 1975, 215-220 Bổ đề 2.2.1 [Brauer and Shockley] Với tj số nguyên dương nhỏ thỏa mãn phương trình tj ≡ j(mod an ) ta ln có hệ thức g(a1 , , an ) = max{tj |j = 1, 2, , an − 1} − an Chứng minh: Giả sử r số nguyên dương Nếu r ≡ 0(mod an ) r tổ hợp nguyên không âm an Nếu r ≡ j(mod an ) r tổ hợp ngun khơng âm a1 , a2 , , an r tj Từ suy kết cần chứng minh Bổ đề 2.2.2 [Brauer and Shockley] Giả sử d = (a1 , , an−1 ) Khi ta có g(a1 , , an ) = dg a1 an−1 , , , an + (d − 1)an d d n Chứng minh: Giả sử G = G(a1 , , an ) = g(a1 , , an ) + Đây số i=1 n xi số nguyên nguyên dương lớn không tổ hợp nguyên i=1 dương với số nguyên xi Hiển nhiên, phương trình g(a1 , , an ) = a1 an−1 dg , , , an + (d − 1)an tương đương d d n G(a1 , , an ) − i=1 a1 an−1 , , , an − d = dG d d hay G(a1 , , an ) = dG n−1 n−1 i=1 − dan + (d − 1)an d a1 an−1 , , , an Bây ta G(a1 , , an ) = d d xi với số nguyên dương thích hợp xi > Thật vậy, an +G(a1 , , an ) > i=1 G(a1 , , an ) nên an + G(a1 , , an ) viết n−1 x i + an x n , ∀ x i an + G(a1 , , an ) = i=1 n−1 xi + an (xn − 1), ∀ xi Từ suy G(a1 , , an ) = n y i , ∀ y i G(a1 , , an ) = i=1 Nếu xn > i=1 1, mâu thuãn với định nghĩa G(a1 , , an ) Do 26 n−1 xn = G(a1 , , an ) = xi với số nguyên dương thích hợp xi > i=1 n−1 Đặt = dbi , i = 1, , n − 1, ta có G = n−1 i=1 cho d Đặt G = bi xi suy G chia hết x i = d i=1 G d (∗) Ta G không tổ hợp nguyên dương b1 , , bn−1 , an Thật vậy, G tổ hợp nguyên dương b1 , , bn−1 , an ta có biểu diễn n−1 bi yi + an yn , ∀ yj > Ta nhận mâu thuẫn G = i=1 n−1 yi + an dyn , ∀ yj > G = dG = i=1 (∗∗) Ta số nguyên T > G tổ hợp nguyên dương b1 , , bn−1 , an Thật vậy, dT > dG = G nên dT tổ hợp nguyên dương n−1 n a1 , , an−1 , an với biểu diễn dT = bi zi , ∀ zj > Vì zi = an zn + d i=1 i=1 (d, an ) = nên zn chia hết cho d Đặt zn = dyn Khi ta nhận n−1 bi zi , ∀ zj > 0, yn > T = an y n + i=1 Từ kết (∗ (∗∗) ta suy G = G(b1 , , bn−1 , an ) với phương trình G = dG ta suy hệ thức cần chứng minh G(a1 , , an ) = dG a1 an−1 , , , an d d Bây ta vận dụng Bổ đề 2.2.2 để chứng minh lại chặn cho số Frobenius A Brauer đưa báo [On a problem of partitions, Am J Math 64, 1942,299-312] Định lý 2.2.3 [Brauer] Giả sử ước chung lớn di = (a1 , , ) cho i = n−1 1, , n Với ký hiệu T (a1 , , an ) = i=1 ai+1 di ta ln có di+1 n g(a1 , , an ) T (a1 , , an ) − i=1 a1 ai+1 a1 , , , g , , Dấu = xảy di di di+1 di di a a a phụ thuộc vào , , i Do di = a1 t1 + · · · + ti nên i+1 = di di di+1 Chứng minh: Chú ý g ai+1 di+1 27 ti a a a ai+1 a1 t1 + ··· + suy i+1 phụ thuộc vào , , i Từ ta có di+1 di di di+1 di di a1 ai+1 a1 g , , , = g , , Sử dụng Bổ đề 2.2.2 ta suy bất di di di+1 di di đẳng thức Trong báo [On a problem of partitions II, Am J Math 64, 1954,343-346] A Brauer B M Seelbinder Định lý 2.2.4 [Brauer and Seelbinder] Giả sử ước chung lớn di = n−1 (a1 , , ) cho i = 1, , n Với ký hiệu T (a1 , , an ) = i=1 ai+1 di ta ln có di+1 n g(a1 , , an ) − min{a1 , , an } T (a1 , , an ) − i=1 Trong giảng đọc Berlin năm 1935, nhà toán học Schur chứng minh kết sau đây: Định lý 2.2.5 [Schur] Giả thiết (a1 , , an ) = < a1 ··· a2 an Khi (a1 − 1)(an − 1) − g(a1 , , an ) Bằng cách sử dụng Lý thuyết Graph, số nhà toán học chứng minh số kết thú vị số Frobenius sau đây: Định lý 2.2.6 [Dulmage and Mendelsohn] Giả sử a số nguyên không âm Khi ta có (1) g(a, a + 1, a + 2, a + 4) = (a + 1) a a+1 a+2 + +2 − 4 (2) g(a, a + 1, a + 2, a + 5) = (a + 1) a a+2 a+1 + + 5 (3) g(a, a + 1, a + 2, a + 6) = a + a+4 + a+5 a +2 a +2 a+1 +5 +2 a+2 −1 Định lý 2.2.7 [Vitek] g(a1 , a2 , a3 , a4 ) a+3 (a4 − 3)(a4 − 2) − + −1 a+3 28 2.2.2 Một số ví dụ bổ sung Mệnh đề 2.2.8 Nếu a1 , a2 , , an ∈ N∗ đơi ngun tố số lớn không viết thành dạng a1 a2 an ( xn x1 x2 + +· · ·+ ) với x1 , , xn ∈ a1 a2 an 1 − − ··· − ) Đặc biệt, n = số lớn a1 a2 an x x x không viết thành dạng a1 a2 a3 + + với x1 , x2 , x3 ∈ N số a1 a2 a3 1 − − [IMO 1983] a1 a2 a3 − a1 a2 a3 N số a1 a2 an (n − − Chứng minh: Quy nạp theo n Với n = 2, số lớn không biểu diễn thành dạng a1 x1 + a2 x2 với x1 , x2 ∈ N x1 a2 − số a1 (a2 − 1) − a2 = 1 a1 a2 (2 − − − ) Giả sử kết luận cho n Ta kết luận a1 a2 cho n + Thật vậy, (a1 an , an+1 ) = nên số nguyên k có biểu diễn k = a1 a2 an an+1 x xn+1 + a1 an an+1 an+1 − x, xn+1 ∈ Z Theo giả thiết quy nạp, x có biểu x x x diễn x = a1 a2 an + + · · · + n với x1 , , xn ∈ Z x2 a1 a2 an a2 − 1, x3 a3 − 1, , xn an − 1, x1 tùy thuộc vào x Vậy x1 x2 xn xn+1 k = a1 a2 an an+1 ( + +···+ + ) với x1 , , xn , xn+1 ∈ Z a1 a2 an an+1 x2 a2 − 1, x3 a3 − 1, , xn an − 1, xn+1 an+1 − Từ kết x x x này, số nguyên lớn không viết thành dạng a1 a2 an ( + +· · ·+ n ) a1 a2 an a2 − an − −1 với x1 , , xn ∈ N số a1 a2 an ( + + ··· + ) hay a1 a2 an 1 a1 a2 an (n − − − − · · · − ) a1 a2 an với xn+1 Hệ 2.2.9 Nếu a1 , a2 , , an ∈ N+ (a1 , , an ) = số nhỏ x1 x2 xn + + ··· + ) với x1 , , xn ∈ N số a1 a2 an 1 a1 a2 an (n − − − − · · · − ) + a1 a2 an viết thành dạng a1 a2 an ( Ví dụ 2.2.10 Tìm số nguyên lớn không biểu diễn thành dạng 7a + 11b + 13c với ba số nguyên a, b, c Bài giải: Vì (7, 11) = (11, 13) = nên theo Mệnh đề 2.2.8 số nguyên r có biểu diễn r = 7α + 11β + 13u với α 10 β 12, cịn u ∈ Z Vậy số ngun lớn khơng biểu diễn thành dạng 7a+11b+13c với ba số nguyên a, b, c số T = 7.10 + 11.12 + 13(−1) = 189 Chú ý 190 = 7.7 + 11.1 + 13.10 188 = 7.7 + 11.2 + 13.9 29 Ví dụ 2.2.11 Tìm số ngun lớn không biểu diễn thành dạng 7a + 11b + 13c với ba số nguyên a, b, c số lớn không viết thành dạng x1 x2 x3 7.11.13( + + ) với x1 , x2 , x3 ∈ N 11 13 Bài giải: Vì (7, 11) = (11, 13) = nên theo Mệnh đề 2.2.8 số nguyên r có biểu diễn r = 7α + 11β + 13u với α 10 β 12, u ∈ Z Vậy số nguyên lớn không biểu diễn thành dạng 7a + 11b + 13c với ba số nguyên a, b, c số T = 7.10 + 11.12 + 13(−1) = 189 Chú ý 190 = 7.7+11.1+13.10 188 = 7.7+11.2+13.9 Số lớn không viết thành dạng x1 x2 x3 1 7.11.13( + + ) với x1 , x2 , x3 ∈ N số 7.11.13(2 − − − ) = 1691 11 13 11 13 Ví dụ 2.2.12 Giả thiết n số nguyên dương Tìm số nguyên lớn không biểu diễn thành dạng (2n − 1).2na + 2n.(2n + 1)b + (2n + 1)(2n − 1)c với ba số nguyên a, b, c số nguyên lớn không biểu diễn thành dạng (2n − 1)α + 2nβ + (2n + 1)u với α, β, u nguyên, u α 2n − 1, β 2n Bài giải: Vì ba số 2n − 1, 2n, 2n + đôi nguyên tố nên theo Mệnh đề 2.2.8 số nguyên lớn không viết thành dạng (2n − 1).2n.(2n + a b c 1 + + − − với a, b, c ∈ N số (2n−1).2n.(2n+1) 2− 2n − 2n 2n + 2n − 2n = 16n − 12n − 4n + Số nguyên lớn không biểu diễn thành 2n + dạng (2n − 1)α + 2nβ + (2n + 1)u với α, β, u nguyên, α 2n − 1, β 2n 1) u số (2n − 1).(2n − 1) + 2n.2n + (2n + 1)(−1) = 8n2 − 6n Vấn đề Frobenius: Ta nhận thấy, số nguyên dương (a1 , , an ) = số nguyên dương b đủ lớn, chẳng hạn b n−1 (an − 1) , biểu diễn thành tổ hợp tuyến tính ngun khơng i=1 âm b = a1 α1 + · · · + an αn với αi nguyên theo Định lý 1.1.2 Khi tồn số nguyên không âm nhỏ G(a1 , , an ) để cho số nguyên b G(a1 , , an ) biểu diễn thành tổ hợp tuyến tính ngun khơng âm b = a1 α1 + · · · + an αn Vấn đề Frobenius đặt : Xác định số nguyên G(a1 , , an ) cho tất tập hữu hạn số nguyên dương a1 , , an với (a1 , , an ) = Đây vấn đề mở mà đến chưa giải Người ta giải số trường hợp đặc biệt Ví dụ 2.2.13 Giả thiết số a1 , , an ∈ N∗ , (a1 , , an ) = 1, > với i Khi số G(a1 , , an ) tồn 30 Bài giải: Vì (a1 , , an ) = nên có số nguyên mi ∈ Z để m1 a1 + m2 a2 + · · · + mk ak +· · ·+mn an = 1, (*) Đánh số lại cần thiết, ta coi m1 , m2 , , mk < 0, mk+1 , , mn Xét số b = (1−a1 )m1 a1 +(1−a1 )m2 a2 +· · ·+(1−a1 )mk ak Do (1 − a1 )mk > nguyên nên b có biểu diễn dạng b = α1 a1 + · · · + an an với αi nguyên Giả sử số nguyên d > b Viết d − b = a1 p + r với r < a1 , p, r ∈ N Khi d = b + a1 p + r = (1 − a1 )m1 a1 + (1 − a1 )m2 a2 + · · · + (1 − a1 )mk ak + a1 p + r.1 = [(1 + r − a1 )m1 + p]a1 + [1 + r − a1 ]m2 a2 + · · · + [1 + r − a1 ]mk ak + rmk+1 ak+1 + · · · + rmn an Như vậy, biểu diễn d thành tổ hợp tuyến tính khơng âm a1 , a2 , , an Vì lớn nên khơng thể tổ hợp tuyến tính khơng âm a1 , , an Do đó, số từ đến b − phải có số ngun dương lớn khơng biểu diễn thành tổ hợp tuyến tính khơng âm a1 , , an G(a1 , , an ) tồn 31 Kết luận Trong luận văn chúng tơi trình bày lại kết sau: (1) Giới thiệu toán đổi tiền vấn đề Frobenius (2) Trình bày lại thuật tốn Euclide để tìm ước chung lớn hai số (3) Giới thiệu vài thuật toán xác định số g(a, b, c) trường hợp đặc biệt (4) Trình bày lại độ phức tạp tính tốn (5) Chứng minh lại công thức xác định số g(a, b) (6) Giới thiệu vài công thức chặn chặn số Frobenius với n 32 Tài liệu tham khảo [1] Hà Huy Khoái(1997), Nhập mơn số học thuật tốn, Nhà xuất Khoa học [2] D Q Việt Đ V Nhỉ(2007), Cơ sở lý thuyết số đa thức, Nhà xuất ĐHSP Hà Nội [3] T Andreescu, D Andrica and I Cucurezeanu(2010), An Introduction to Diophantine Equations, Birkhauser [4] M Beck, R Diaz and S Robin (2002), The Frobenius problem, rational polytopes, and Fourier- Dedekind sums, J Number Theory, 96(1), 1-21 [5] A Brauer and J.E Shockley (1962), On a problem of Frobenius, J Reine Ange Math 211 , 215-220 [6] J S Byrnes (1974), On a partition problem of Frobenius, J Comb Theor Sec A, 17, 162-166 [7] J L Davison(1994), On the linear diophantine of Frobenius, J Number Theory, 48, 353-363 [8] P Erdos and R L Graham (1972), On linear diophantine problem of Frobenius, Acta Arithmetica, 21, 399-408 [9] S M Johnson (1960), A linear diophantine problem, Can J Math 12, 390-398 [10] J L Ramíez Alfonsín (2005), The diophantine Frobenius problem, Oxford University Press CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự - Hạnh phúc ————————————— BẢN XÁC NHẬN Xác nhận luận văn chỉnh sửa theo ý kiến kết luận Hội đồng bảo vệ luận văn Người hướng dẫn khoa học PGS TS Đàm Văn Nhỉ Xác nhận sở đào tạo ... tính số Frobenius 1.4.1 Độ phức tạp 1.4.2 Một vài số chặn chặn số Frobenius 3 6 8 11 12 13 13 14 Số Frobenius 2.1 Số Frobenius cho n = 2, n = 2.1.1 Số Frobenius. .. xác định số Frobenius n số cho vấn đề P 1.4.2 Một vài số chặn chặn số Frobenius Một số nhà toán học quan tam đến số Frobenius đưa chặn hay chặn cho số √ (1) [Davison 1994] g(a, b, c) 3abc − a −... 2.1.2 Tiếp cận số Frobenius qua hàm sinh 2.1.3 Về Số Frobenius g(a, b, c) 2.1.4 Một vài công thức chặn 2.2 Về Số Frobenius g(a1 , a2 , a3 , a4 ) 2.2.1 Một vài kết g(a1 , a2