Luận văn Thạc sĩ Toán học: Bài toán đổi tiền của Frobenius

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

17
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Fredinand Georg Frobenius (1849 - 1917) là một nhà toán học người Đức nổi tiếng với những đóng góp trong lý thuyết hàm Eliptic, phương trình vi phân và lý thuyết nhóm. Bài toán Diophantine tuyến tính của ông có những ứng dụng quan trọng trong nhiều lĩnh vực khác nhau của toán học như lý thuyết số, lý thuyết tự động và tổ hợp. Luận văn sẽ đi sâu nghiên cứu về vấn đề này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Bài toán đổi tiền của Frobenius

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGỤY PHƢƠNG HOÀI BÀI TOÁN ĐỔI TIỀN CỦA FROBENIUS LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGỤY PHƢƠNG HOÀI BÀI TOÁN ĐỔI TIỀN CỦA FROBENIUS Chuyên ngành: Phƣơng pháp Toán sơ cấp Mã số: 8460113 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Hoàng Lê Trƣờng THÁI NGUYÊN - 2018
Mục lục MỞ ĐẦU 1 1 Bài toán đổi tiền của Frobenius 3 1.1 Hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Hai hệ đồng xu . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Phân thức đơn giản và công thức Frobenius . . . . . . . . . 17 1.4 Kết quả của Sylvester . . . . . . . . . . . . . . . . . . . . . 22 1.5 Số Frobenius cho hai đồng xu . . . . . . . . . . . . . . . . . 25 1.6 Định lý của Sylvester . . . . . . . . . . . . . . . . . . . . . 29 2 Một số vấn đề mở rộng 33 2.1 Ba đồng xu và nhiều đồng xu . . . . . . . . . . . . . . . . . 33 2.2 Số Frobenius cho các tập đặc biệt . . . . . . . . . . . . . . 39 2.2.1 Số Frobenius cho cấp số cộng . . . . . . . . . . . . . 39 2.2.2 Số Frobenius cho cấp số nhân . . . . . . . . . . . . . 40 2.3 Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Kết luận 45 Tài liệu tham khảo 46
MỞ ĐẦU Fredinand Georg Frobenius (1849 - 1917) là một nhà toán học người Đức nổi tiếng với những đóng góp trong lý thuyết hàm Eliptic, phương trình vi phân và lý thuyết nhóm. Bài toán Diophantine tuyến tính của ông có những ứng dụng quan trọng trong nhiều lĩnh vực khác nhau của toán học như lý thuyết số, lý thuyết tự động và tổ hợp. Một ví dụ nổi tiếng của bài toán Diophantine tuyến tính của Frobenius là "Bài toán đổi tiền của Frobenius": Cho trước k loại tiền có mệnh giá là các số tự nhiên nguyên tố cùng nhau, xác định khoản tiền lớn nhất không thể đổi thành các loại tiền trên. Cũng có nhiều ví dụ trong số học sơ cấp dạng như: Tìm khoản tiền lớn nhất không thể đổi được thành các loại tiền mệnh giá 3 xu, 5 xu, 7 xu. Bài toán Frobenius đã được giải quyết cho trường hợp hai số. Ta đã biết công thức tính số Frobenius của hai số tự nhiên a, b nguyên tố cùng nhau là ab − a − b và số nguyên dương không biểu diễn được qua a, b là 1 (a − 1)(b − 1). Nhưng việc giải quyết với trường hợp nhiều hơn hoặc bằng 2 3 số là vô cùng khó và đến nay vẫn là một bài toán mở. Trong luận văn này, tôi trình bày một cách có hệ thống một vài kết quả quan trọng của Bài toán đổi tiền của Frobenius. Mục tiêu chính của luận văn là trả lời câu hỏi khi nào một khoản tiền cho trước có thể đổi thành những đồng tiền với mệnh giá cho trước, xác định khoản tiền lớn nhất không thể đổi được và xác định có bao nhiêu cách để đổi tiền. Chính vì vậy, chúng tôi đã chọn đề tài “Bài toán đổi tiền của Frobenius” làm chủ đề nghiên cứu cho luận văn. Bố cục của luận văn gồm mở đầu, hai chương, kết luận và tài liệu tham khảo. Trong chương 1, chúng tôi giới thiệu sơ lược về bài toán đổi tiền của 1
Frobenius, trình bày công thức Frobenius cho trường hợp hai số và kết quả của Sylvester. Bài toán Frobenius cho hai đồng xu và chứng minh định lý của Sylvester cũng được trình bày ở phần cuối Chương 1. Chương 2 trình bày một số kết quả về trường hợp đặc biệt của bài toán Frobenius cho ba số và cho các tập đặc biệt. Cuối chương này chúng tôi có trình bày hai ví dụ thực tế tương tự với bài toán đổi tiền của Frobenius. Với tình cảm chân thành, tác giả xin được bày tỏ lòng biết ơn đến trường Đại học Khoa học – Đại học Thái Nguyên, Phòng Đào tạo, Khoa Toán – Tin, quý thầy cô giáo giảng dạy lớp cao học Toán K10 đã tận tình hướng dẫn, tạo mọi điều kiện cho tác giả trong suốt quá trình học tập, nghiên cứu và hoàn thành luận văn. Đặc biệt, tác giả xin bày tỏ lòng biết ơn sâu sắc đến TS. Hoàng Lê Trường, người thầy trực tiếp giảng dạy, hướng dẫn khoa học. Với những kiến thức, kinh nghiệm quý báu, thầy đã ân cần chỉ bảo giúp đỡ tác giả tự tin, vượt qua những khó khăn, trở ngại trong quá trình nghiên cứu để hoàn thành luận văn. Xin được bày tỏ lòng biết ơn của tác giả đến các bạn học viên, các đồng nghiệp, người thân đã động viên, giúp đỡ, tạo điều kiện thuận lợi để tác giả hoàn thành khóa học. Xin chân thành cảm ơn ! Tác giả Ngụy Phương Hoài 2
Chương 1 Bài toán đổi tiền của Frobenius Trong chương này, chúng tôi trình bày một số kiến thức chuẩn bị như hàm sinh, các ứng dụng của hàm sinh để tìm hàm phân hoạch có giới hạn, từ đó chứng minh được bài toán Frobenius cho hai số nguyên tố cùng nhau. Bài toán Frobenius cùng các ví dụ trong luận văn giúp trả lời câu hỏi số tiền lớn nhất không xuất hiện khi dùng hệ thống tiền mới hay số điểm cao nhất không xuất hiện trong trò chơi là bao nhiêu. Phần cuối của chương cũng trình bày một số kết quả về số Frobenius trong trường hợp ba số và trong trường hợp đặc biệt của cấp số cộng, cấp số nhân. 1.1 Hàm sinh Hàm sinh có nhiều ứng dụng của toán rời rạc cũng như lý thuyết số. Hàm sinh giúp ta chuyển những bài toán về dãy số thành những bài toán về hàm số. Với điều này chúng ta có thể dễ dàng giải quyết được một số bài toán. Giả sử chúng ta khảo sát một dãy số vô hạn (ak )∞ k=0 phát sinh trong hình học hoặc theo kiểu đệ quy (truy hồi). Tìm một “công thức chính xác” để tính giá trị ak theo chỉ số k ? Có bao nhiêu cách xác định ak khác nhau? Chuyển dãy số này vào hàm sinh X F (z) = ak z k k≥0 cho phép chúng ta tìm ra câu trả lời cho các câu hỏi trên một cách vô cùng 3
nhanh chóng và dễ dàng. Chúng ta coi hàm F (z) như kết quả của việc chuyển đổi dãy số (ak ) từ hàm rời rạc sang hàm liên tục. Để minh họa cho các khái niệm này, chúng ta sẽ bắt đầu bằng ví dụ cổ điển về dãy Fibonacci fk được đặt tên theo tên của nhà toán học Leonardo Pisano Fibonacci và được định nghĩa bởi công thức truy hồi f0 = 0, f1 = 1, và fk+2 = fk+1 + fk với k ≥ 0. Từ đó ta có giá trị dãy số (fk )∞ k=0 = (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .). Bây giờ chúng ta hãy xem hàm sinh có thể mang lại kết quả gì cho chúng ta. Nhắc lại hàm sinh của dãy Fibonacci (fk )∞ k=0 là X F (z) := fk z k . k≥0 Chúng ta đặt hai vế của công thức truy hồi vào hàm sinh như dưới đây X X X X k k k fk+2 z = (fk+1 + fk )z = fk+1 z + fk z k . (1.1) k≥0 k≥0 k≥0 k≥0 Vế trái của đẳng thức (1.1) bằng X 1 X 1 X 1 fk+2 z k = f k+2 z k+2 = f k z k = (F (z) − z). k≥0 z 2 k≥0 z 2 k≥2 z2 Trong khi đó vế phải của đẳng thức (1.1) có giá trị X X 1 fk+1 z k + fk z k = F (z) + F (z). k≥0 k≥0 z Theo đó, đẳng thức (1.1) có thể viết lại như sau 1 1 (F (z) − z) = F (z) + F (z), z2 z hoặc z F (z) = . 1 − z − z2 4
Khi chúng ta khai triển hàm F (z) thành một chuỗi lũy thừa, chúng ta sẽ có được dãy số Fibonacci là hệ số của chuỗi như dưới đây z = z + z 2 + 2z 3 + 3z 4 + 5z 5 + 8z 6 + 13z 7 + 21z 8 + 34z 9 + . . . . 1 − z − z2 Bây giờ ta sử dụng phương pháp giải hàm hữu tỷ thường dùng: phương pháp khai triển phân thức hữu tỷ thành các phân thức hữu tỷ đơn giản. Xét trường hợp của chúng ta, phần mẫu số là √ ! √ ! 1 + 5 1 − 5 1 − z − z2 = 1 − z 1− z 2 2 và khi khai triển thành các phân thức hữu tỷ đơn giản, ta có √ √ z 1/ 5 1/ 5 F (z) = = √ − √ . (1.2) 1 − z − z2 1+ 5 1− 5 1− z 1− z 2 2 Hai biểu thức trên được khai triển thành các chuỗi thông qua chuỗi hình học X 1 xk = (1.3) k≥0 1−x √ √ 1+ 5 1− 5 với giá trị tương ứng x = z và x = z . Từ đó, ta thu được 2 2 ∞ √ !k ∞ √ !k z 1 X 1+ 5 1 X 1− 5 F (z) = =√ z −√ z 1 − z − z2 5 k≥0 2 5 k≥0 2 ∞  √ !k √ !k  1 X  1+ 5 1− 5  k =√ − z . 5 k≥0 2 2 So sánh các hệ số của z k trong định nghĩa F (z) = fk z k với các hệ số P k≥0 k của z trong biểu thức F (z) bên trên, chúng ta nhận được công thức √ !k √ !k 1 1+ 5 1 1− 5 fk = √ −√ 5 2 5 2 5
cho dãy Fibonacci. Phương pháp phân tích một hàm sinh hữu tỷ thành các phân thức đơn giản như trên là một trong những công cụ toán học quan trọng của chúng ta. Bởi vì chúng ta sẽ sử dụng phương pháp phân tích đa thức hữu tỷ thành đa thức đơn giản nên chúng ta phát biểu chuẩn tắc phương pháp này bởi định lý sau đây. Định lý 1.1.1 (Khai triển phân thức đơn giản). Cho hàm hữu tỷ p(z) F (z) := Qm ek , k=1 (z − ak ) trong đó p là một đa thức có bậc nhỏ hơn e1 + e2 + . . . + em và ak là các số phân biệt, khi đó tồn tại phép phân tích m X ck,1 ck,2 ck,ek F (z) = + + ... + , k=1 z − ak (z − ak )2 (z − ak )ek trong đó ck,j ∈ C là giá trị duy nhất. 1.2 Hai hệ đồng xu Hãy tưởng tượng chúng ta đưa ra một hệ thống đồng tiền mới. Thay vì việc sử dụng các đồng 1 cent, đồng 5 cent, 10 cent và 25 cent, chúng ta đồng ý sử dụng các đồng 4 cent, 7cent, 9 cent và 34 cent. Chúng ta có thể chỉ ra được nhược điểm của hệ thống đồng tiền mới này như sau: một vài số tiền trong hệ thống cũ là không thể đổi được sang số tiền trong hệ thống mới (trừ các đồng tiền có sẵn), ví dụ 2 hoặc 5 cent. Tuy nhiên, chính nhược điểm này làm cho hệ thống đồng tiền mới này thú vị hơn hệ thống đồng tiền cũ, vì chúng ta có thể đặt ra câu hỏi “có thể thu được tổng giá trị tiền không đổi được là bao nhiêu?”. Thực tế khi sử dụng hệ thống tiền mới này chúng ta có ít hơn tiền cũ và do đó phần dư không đổi được biến mất khỏi thực tế. Một câu hỏi tự nhiên đặt ra, số tiền lớn nhất không thể đổi có giá trị bao nhiêu? Câu hỏi này đã nhận được câu trả lời đầu tiên bởi Ferdinand Georg 6
Frobenius (1849-1917), và James Joseph Sylvester (1814-1897). Chúng ta muốn đặt ra một câu hỏi mang tính khái quát chung nhất có thể. Vì thế chúng ta đưa ra câu hỏi còn được gọi là bài toán đổi tiền của Frobenius như sau: Bài 1.2.1 (Bài toán đổi tiền của Frobenius). Đối với các đồng tiền có mệnh giá a1 , a2 , . . . , ad là các số nguyên dương có ước chung lớn nhất bằng 1, câu hỏi đặt ra là: có thể đưa ra công thức số tiền lớn nhất không thể có được bằng cách sử dụng đồng tiền a1 , a2 , . . . , ad ? Để phát biểu cụ thể về mặt toán học, chúng ta có một tập hợp số nguyên dương A = {a1 , a2 , . . . , ad } với gcd(a1 , a2 , . . . , ad ) = 1. Định nghĩa 1.2.2. Số nguyên dương n được gọi là biểu diễn được bằng tập số A trên nếu tồn tại các số nguyên không âm m1 , m2 , . . . , md sao cho n = m1 a1 + m2 a2 + . . . + md ad . Ví dụ 1.2.3. Cho tập số A = {2, 3, 5, 7}. Khi đó, các số 13 = 0 · 2 + 2 · 3 + 0 · 5 + 1 · 7, 15 = 0 · 2 + 5 · 3 + 0 · 5 + 0 · 7, 28 = 14 · 2 + 0 · 3 + 0 · 5 + 0 · 7, nên chúng biểu diễn được theo A. Xét về ngôn ngữ đồng tiền, điều này có nghĩa là chúng ta có thể đổi được n thành các đồng xu a1 , a2 , . . . , ad . Bài toán Frobenius (thường được gọi là bài toán Diophantine tuyến tính của Frobenius) yêu cầu chúng ta tìm ra số nguyên lớn nhất không thể biểu diễn thông qua các số nguyên không âm a1 , a2 , . . . , ad như trên. 7
Định nghĩa 1.2.4. Số nguyên lớn nhất không thể biểu diễn thông qua các số nguyên không âm a1 , a2 , . . . , ad như trên được gọi là số Frobenius và kí hiệu là g(a1 , a2 , . . . , ad ). Giả thiết gcd(a1 , a2 , . . . , ad ) = 1 là cần thiết để số Frobenius tồn tại. Nếu ước chung lớn nhất khác 1, tất cả các số nguyên không là bội của gcd(a1 , a2 , . . . , ad ) sẽ không thể biểu diễn được dưới dạng tổ hợp tuyến tính của các số trong A. Do đó, có thể không tồn tại số lớn nhất không thể biểu diễn thông qua A, có nghĩa là có thể không tồn tại số Frobenius nếu gcd(a1 , a2 , . . . , ad ) 6= 1. Ví dụ 1.2.5. Nếu ta có hai đồng 4 cent và 6 cent, ước chung lớn nhất là 2, không có cách kết hợp một số lượng bất kỳ hai đồng xu này để thu được tổng là một số lẻ. Mặt khác, khi ước chung lớn nhất bằng 1, theo định lý Schur, tập các số nguyên không thể biểu diễn được bằng tổ hợp tuyến tính của {a1 , a2 , . . . , ad } bị chặn, và do đó số Frobenius tồn tại. Trong lý thuyết tổ hợp, định lý Schur cho biết số cách biểu diễn một số cho trước thành tổ hợp tuyến tính (nguyên, không âm) của một tập cố định gồm các số nguyên tố cùng nhau. Định lý 1.2.6 (Schur). Cho {a1 , . . . , ad } là một tập các số nguyên sao cho gcd(a1 , a2 , . . . , ad ) = 1, số các bộ số nguyên không âm (c1 , . . . , cd ) khác nhau sao cho x = c1 a1 + · · · + cd ad khi x dần tới vô cùng là xd−1 (1 + o(1)). (n − 1)!a1 · · · ad Nói cách khác, với mọi tập các số nguyên tố cùng nhau {a1 , . . . , ad }, tồn tại một giá trị của x sao cho với số lớn hơn nó đều biểu diễn được thành tổ hợp tuyến tính của {a1 , . . . , an } theo ít nhất một cách. Hệ quả này của định lý Schur có thể được lặp lại trong một ngữ cảnh quen thuộc, xét bài toán Frobenius đổi một số tiền bằng cách sử dụng một tập hợp 8
tiền xu. Nếu mệnh giá của đồng xu là các số nguyên tố cùng nhau thì bất kỳ số tiền đủ lớn nào cũng có thể đổi được chỉ bằng những đồng tiền này. Nếu d = 1 thì a1 = 1 nên tất cả các số tự nhiên đều có thể biểu diễn được qua a1 . Do đó, không tồn tại số Frobenius trong trường hợp d = 1. Định lý dưới đây cho ta một công thức với d = 2. Định lý 1.2.7. Nếu a1 và a2 là các số nguyên dương nguyên tố cùng nhau thì g(a1 , a2 ) = a1 a2 − a1 − a2 . Ví dụ 1.2.8. Cho A1 = {3, 4}. Khi đó a1 = 3 và a2 = 4 là các số nguyên dương nguyên tố cùng nhau. Theo định lý trên thì g(3, 4) = g(a1 , a2 ) = a1 a2 − a1 − a2 = 12 − 3 − 4 = 5 là số nguyên lớn nhất không thể biểu diễn được thông qua các số trong A1 . Các số nguyên 6, 7, 8, 9, . . . đều biểu diễn được thông qua A1 . Ví dụ 1.2.9. Cho A2 = {7, 8}. Khi đó a1 = 7 và a2 = 8 là các số nguyên dương nguyên tố cùng nhau. Theo định lý trên thì g(7, 8) = g(a1 , a2 ) = a1 a2 − a1 − a2 = 56 − 7 − 8 = 41 là số nguyên lớn nhất không thể biểu diễn được thông qua các số trong A2 . Tất cả các số nguyên 42, 43, 44, . . . đều biểu diễn được thông qua A2 . Ví dụ các 43 = 5 · 7 + 8, 44 = 4 · 7 + 2 · 8. Định lý 1.2.10 (Định lý Sylvester). Cho a1 và a2 là hai số nguyên dương nguyên tố cùng nhau. Đúng một nửa số nguyên nằm trong khoảng 1 và (a1 − 1)(a2 − 1) có thể biểu diễn theo {a1 , a2 }. Mục đích của chúng ta trong chương này là chứng minh hai định lý trên (và đi xa hơn một chút) bằng cách khai triển thành phân thức đơn giản. Chúng ta tiếp cận bài toán Frobenius bằng cách nghiên cứu các hàm phân hoạch có giới hạn. 9
Định nghĩa 1.2.11. Một phân hoạch của số nguyên dương n là một tập các số nguyên dương {n1 , n2 , . . . , nk } (n1 ≤ n2 ≤ . . . ≤ nk ) sao cho n = n1 + n2 + · · · + nk . Các số n1 , n2 , . . . , nk được gọi là các phần của phép phân hoạch. Định nghĩa 1.2.12. Số cách phân hoạch của số nguyên dương n chỉ sử dụng các phần tử của A = {a1 , . . . , ad } được xác định bởi hàm phân hoạch sau pA (n) := #{(m1 , . . . md ) ∈ Zd : mọi mj ≥ 0, m1 a1 + . . . + md ad = n}. Xét ở khía cạnh hàm đơn giản, g(a1 , a2 , . . . , ad ) là số nguyên dương n lớn nhất để pA (n) = 0. Chúng ta có một cách giải thích hình học khá đẹp về hàm phân hoạch có giới hạn, biểu diễn hình học bắt đầu với tập số P = {(x1 , x2 , . . . , xd ) ∈ Rd : mọi xj ≥ 0, x1 a1 + x2 a2 + . . . + xd ad = 1}. (1.4) Mở rộng thứ n của tập số bất kỳ S ⊆ Rd được định nghĩa bởi {(nx1 , nx2 , . . . , nxd ) : (x1 , x2 , . . . , xd ) ∈ S} . Bài toán 1.2.13. Cho trước một đồng tiền và một hệ thống các đồng tiền. Khi đó chúng ta muốn biết có bao nhiêu cách đổi đồng tiền thành các đồng tiền cho trước. Cách tiếp cận bài toán ở đây là sử dụng hàm sinh. Cụ thể về mặt toán học, chúng ta có một tập hợp các số nguyên dương A = {a1 , . . . , ad } sao cho gcd(a1 , . . . , ad ) = 1. Khi đó hàm phân hoạch pA (n) là hàm đếm số cách đổi một đồng tiền n thành các đồng có mệnh giá a1 , . . . , ad . Các số không âm m1 , . . . , md trong phương trình n = m1 a1 + . . . + md ad có thể xem như một điểm nguyên trong không gian Rd . Do đó chúng ta có thể xem tập các cách đổi tiền như là tập các điểm nguyên (X1 , X2 , . . . , Xd ) trong không gian Rd mà thỏa mãn phương trình n = X1 a1 + . . . + Xd ad . Từ đó, 10
chúng ta có thể mô tả hình học tập các cách đổi tiền bởi các siêu mặt trong không gian Rn . Cụ thể ở đây tập các siêu mặt là X1 a1 + . . . + Xd ad = 1 và Xi ≥ 0 với mọi i = 1, . . . , d. Như vậy ta có một biểu diễn hình học khá đẹp về hàm đơn giản có giới hạn. Chúng ta có mô tả hình học bắt đầu với tập số P = {(x1 , x2 , . . . , xd ) ∈ Rd : ∀xj ≥ 0, x1 a1 +x2 a2 +. . .+xd ad = 1}. (1.5) Mở rộng nth trong tập số P ⊆ Rd là nP := {(nx1 , nx2 , . . . , nxd ) : (x1 , x2 , . . . , xd ) ∈ P } . y n b 1 b n a x 1 1 a c n c z Hình 1.1: Hình đa diện P với d = 3. Hàm pA (n) được tính một cách chính xác các điểm số nguyên trong Zd nằm trong dãy mở rộng số nguyên dương nth của tập số P . Tập Zd là một ví dụ về một mạng lưới, và các điểm số nguyên thường được gọi là điểm 11
lưới. Quá trình mở rộng tập hợp số trong tình huống này trong bối cảnh này tương đương với việc thay thế x1 a1 + . . . ..xd ad = 1 trong định nghĩa P với x1 a1 + . . . ..xd ad = n. Tập số P biểu diễn thành một hình đa diện. Chúng ta có thể dễ dàng vẽ hình biểu diễn P và tập số mở rộng cho d ≤ 3; Hình 1.1 thể hiện hình không gian 3 chiều. Ví dụ 1.2.14. Với d = 2, a1 = 3, a2 = 5 ta có P = {(x1 , x2 ) ∈ R2 : mọi xj ≥ 0, 3x1 + 5x2 = 1}. Mở rộng thứ 2 của P là tập {(2x1 , 2x2 ) : (x1 , x2 ) ∈ P } = {(2x1 , 2x2 ) ∈ R2 : x1 ≥ 0, x2 ≥ 0, 3x1 + 5x2 = 1} = {(x1 , x2 ) ∈ R2 : x1 ≥ 0, x2 ≥ 0, 3x1 + 5x2 = 2}. Tương tự, mở rộng thứ 3 của P là tập {(3x1 , 3x2 ) : (x1 , x2 ) ∈ P } = {(3x1 , 3x2 ) ∈ R2 : x1 ≥ 0, x2 ≥ 0, 3x1 + 5x2 = 1} = {(x1 , x2 ) ∈ R2 : x1 ≥ 0, x2 ≥ 0, 3x1 + 5x2 = 3}. Và tiếp tục cho các mở rộng khác. Ví dụ 1.2.15. Chúng ta bắt đầu với với d = 2, a1 = 3, a2 = 5. Khi đó chúng ta bắt đầu với đa diện P = {(x1 , x2 ) ∈ R2 : ∀xj ≥ 0, 3x1 + 5x2 = 1}. Bây giờ chúng ta tính hàm P{3,5} (n) = |nP ∩ Z2 | thông qua đếm các điểm trong nP . Với n = 1, chúng ta thấy rằng không có điểm nguyên không âm nào nằm trên đường thẳng 3x1 + 5x2 = 1. Do đó P{3,5} (1) = 0. Với n = 2, chúng ta thấy rằng không có điểm nguyên 12
không âm nào nằm trên đường thẳng 3x1 + 5x2 = 2. Do đó P{3,5} (2) = 0. Với n = 3, chúng ta thấy rằng có duy nhất điểm nguyên không âm (1, 0) nằm trên đường thẳng 3x1 + 5x2 = 3. Do đó P{3,5} (3) = 1. Với n = 4, chúng ta thấy rằng không có điểm nguyên không âm nào nằm trên đường thẳng 3x1 + 5x2 = 4. Do đó P{3,5} (4) = 0. Với n = 5, chúng ta thấy rằng có duy nhất điểm nguyên không âm (0, 1) nằm trên đường thẳng 3x1 + 5x2 = 5. Do đó P{3,5} (5) = 1. Với n = 6, chúng ta thấy rằng có duy nhất điểm nguyên không âm (2, 0) nằm trên đường thẳng 3x1 + 5x2 = 6. Do đó P{3,5} (6) = 1. Với n = 7, chúng ta thấy rằng không có điểm nguyên không âm nào nằm trên đường thẳng 3x1 + 5x2 = 7. Do đó P{3,5} (7) = 0. Với n = 8, chúng ta thấy rằng có duy nhất điểm nguyên không âm (1, 1) nằm trên đường thẳng 3x1 + 5x2 = 8. Do đó P{3,5} (8) = 1. Với n = 9, chúng ta thấy rằng có duy nhất điểm nguyên không âm (3, 0) nằm trên đường thẳng 3x1 + 5x2 = 9. Do đó P{3,5} (9) = 1. Với n = 10, chúng ta thấy rằng có duy nhất điểm nguyên không âm (0, 2) nằm trên đường thẳng 3x1 + 5x2 = 10. Do đó P{3,5} (10) = 1. Với n = 11, chúng ta thấy rằng có duy nhất điểm nguyên không âm (2, 1) nằm trên đường thẳng 3x1 + 5x2 = 11. Do đó P{3,5} (11) = 1. Với n = 12, chúng ta thấy rằng có duy nhất điểm nguyên không âm (4, 0) nằm trên đường thẳng 3x1 + 5x2 = 12. Do đó P{3,5} (12) = 1. Với n = 13, chúng ta thấy rằng có duy nhất điểm nguyên không âm (1, 2) nằm trên đường thẳng 3x1 + 5x2 = 13. Do đó P{3,5} (12) = 1. Với n = 14, chúng ta thấy rằng có duy nhất điểm nguyên không âm (3, 1) nằm trên đường thẳng 3x1 + 5x2 = 14. Do đó P{3,5} (12) = 1. Với n = 15, chúng ta thấy rằng có 2 điểm nguyên không âm (5, 0),(0, 3) nằm trên đường thẳng 3x1 + 5x2 = 15. Do đó P{3,5} (12) = 2. Trong phần tiêp theo chúng ta sẽ chỉ ra công thức tính cụ thể P{3,5} (n) thông qua 3 và 5. n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P{3,5} (n) 0 0 1 0 1 1 0 1 1 1 1 1 1 1 2 13
3 2 1 1 2 3 4 5 Hình 1.2: Các số nguyên không âm thỏa mãn 3x + 5y = n, với n = 0, 1, 2, ... . Ví dụ 1.2.16. Chúng ta bắt đầu với với d = 2, a1 = 2, a2 = 3. Khi đó chúng ta bắt đầu với đa diện P = {(x1 , x2 ) ∈ R2 : ∀xj ≥ 0, 2x1 + 3x2 = 1}. Bây giờ chúng ta tính hàm P{2,3} (n) = |nP ∩ Z2 | thông qua đếm các điểm trong nP . Với n = 1, chúng ta thấy rằng không có điểm nguyên không âm nào nằm trên đường thẳng 2x1 + 3x2 = 1. Do đó P{2,3} (1) = 0. Với n = 2, chúng ta thấy rằng có duy nhất điểm nguyên không âm (1, 0) nằm trên đường thẳng 2x1 +3x2 = 2. Do đó P{2,3} (2) = 1. Với n = 3, chúng ta thấy rằng có duy nhất điểm nguyên không âm (0, 1) nằm trên đường thẳng 2x1 + 3x2 = 3. Do đó P{2,3} (3) = 1. Với n = 4, chúng ta thấy rằng có duy nhất điểm nguyên không âm (2, 0) nằm trên đường thẳng 2x1 + 3x2 = 4. Do đó P{2,3} (4) = 1. Với n = 5, chúng ta thấy 14
rằng có duy nhất điểm nguyên không âm (1, 1) nằm trên đường thẳng 2x1 + 3x2 = 5. Do đó P{2,3} (5) = 1. Với n = 6, chúng ta thấy rằng có duy nhất điểm nguyên không âm (0, 2) nằm trên đường thẳng 2x1 + 3x2 = 6. Do đó P{2,3} (6) = 1. Với n = 7, chúng ta thấy rằng có duy nhất điểm nguyên không âm (2, 1) nằm trên đường thẳng 2x1 + 3x2 = 7. Do đó P{2,3} (7) = 1. Với n = 8, chúng ta thấy rằng có 2 điểm nguyên không âm (4, 0) và (1, 2) nằm trên đường thẳng 2x1 + 3x2 = 8. Do đó P{2,3} (8) = 2. Với n = 9, chúng ta thấy rằng có 2 điểm nguyên không âm (0, 3) và (3, 1) nằm trên đường thẳng 2x1 + 3x2 = 9. Do đó P{2,3} (9) = 2. Với n = 10, chúng ta thấy rằng có 2 điểm nguyên không âm (5, 0), (2, 2) nằm trên đường thẳng 2x1 + 2x2 = 10. Do đó P{2,3} (10) = 2. Với n = 11, chúng ta thấy rằng có 2 điểm nguyên không âm (4, 1), (1, 3) nằm trên đường thẳng 2x1 + 3x2 = 11. Do đó P{2,3} (11) = 2. Với n = 12, chúng ta thấy rằng có 3 điểm nguyên không âm (6, 0) (3, 2), 0, 4 nằm trên đường thẳng 2x1 + 2x2 = 12. Do đó P{2,3} (12) = 3. Với n = 13, chúng ta thấy rằng có 2 điểm nguyên không âm (5, 1), (2, 3) nằm trên đường thẳng 2x1 +3x2 = 13. Do đó P{2,3} (13) = 2. Với n = 14, chúng ta thấy rằng có 3 điểm nguyên không âm (7, 0), (4, 2), (1, 4) nằm trên đường thẳng 2x1 + 3x2 = 14. Do đó P{2,3} (14) = 3. Với n = 15, chúng ta thấy rằng có 3 điểm nguyên không âm (6, 1), (3, 3), (0, 5) nằm trên đường thẳng 2x1 + 3x2 = 15. Do đó P{2,3} (15) = 3. Trong phần tiêp theo chúng ta sẽ chỉ ra công thức tính cụ thể P{2,3} (n) thông qua 2 và 3. n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P{3,5} (n) 0 1 1 1 1 1 1 2 2 2 2 3 2 3 3 15
3 2 1 1 2 3 4 5 Hình 1.3: Các số nguyên không âm thỏa mãn 2x + 3y = n với n = 0, 1, 2, .... Ví dụ 1.2.17. Chúng ta bắt đầu với với d = 2, a1 = 3, a2 = 4. Khi đó chúng ta bắt đầu với đa diện P = {(x1 , x2 ) ∈ R2 : ∀xj ≥ 0, 3x1 + 4x2 = 1}. Bây giờ chúng ta tính hàm P{3,4} (n) = |nP ∩ Z2 | thông qua đếm các điểm trong nP . Với n = 1, chúng ta thấy rằng không có điểm nguyên không âm nào nằm trên đường thẳng 3x1 +4x2 = 1. Do đó P{3,4} (1) = 0. Với n = 2, chúng ta thấy rằng không có điểm nguyên không âm nào nằm trên đường thẳng 3x1 + 4x2 = 2. Do đó P{2,3} (2) = 0. Với n = 3, chúng ta thấy rằng có duy nhất điểm nguyên không âm (1, 0) nằm trên đường thẳng 3x1 + 4x2 = 3. Do đó P{3,4} (3) = 1. Với n = 4, chúng ta thấy rằng có duy nhất điểm nguyên không âm (0, 1) nằm trên đường thẳng 3x1 + 4x2 = 4. Do đó P{2,3} (4) = 1. Với n = 5, chúng ta thấy rằng không có điểm nguyên không âm nào nằm trên đường thẳng 3x1 + 4x2 = 5. Do 16
đó P{3,4} (5) = 0. Với n = 6, chúng ta thấy rằng có duy nhất điểm nguyên không âm (2, 0) nằm trên đường thẳng 3x1 +4x2 = 6. Do đó P{3,4} (6) = 1. Với n = 7, chúng ta thấy rằng có duy nhất điểm nguyên không âm (1, 1) nằm trên đường thẳng 3x1 + 4x2 = 7. Do đó P{3,4} (7) = 1. Với n = 8, chúng ta thấy rằng có 1 điểm nguyên không âm (0, 2) nằm trên đường thẳng 3x1 + 4x2 = 8. Do đó P{3,4} (8) = 1. Với n = 9, chúng ta thấy rằng có 1 điểm nguyên không âm (3, 0) nằm trên đường thẳng 3x1 +4x2 = 9. Do đó P{3,4} (9) = 1. Với n = 10, chúng ta thấy rằng có 1 điểm nguyên không âm (2, 1) nằm trên đường thẳng 3x1 + 4x2 = 10. Do đó P{3,4} (10) = 1. Với n = 11, chúng ta thấy rằng có 1 điểm nguyên không âm (1, 2) nằm trên đường thẳng 3x1 + 4x2 = 11. Do đó P{3,4} (11) = 1. Với n = 12, chúng ta thấy rằng có 2 điểm nguyên không âm (4, 0) (0, 3) nằm trên đường thẳng 3x1 + 4x2 = 12. Do đó P{3,4} (12) = 2. Với n = 13, chúng ta thấy rằng có 1 điểm nguyên không âm (3, 1) nằm trên đường thẳng 3x1 + 4x2 = 13. Do đó P{3,4} (13) = 1. Với n = 14, chúng ta thấy rằng có 1 điểm nguyên không âm (2, 2) nằm trên đường thẳng 3x1 + 4x2 = 14. Do đó P{3,4} (14) = 1. Với n = 15, chúng ta thấy rằng có 2 điểm nguyên không âm (5, 0), (1, 3) nằm trên đường thẳng 3x1 + 5x2 = 11. Do đó P{3,4} (15) = 2. Trong phần tiêp theo chúng ta sẽ chỉ ra công thức tính cụ thể P{3,4} (n) thông qua 3 và 4. n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P{3,4} (n) 0 0 1 1 0 1 1 1 1 1 1 2 1 1 2 1.3 Phân thức đơn giản và công thức Frobenius Trước hết, chúng ta tập trung vào các trường hợp d = 2 và tiến hành nghiên cứu p{a,b} (n) = # (k, l) ∈ Z2 : k, l ≥ 0, ak + bl = n . Lưu ý chúng ta yêu cầu a, b là nguyên tố cùng nhau, tập hợp số nguyên dương A chỉ có hai số, A = {a, b}. Chúng ta bắt đầu thảo luận vấn đề 17