ĐẠ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
(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
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 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.
1
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
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ả
2
Ngụy Phương Hoài
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
1.1 Hàm sinh
ba số và trong trường hợp đặc biệt của cấp số cộng, cấp số nhân.
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.
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
Giả sử chúng ta khảo sát một dãy số vô hạn (ak)∞
F (z) =
akzk
k≥0
(cid:88)
3
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
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.
f0 = 0, f1 = 1, và fk+2 = fk+1 + fk với k ≥ 0.
Để 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
(fk)∞
k=0 = (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .).
Từ đó ta có giá trị dãy số
k=0 là
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)∞
F (z) :=
fkzk.
k≥0
(cid:88)
Chúng ta đặt hai vế của công thức truy hồi vào hàm sinh như dưới đây
fk+2zk =
(fk+1 + fk)zk =
fk+1zk +
fkzk.
k≥0
k≥0
k≥0
k≥0
(cid:88) (cid:88) (cid:88) (cid:88) (1.1)
Vế trái của đẳng thức (1.1) bằng
fk+2zk+2 =
fkzk =
fk+2zk =
1 z2
1 z2
1 z2 (F (z) − z).
k≥0
k≥2
k≥0
(cid:88) (cid:88) (cid:88)
Trong khi đó vế phải của đẳng thức (1.1) có giá trị
F (z) + F (z).
fk+1zk +
fkzk =
1 z
k≥0
k≥0
(cid:88) (cid:88)
F (z) + F (z),
1 z2 (F (z) − z) =
1 z
Theo đó, đẳng thức (1.1) có thể viết lại như sau
F (z) =
z 1 − z − z2 .
4
hoặc
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ẽ
z
1 − z − z2 = z + z2 + 2z3 + 3z4 + 5z5 + 8z6 + 13z7 + 21z8 + 34z9 + . . . . Bây giờ ta sử dụng phương pháp giải hàm hữu tỷ thường dùng: phương
có được dãy số Fibonacci là hệ số của chuỗi như dưới đây
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à
5
5
z
1 −
z
1 − z − z2 =
1 −
1 + 2
1 − 2
(cid:33) (cid:32) (cid:33) (cid:32)
√
√
5 √
5 √
và khi khai triển thành các phân thức hữu tỷ đơn giản, ta có
F (z) =
−
.
z 1 − z − z2 =
5
5
z
z
1 −
1 −
1/ 1 + 2
1/ 1 − 2
(1.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
xk =
1 1 − x
k≥0 √
√
5
5
học (cid:88) (1.3)
z và x =
z. Từ đó, ta thu được
1 + 2
1 − 2
√
√
với giá trị tương ứng x =
5
5
∞ (cid:88)
∞ (cid:88)
−
F (z) =
z
z
z 1 − z − z2 =
1 + 2
1 √ 5
1 √ 5
k≥0
k≥0
(cid:33)k (cid:32) (cid:33)k (cid:32)
√
√
1 − 2 (cid:33)k
5
5
∞ (cid:88)
=
−
(cid:32) (cid:33)k (cid:32)
1 + 2
1 − 2
1 √ 5
k≥0
fkzk với các hệ số
zk.
So sánh các hệ số của zk trong định nghĩa F (z) = (cid:80) k≥0
√
√
của zk trong biểu thức F (z) bên trên, chúng ta nhận được công thức
5
5
−
fk =
1 + 2
1 − 2
1 √ 5
1 √ 5
5
(cid:33)k (cid:32) (cid:32) (cid:33)k
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.
F (z) :=
,
Định lý 1.1.1 (Khai triển phân thức đơn giản). Cho hàm hữu tỷ
p(z) k=1(z − ak)ek
(cid:81)m
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
ck,2
m (cid:88)
+
F (z) =
,
(cid:19)
(z − ak)2 + . . . +
ck,ek (z − ak)ek
k=1 trong đó ck,j ∈ C là giá trị duy nhất.
1.2 Hai hệ đồng xu
(cid:18) ck,1 z − ak
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
6
nhiêu? Câu hỏi này đã nhận được câu trả lời đầu tiên bởi Ferdinand Georg
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ố
A = {a1, a2, . . . , ad}
nguyên dương
với gcd(a1, a2, . . . , ad) = 1.
n = m1a1 + m2a2 + . . . + mdad.
Đị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
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,
Ví dụ 1.2.3. Cho tập số A = {2, 3, 5, 7}. Khi đó, các số
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
7
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.
Đị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) (cid:54)= 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.
(1 + o(1)).
xd−1 (n − 1)!a1 · · · ad
Đị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 = c1a1 + · · · + cdad khi x dần tới vô cùng là
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,
8
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
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.
g(a1, a2) = a1a2 − a1 − a2.
Đị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(3, 4) = g(a1, a2) = a1a2 − a1 − a2 = 12 − 3 − 4 = 5
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ì
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.
g(7, 8) = g(a1, a2) = a1a2 − a1 − a2 = 56 − 7 − 8 = 41
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ì
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
9
hoạch có giới hạn.
Đị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.
pA(n) := #{(m1, . . . md) ∈ Zd : mọi mj ≥ 0, m1a1 + . . . + mdad = n}.
Đị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
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
P = {(x1, x2, . . . , xd) ∈ Rd : mọi xj ≥ 0, x1a1 + x2a2 + . . . + xdad = 1}. (1.4)
có giới hạn, biểu diễn hình học bắt đầu với tập số
{(nx1, nx2, . . . , nxd) : (x1, x2, . . . , xd) ∈ S} .
Mở rộng thứ n của tập số bất kỳ S ⊆ Rd được định nghĩa bởi
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.
10
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 = m1a1 + . . . + mdad 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 = X1a1 + . . . + Xdad. Từ đó,
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à X1a1 + . . . + Xdad = 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
P = {(x1, x2, . . . , xd) ∈ Rd : ∀xj ≥ 0, x1a1 +x2a2 +. . .+xdad = 1}. (1.5)
tập số
nP := {(nx1, nx2, . . . , nxd) : (x1, x2, . . . , xd) ∈ P } .
y
n b
1 b
x
n a
1 a
1 c
n c
z
Hình 1.1: Hình đa diện P với d = 3.
Mở rộng nth trong tập số P ⊆ Rd là
11
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
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ế x1a1 + . . . ..xdad = 1 trong định nghĩa P với x1a1 + . . . ..xdad = 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.
P = {(x1, x2) ∈ R2 : mọi xj ≥ 0, 3x1 + 5x2 = 1}.
Ví dụ 1.2.14. Với d = 2, a1 = 3, a2 = 5 ta có
{(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}.
Mở rộng thứ 2 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}.
Tương tự, mở rộng thứ 3 của P là tập
Và tiếp tục cho các mở rộng khác.
P = {(x1, x2) ∈ R2 : ∀xj ≥ 0, 3x1 + 5x2 = 1}.
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{3,5}(n) = |nP ∩ Z2|
Bây giờ chúng ta tính hàm
12
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
n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2
1
1
1
1
1
P{3,5}(n) 0 0 1 0 1 1 0 1 1
13
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.
G1J1K1L1
3
2
1
1
2
3
5
4
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, ... .
P = {(x1, x2) ∈ R2 : ∀xj ≥ 0, 2x1 + 3x2 = 1}.
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{2,3}(n) = |nP ∩ Z2|
Bây giờ chúng ta tính hàm
14
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
n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3
3
2
3
2
2
P{3,5}(n) 0 1 1 1 1 1 1 2 2
15
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.
G1J1K1L1
3
2
1
1
2
3
5
4
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, ....
P = {(x1, x2) ∈ R2 : ∀xj ≥ 0, 3x1 + 4x2 = 1}.
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{3,4}(n) = |nP ∩ Z2|
Bây giờ chúng ta tính hàm
16
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
n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2
1
1
2
1
1
P{3,4}(n) 0 0 1 1 0 1 1 1 1
1.3 Phân thức đơn giản và công thức Frobenius
đó 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.
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
p{a,b}(n) = # (cid:8)(k, l) ∈ Z2 : k, l ≥ 0, ak + bl = n(cid:9) .
nghiên cứu
17
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 đề
xoay quanh các hàm sinh. Xét tích của hai chuỗi hình học dưới đây:
= (1 + za + z2a + . . .)(1 + zb + z2b + . . .).
1 − za
1 − zb
(cid:19) (cid:18) 1 (cid:19) (cid:18) 1
=
zakzbl =
p{a,b}(n)zn.
1 − za
1 − zb
n≥0
k≥0
l≥0
(cid:19) Nhân tất cả các số hạng với nhau, ta thu được một chuỗi lũy thừa có số mũ là tổ hợp tuyến tính của a và b. Trong thực tế, hệ số zn trong chuỗi lũy thừa này là số cách có thể biểu diễn n ở dạng tổ hợp tuyến tính không âm của a và b. Nói cách khác, các hệ số này là đánh giá chính xác hàm đếm p{a,b} của chúng ta: (cid:18) 1 (cid:19) (cid:18) 1 (cid:88) (cid:88) (cid:88)
n=0.
(cid:17) Vì vậy hàm là hàm sinh cho chuỗi các số nguyên (cid:0)p{a,b}(n)(cid:1)∞ (cid:16) 1 1−za
(cid:17) (cid:16) 1 1−zb Bây giờ chúng ta sẽ nghiên cứu hàm ở vế trái.
Chúng ta muốn tìm ra một công thức thú vị cho p{a,b}(n) bằng cách xem xét kỹ hàm sinh ở vế trái. Để việc tính toán dễ dàng hơn, chúng ta nghiên cứu số hạng tự do của một chuỗi liên quan, cụ thể là p{a,b}(n) là một số hạng tự do của chuỗi
f (z) :=
p{a,b}(k)zk−n.
1 (1 − za)(1 − zb)zn =
k≥0
(cid:88)
Chuỗi số trên không thực sự là một chuỗi lũy thừa bởi vì nó có chứa các số
hạng với số mũ âm. Chuỗi số này được gọi là chuỗi Laurent, đặt tên theo
tên nhà toán học Pierre Alphonse Laurent (1813-1854). Đối với một chuỗi lũy thừa (giá trị giữa = 0), chúng ta có thể tính giá trị của hàm tương ứng tại z = 0 để thu được số hạng tự do; khi chuỗi có số mũ âm thì ta không
thể áp dụng cách tính này. Tuy nhiên, nếu đầu tiên chúng ta trừ đi tất cả
các số hạng có số mũ âm, chúng ta sẽ có được một chuỗi lũy thừa có các
số hạng tự do (không thay đổi) có thể được tính toán bằng cách tính giá trị của hàm còn lại này tại z = 0.
18
Để có thể tính toán được số hạng tự do này, chúng ta sẽ sử dụng phương pháp phân tích đa thức hữu tỷ f thành các phân thức hữu tỷ đơn giản. Để
+ i sin
.
ξa := e2πi/a = cos
2π a
2π a
thực hiện phân tích phân thức đơn giản, trước hết chúng ta tiến hành thực hiện thông qua một ví dụ một chiều. Biểu diễn nghiện e2πi/a của phương trình 1 − za thông qua ξa
a, . . . , ξa−1
a, ξ3
a
. Khi đó tổ hợp tất cả các nghiệm e2πi/a của phương trình 1 − za sẽ có dạng 1, ξa, ξ2
1 1 − za .
Ví dụ 1.3.1. Hãy xác định khai triển của phân thức
a−1 (cid:88)
.
1 1 − za =
Ck z − ξk a
k=0
Giải. Các điểm cực của hàm này được nằm tại tất cả các nghiệm e2πi/a của phương trình 1 − za . Cụ thể là tại ξk a, ∀k = 0, 1, . . . , a − 1. Do đó chúng ta có thể khai triển thành
Để xác định hệ số Ck chúng ta làm như sau
z
1
.
Ck = limz→ξk
= limz→ξk
(z−ξk a)
a
a
a
1 − za
−aza−1 = limz→ξk
−aza = −
ξk a a
(cid:19) (cid:18) 1
Ở đây, chúng ta đã sử dụng quy tắc của L’Hôpital cho đẳng thức thứ hai.
1
a−1 (cid:88)
.
1 − za = −
1 a
ξk a z − ξk a
k=0
Do đó, chúng ta có được khai triển
(cid:3)
a−1 (cid:88)
b−1 (cid:88)
f (z) =
+
+
+
A1 z
A2 z2 + . . . +
An zn +
B1 z − 1
B2 (z − 1)2 +
Ck z − ξk a
j=1
k=1
Dj z − ξj b (1.6)
19
Trở lại với phân thức f , các cực điểm của f là tại z = 0 với bội n, tại z = 1 với bội số 2 và tại tất cả các nghiệm của phương trình 1 − za và 1 − zb với bội số 1 bởi vì a và b nguyên tố cùng nhau. Theo đó, phân thức hữu tỷ f được khai triển như dưới đây:
,
Ck = −
a
với
.
Dj = −
(1.7)
b
1 a ) ξk(n−1) a (1 − ξkb 1 1 − ξja b
ξj(n−1) b
(cid:16) (cid:17)
.
B2 = limz→1
(z − 1)2 (1 − za)(1 − zb)zn =
1 ab
Để tính B2, chúng ta nhân cả hai vế của đẳng thức (1.6) với (z − 1)2, lấy giới hạn z → 1 và áp dụng quy tắc L’Hôpital hai lần, thu được
Đối với hệ số B1, bằng cách áp dụng hai lần quy tắc L’Hôpital, chúng ta tính toán được
=
−
−
−
.
B1 = limz→1(z−1)
1 (1 − za)(1 − zb)zn −
1 ab (z − 1)2
1 ab
1 2a
1 2b
n ab
(cid:32) (cid:33)
Ta không cần phải tính toán các hệ số A1, . . . , An, bởi vì chúng chỉ tạo ra các số hạng có số mũ âm, do đó chúng ta có thể bỏ qua mà không ảnh hưởng gì vì các số hạng này không đóng góp gì cho số hạng tự do của f .
a−1 (cid:88)
b−1 (cid:88)
+
+
p{a,b}(n) =
Khi chúng ta tính được các hệ số khác, như chúng ta đã đề cập ở trên, số hạng tự do trong chuỗi Laurent của f sẽ được tính tại 0 như dưới đây
B2 (z − 2)2 +
Ck z − ξk a
Dj z − ξj b
j=1
k=1
a−1 (cid:88)
b−1 (cid:88)
−
.
= −B1 + B2 −
Ck ξk a
Dj ξj b
j=1
k=1
(cid:18) B1 z − 1 (cid:19)(cid:12) (cid:12) (cid:12) (cid:12)z=0
Thay các hệ số tại (1.7) vào đẳng thức trên, khi đó đẳng thức được rút
a−1 (cid:88)
b−1 (cid:88)
+
+
+
+
. (1.8)
p{a,b}(n) =
1 2a
1 2b
n ab
1 a
1 b
1 a )ξkn (1 − ξkb a
1 b )ξjn (1 − ξja
b
j=1
k=1
gọn thành
Bây giờ chúng ta tiến hành phân tích từng tổng trong (1.8) để đưa chúng
20
trở về dạng thức quen thuộc hơn.
Để thực hiện bước tiếp theo, chúng ta cần xác định hàm nguyên lớn nhất (cid:98)x(cid:99), là số nguyên lớn nhất có giá trị nhỏ hơn hoặc bằng x. Đi cùng với hàm này là hàm phần thập phân {x} = x − (cid:98)x(cid:99).
Ví dụ 1.3.2. Cho x = 3.4, khi đó (cid:98)x(cid:99) = (cid:98)3.4(cid:99) = 3 và {x} = x − (cid:98)x(cid:99) = 3.4 − 3 = 0.4. Cho y = 5.0 thì (cid:98)y(cid:99) = (cid:98)5(cid:99) = 5 = y và {y} = {5} = 5 − (cid:98)5(cid:99) = 5 − 5 = 0.
Tiếp theo, chúng ta sẽ nghiên cứu trường hợp đặc biệt với b = 1. Trường hợp này khá thú vị, do p{a,1}(n) đơn giản là đếm số điểm nguyên trong từng khoảng:
n a
p{a,1}(n) = # (cid:8)(k, l) ∈ Z2 : k, l ≥ 0, ak + l = n(cid:9) = # {k ∈ Z : k ≥ 0, ak ≤ n} k ∈ Z : 0 ≤ k ≤ (cid:107)
=
+ 1.
= # (cid:106)n a
(cid:111) (cid:110)
Mặt khác, chúng ta vừa tìm một biểu thức khác cho hàm này, do đó
a−1 (cid:88)
+ 1.
+
+
+
= p{a,1}(n) =
1 2a
1 2
n a
1 a
(cid:107)
1 a)ξkn (1 − ξk a
k=1
(cid:106)n a
Thông qua hàm phần thập phân {x} = x − [x], chúng ta rút ra công thức cho tổng dưới đây trên tất cả các nghiệm e2πi/a của phương trình 1 − za
a−1 (cid:88)
= −
+
−
.
1 a
1 2
1 2a
1 a)ξkn (1 − ξk a
k=1
(cid:111) (1.9) (cid:110)n a
a−1 (cid:88)
a−1 (cid:88)
Đến đây, chúng ta gần tính ra kết quả. Dựa vào đẳng thức
,
=
1 a
1 a
1 a )ξkn (1 − ξbk a
1 a)ξb−1kn (1 − ξk a
k=1
k=1
(1.10)
trong đó b−1 là một số nguyên và b−1b ≡ 1 (mod a), ta đi đến kết luận là
a−1 (cid:88)
+
= −
−
.
1 a
1 2
1 2a
1 a )ξkn (1 − ξbk a
k=1
21
(cid:27) (1.11) (cid:26)b−1n a
Bây giờ việc cần làm là thay biểu thức này vào công thức (1.8), ta chứng
minh được định lý sau đây, thu được một công thức đẹp mà được tìm ra
bởi Peter Barlow (1776-1862) và (theo dạng thức chúng ta nêu ở đây) bởi
Tiberiu Popoviciu (1906-1975).
Định lý 1.3.3 (Công thức Barlow-Popoviciu). Nếu a và b là nguyên tố
cùng nhau thì
−
−
+ 1,
p{a,b}(n) =
n ab
(cid:27) (cid:27)
(cid:26)b−1n a (cid:26)a−1n b
trong đó b−1b ≡ 1 (mod a) và a−1a ≡ 1 (mod b).
Hệ quả 1.3.4. Cho các số nguyên dương a và b nguyên tố cùng nhau. Gọi p và q là các số nguyên dương sao cho aq − bp = 1. Khi đó
−
p{a,b}(n) =
(cid:23) (cid:107) nếu a không chia hết n,
−
1.4 Kết quả của Sylvester
(cid:107) nếu a chia hết n. (cid:106) qn b (cid:106) qn b (cid:22)pn a pn a
Trước khi chúng ta áp dụng Định lý 1.3.3 để chứng minh các Định lý
ax + by = n,
x, y ≥ 0.
1.2.7 và 1.2.10, chúng ta hãy dành chút thời gian trở lại với hình học gắn với hàm phân hoạch có giới hạn p{a,b}(n). Trong trường hợp không gian 2 chiều (tình huống trong Định lý 1.3.3), chúng ta đang tính toán số điểm nguyên (x, y) ∈ Z2 trên các đoạn thẳng được xác định bằng các ràng buộc
0,
, 0
n b
, 0
0,
,
n b
(cid:16) (cid:17) (cid:17) Như vậy đoạn thẳng này kết nối các điểm và , chúng ta biểu (cid:16)n a (cid:104)(cid:16) (cid:17)(cid:105) (cid:17) thị đoạn thẳng này bằng .
x và y trong Rd như sau
[x, y] := {λx + (1 − λ)y : 0 ≤ λ ≤ 1},
22
(cid:16)n a Tổng quát hơn, chúng ta định nghĩa đoạn thẳng khép kín nối các điểm
0,
, 0
,
n b
(cid:104)(cid:16) (cid:17)(cid:105) (cid:17) sẽ mở rộng. Trong thực Khi giá trị n tăng, đoạn thẳng và chúng ta sẽ sử dụng các ký hiệu thông thường tương tự để biểu thị đoạn thẳng mở (x, y) và đoạn thẳng nửa mở (x, y]. (cid:16)n a
n ab
tế, người ta thậm chí có thể đoán rằng số lượng điểm trên đoạn thẳng tăng tuyến tính theo n, bởi vì đoạn thẳng là đối tượng 1 chiều. Định lý 1.3.3 xác định nhận định trên một cách chính xác: p{a,b}(n) có “số hạng dẫn , và các số hạng còn lại chịu ràng buộc theo các hàm của n. Hình đầu”
Hình 1.4: Các số nguyên không âm thỏa mãn 4x + 7y = n, với n = 0, 1, 2, . . .
1.4 cho thấy dạng hình học của hàm đếm p{4,7} áp dụng với một số giá trị đầu tiên của n.
Nhận xét 1.4.1. Chúng ta lưu ý rằng, theo Định lý 1.2.7, ứng với n = a · b − a − b = 4 · 7 − 4 − 7 = 17 là số nguyên lớn nhất không biểu diễn được thông qua {4, 7}. Trong Hình 1.4, đường thẳng tô đậm ứng với n = 17 là
đường thẳng cuối cùng không chứa điểm nguyên nào, tất cả những đường ứng với n > 17 đều chứa điểm nguyên. Kết quả này phù hợp với Định lý
1.2.7.
23
Bổ đề 1.4.2. Nếu a và b là các số nguyên dương nguyên tố cùng nhau và
n ∈ [1, ab − 1] không phải là bội số của a và b, khi đó
p{a,b}(n) + p{a,b}(ab − n) = 1.
Nói cách khác, với giá trị n nằm trong khoảng từ 1 đến ab − 1 và không chia hết cho a hoặc b, thì một trong hai số nguyên n và ab − n có thể biểu diễn theo hai số a và b.
−
−
+ 1
p{a,b}(ab − n) =
ab − n ab
(cid:27) (cid:27)
= 2 −
−
−
n ab
(cid:26)a−1(ab − n) b (cid:27) (cid:27)
= −
+
+
n ab
(cid:26)−a−1n b Chứng minh. Dựa vào Định lý 1.3.3 ta có (cid:26)b−1(ab − n) a (cid:26)−b−1n a (cid:27) (cid:27) (vì {−x} = 1 − {x}) (cid:26)a−1n b
(cid:26)b−1n a = 1 − p{a,b}(n).
p{a,b}(n) + p{a,b}(ab − n) = 1
Chứng minh của Định lý 1.2.7. Ta phải chỉ ra rằng p{a,b}(ab − a − b) = 0 và p{a,b}(n) > 0 với mọi n > ab − a − b. Với khẳng định đầu tiên ta có vì a, b nguyên tố cùng nhau nên p{a,b}(a + b) = 1. Đặt a + b = n, ta có n thỏa mãn điều kiện của Bổ đề 1.4.2. Do đó
p{a,b}(a + b) + p{a,b}(ab − (a + b)) = 1.
hay
p{a,b}(ab − (a + b)) = 0 hay p{a,b}(ab − a − b) = 0.
Vì p{a,b}(a + b) = 1 nên
(cid:9) ≤ 1 − 1 Để chứng minh khẳng định thứ hai, ta chú ý rằng với bất kỳ số nguyên m, (cid:8) m a
1 −
−
−
1 −
+ 1
p{a,b}(ab − a − b + n) ≥
a. Do đó với bất kỳ số nguyên dương n, (cid:19) ab − a − b + n ab
1 a
1 b
24
(cid:18) (cid:18) (cid:19)
=
> 0.
n ab
ab − 1 − (b − 1) − (a − 1) = ab − a − b + 1 = (a − 1)(b − 1)
Chứng minh của Định lý 1.2.10. Nhắc lại rằng Bổ đề 1.4.2 khẳng định rằng với n nằm giữa 1 và ab − 1 và không chia hết cho a hoặc b, có đúng một trong hai số n hoặc ab − n biểu diễn được. Có b − 1 số nguyên là bội của a nằm trong đoạn từ 1 tới ab−1, đó là các số a, 2a, 3a, . . . , (b−1)a. Có a − 1 số nguyên là bội của b nằm trong đoạn từ 1 tới ab − 1, đó là các số b, 2b, 3b, . . . , (a − 1)b. Suy ra có
số nguyên nằm giữa 1 và ab − 1 không chia hết cho a hoặc b. Cuối cùng, ta chú ý rằng p{a,b}(n) > 0 nếu n là bội của a hoặc b. Do đó, số số nguyên
(a − 1)(b − 1).
1 2
không biểu diễn được thông qua a, b là
Như vậy ta đã chứng minh được Định lý 1.2.7 về số Frobenius cho trường
hợp hai chiều và Định lý 1.2.10 của Sylvester. Chú ý rằng, ta còn chứng minh được nhiều hơn thế. Về bản chất, theo Bổ đề 1.4.2 p{a,b}(n) = 0 hoặc p{a,b}(n) = 1, tức là tất cả các số nguyên dương nhỏ hơn ab có nhiều nhất một cách biểu diễn. Do đó ta có hệ quả sau.
Hệ quả 1.4.3. Nếu a và b là hai số nguyên dương nguyên tố cùng nhau thì các số nguyên có thể biểu diễn được thông qua a và b nhỏ hơn a · b có
1.5 Số Frobenius cho hai đồng xu
biểu diễn duy nhất.
Hệ quả của định lý Schur khẳng định nội dung chúng ta đã biết, đó là số Frobenius g(a1, . . . , ak) được xác định rõ. Bây giờ chúng ta cùng hãy xem việc xác định số này trong trường hợp đơn giản nhất. Xin nhắc lại
25
hai kết quả kinh điển như dưới đây:
• Định lý hai đồng xu: Cho a và b là các số nguyên dương nguyên tố
• Định lý của Sylvester : Cho a và b là các số nguyên dương nguyên tố cùng nhau, khi đó, đúng một nửa số nguyên nằm trong khoảng 1 và (a − 1)(b − 1) có thể biểu diễn theo a và b.
cùng nhau, khi đó ta có: g(a, b) = ab − a − b.
Như vậy, chúng ta có thể xác định được ngay số Frobenius khi chỉ có hai
đồng xu. Ngoài ra, chúng ta cũng biết chính xác có bao nhiêu số nguyên
không thể biểu diễn được. Alfonsin [5] chỉ ra bốn cách chứng minh định
lý Hai đồng xu, Beck-Robins chỉ ra một cách chứng minh khác. Có thể có
nhiều cách khác chưa được khám phá để chứng minh hai định lý này.
Định nghĩa 1.5.1. Tập các số {a0, a1, . . . , a(m − 1) (mod m)} tạo thành một tập các số đồng dư hoàn chỉnh, còn gọi là một hệ phủ, của m nếu
(mod m)
ai ≡ i
chúng thỏa mãn
với i = 0, 1, . . . , m − 1.
Ví dụ, một tập các số đồng dư hoàn chỉnh cơ sở b đồng dư m nếu các phần dư r1 trong bi ≡ ri (mod m) với i = 1, . . . , m − 1 là tất cả các giá trị 1, 2, . . . , m − 1.
Để tạo thành một tập các số đồng dư hoàn chỉnh của m, ta cần một
tập m số nguyên và không có hai số nào cùng đồng dư m.
Bổ đề 1.5.2. Cho hai số nguyên dương a, b với gcd(a, b) = 1, khi đó 0b, 1b, 2b, 3b, . . . , (a − 1)b tạo nên một tập các số đồng dư hoàn chỉnh của a.
ib ≡ jb
(mod a) ⇒ a | ib − jb
⇒ a | b(i − j)
⇒ a | (i − j) do gcd(a, b) = 1
⇒ i ≡ j
(mod a).
26
Chứng minh. Cho i (cid:54)= j và i ∈ {0, 1, 2, . . . , a − 1}, lưu ý rằng
Trường hợp này không thể xảy ra vì i (cid:54)= j và i ∈ {0, 1, 2, . . . , a − 1}. Như vậy, 0b, 1b, 2b, 3b, . . . , (a − 1)b tạo nên một tập hợp số đồng dư hoàn chỉnh của a bởi vì tập hợp số này được tạo bởi a số nguyên khác nhau đồng dư a.
Bây giờ chúng ta chứng minh định lý hai đồng xu nổi tiếng của Calavaras
County.
Định lý 1.5.3 (Định lý hai đồng xu). Cho hai số nguyên dương nguyên tố cùng nhau a, b với gcd(a, b) = 1, khi đó ta có g(a, b) = ab − b − a.
Chứng minh. Việc chứng minh được sẽ dễ dàng hơn bằng cách giả thiết (không mất tính tổng quát) rằng a < b. Để chứng minh định lý này, trước hết chúng ta chỉ ra rằng tất cả giá trị lớn hơn (a − 1)b đều có thể biểu diễn thông qua a và b, sau đó trở lại dãy số tìm số nguyên đầu tiên không thể biểu diễn theo a và b chính là g(a, b).
Khẳng định: Cho số nguyên n bất kỳ sao cho n > (a − 1)b, khi đó n có thể biểu diễn theo a và b.
Chứng minh khẳng định. Cho n > (a − 1)b, Bổ đề 1.5.2 chỉ ra rằng đúng một trong các số 0b, 1b, 2b, 3b, . . . , (a − 1)b là đồng dư với n (mod a); đặt bằng tb ≡ n (mod a) với t ∈ {0, 1, 2, . . . , a − 1}. Lưu ý rằng tb < (a − 1)b < n vì t ∈ {0, 1, 2, . . . , a − 1}. Tiếp theo, lưu ý rằng việc cộng bất kỳ bội số của a vào một số nguyên đồng dư với n modulo a, sẽ cho ra một số nguyên đồng dư với n modulo a. Do tb < n và tb = n (mod a), khi đó n bằng tb cộng với một số bội của a. Vì vậy, cộng các bội số cần thiết của a vào tb để có thể biểu diễn n theo a và b, khi đó ta có tb + ua = n. Theo
đó, khẳng định trên được chứng minh.
Chúng ta đã chứng minh được rằng với mỗi số nguyên lớn hơn (a−1)b = ab − b có thể biểu diễn theo a và b, bây giờ chúng ta hãy quay trở lại với các giá trị nhỏ hơn ab − b và xem giá trị nào có biểu diễn, giá trị nào không
27
thể biểu diễn.
Mỗi giá trị trong dãy số ab−b, ab−b−1, ab−b−2, . . . , ab−b−(a−1) là các modulo a khác nhau vì các số nguyên liên tiếp a luôn có modulo a khác nhau. Như vậy, theo Bổ đề 1.5.2 với từng giá trị v ∈ {0, 1, 2, . . . , a − 1}, tồn tại w ∈ {0, 1, 2, . . . , a − 1} sao cho ab − bv = wb (mod a). Bây giờ, chú ý rằng a < b thì ab − 2b < ab − b − (a − 1), khi đó mỗi số trong dãy 0b, 1b, 2b, 3b, . . . , (a − 2)b = ab − 2b có giá trị bé hơn mỗi số trong dãy (a − 1)b = ab − b, ab − b − 1, ab − b − 2, . . . , ab − b − (a − 1). Như vậy, do wb = ab − b − v (mod a) và wb < ab − b − v, khi đó, ab − b − v bằng wb cộng với một số bội của a. Vì vậy, hãy cộng thêm các bội số cần thiết của a vào wb để có thể biểu diễn a trong ab − b − v theo a và b, khi đó, ta có wb + xa = ab − b − v.
Ta đã chứng minh được với mỗi số nguyên lớn hơn hoặc bằng ab − b − (a − 1) có thể biểu diễn theo a và b. Bây giờ chúng ta đạt được số nguyên đầu tiên không thể biểu diễn theo a và b, cụ thể theo ab − b − a. Để giải thích được điều này, giả sử rằng ab − b − a có thể biểu diễn theo a và b. Do đó tồn tại p, q ∈ N ,ab − b − a = pa + qb. Để biểu diễn được như vây, yêu cầu ab − b − a thuộc một ba trường hợp sau
1. là một bội số của a, hoặc
2. là một bội số của b, hoặc
3. là một bội số của b cộng với một bội số của a.
Hai trường hợp đầu sẽ không bao giờ xảy ra do ab−b−a = b(a−1)−a chỉ ra ab−b−a không phải là một bội số của b, trong khi ab−b−a = a(b−1)−b cho thấy ab − b − a không phải là một bội số của a. Vì vậy, giả định là ab − b − a = pa + qb là một bội số của b cộng với một bội số của a. Bây
ab − b − a = pa + qb với p, q là các số dương
⇒ qb ≡ ab − b − a (mod a) và qb < ab − b − a.
giờ chúng ta sẽ thấy rằng điều này không thể xảy ra do
28
Tuy nhiên, 0b, 1b, 2b, 3b, ..., (a − 2)b chỉ là các bội số của b, có giá trị nhỏ hơn ab − b − a, và không có số hạng nào trong dãy này là đồng dư modulo
a với ab − b − a = (a − 1)b − a = (a − 1)b (mod a), vì vậy không có giá trị qb tồn tại như trên.
1.6 Định lý của Sylvester
Sylvester yêu cầu chúng ta xem xét bổ đề dưới đây.
Bổ đề 1.6.1. Cho gcd(a, b) = 1 và (cid:98)x(cid:99) là hàm số nguyên lớn nhất, khi
a−1 (cid:88)
=
(a − 1)(b − 1).
đó: (cid:23)
1 2
i=1
(cid:22)ib a
Chứng minh. Gọi một lưới điểm trong R2 “có giá trị dương” nếu cả hai tọa độ có giá trị dương. Ta tính số điểm lưới có giá trị dương nằm dưới đường
x trong khoảng x = 1 và x = a − 1:
b a
thẳng y =
• Khi x = 1 thì y =
b a
(cid:23) , do đó có điểm lưới có giá trị dương nằm (cid:22) b a
phía dưới đường thẳng x = 1.
• Khi x = 2 thì y = 2
2
b a
b a
(cid:22) (cid:23) , do đó có điểm lưới có giá trị dương nằm
• . . . . . . . . . . . .
phía dưới đường thẳng x = 2.
• Khi x = a − 1 thì y = (a − 1)
b a
(cid:23) , do đó có điểm lưới có (cid:22)(a − 1)b a
giá trị dương nằm phía dưới đường thẳng x = a − 1.
x trong khoảng x = 1 và x = a − 1 là
Như vậy, số lượng các điểm lưới có giá trị dương nằm phía dưới đường
b a
thẳng y =
a−1 (cid:88)
.
(cid:23)
i=1
(cid:22)ib a
Tiếp theo, chúng ta hãy đếm số điểm lưới dựa trên cơ sở hình học: cắt mặt
x từ điểm (0, 0) đến (a, b).
b a
29
phẳng hình chữ nhật xác đường thẳng y =
Hình chữ nhật này có chiều rộng bằng a và chiều dài bằng b và lưu ý rằng
x trong
b a
các điểm lưới có giá trị dương nằm phía dưới đường thẳng y =
x cắt hình chữ nhật này từ góc này
chia cắt; ngoài ra, đường thẳng y = khoảng x = 1 và x = a − 1 đều nằm trong phạm vi hình chữ nhật đã được b a đến góc kia thành hai phần bằng nhau.
Bây giờ chúng ta hãy cắt đều các cạnh của hình chữ nhật a × b để có được một hình chữ nhật mới có chiều rộng a − 2 và chiều dài b − 2
đơn vị, hình chữ nhật được cắt đối xứng sao cho đường thẳng vẫn cắt
x. Lưu ý rằng
b a
i=1 nằm bên dưới đường thẳng đều nằm trong phạm vi hình chữ nhật này
(cid:23) đều hình chữ nhật này thành hai. Bây giờ chúng ta có một hình chữ nhật (a − 2) × (b − 2) chứa điểm lưới (a − 1)(b − 1) được cắt đều làm đôi bởi a−1 (cid:88) điểm lưới mang giá trị dương đường thẳng y = (cid:22)ib a
đồng thời là các điểm nút duy nhất còn lại nằm bên dưới đường thẳng. Cũng lưu ý rằng với gcd(a, b) = 1 thì không một điểm nút nào trong hình chữ nhật này nằm trên đường thẳng do x cần phải là một bội số của a
x là một số nguyên, tuy nhiên, giá trị x lớn nhất trong hình chữ
b a
để y =
nhật này chỉ bằng a − 1.
Do hình chữ nhật chứa (a − 1)(b − 1) điểm lưới và đường thẳng chia
đôi hình chữ nhật thành hai phần bằng nhau, không có điểm lưới nào nằm
trực tiếp trên đường thẳng, khi đó số lượng các điểm lưới nằm bên dưới
(a − 1)(b − 1).
1 2
(a − 1)(b − 1) số nguyên không có thể biểu diễn theo a và b.
đường thẳng trong hình chữ nhật này là
Định lý 1.6.2. Cho hai số nguyên dương a, b với gcd(a, b) = 1, khi đó có 1 2
Chứng minh. Định lý 1.5.3 chỉ ra rằng tất cả các số nguyên lớn hơn ab − b − a có thể biểu diễn theo a và b, vì vậy chúng ta cần kiểm tra xem số
nào có thể biểu diễn và số nào không thể biểu diễn xét trên phạm vi các số nguyên nằm trong khoảng [1, ab − b − a].
30
Khẳng định: Với giá trị k ∈ {1, 2, . . . , a − 1} , tồn tại tk sao cho với mọi số
trong dãy số nguyên không âm ab − kb − a, ab − kb − 2a, . . . , ab − kb − tka không thể biểu diễn theo a và b, trong đó tk có giá trị lớn nhất đảm bảo các giá trị nguyên không âm.
xa + yb = ab − kb − qa
⇒ yb = (a − k)b − (q + x)a.
Chứng minh. Giả sử ngược lại với k ∈ {1, 2, . . . , a − 1} , ∃x, y ∈ N, ∃q ∈ {1, 2, . . . , tk} sao cho xa + yb = ab − kb − qa. Khi này, ta có:
Điều này chỉ ra
0, 1, 2, ..., a − k − 1 và
1. yb < (a − k)b, do đó y là bằng đúng một trong các số của dãy
2. yb ≡ (a − k)b (mod a).
Tuy nhiên, không có số nào trong dãy 0, 1, 2, ..., a − k − 1 đồng dư modulo a với a − k, do đó không tồn tại giá trị y ∈ Z≥0, q ∈ {1, 2, . . . , t} để xa + yb = ab − kb − qa. Như vậy, khẳng định trên được chứng minh, tuy nhiên vẫn cần phải xác định giá trị tk.
Để xác định độ lớn của tk trong ab−kb−a, ab−kb−2a, . . . , ab−kb−tka, chúng ta đặt ra câu hỏi tk có thể lớn đến mức nào mà vẫn đảm bảo ab − kb − tka không âm? Lưu ý rằng ab − kb − tka = (a − k)b − tka, vì vậy chúng ta muốn trừ bội số lớn nhất của a đi từ (a − k)b, khi đó vẫn tồn tại một số nguyên không âm. Câu hỏi đặt ra là khi đó có bao nhiêu số a (cid:23) . Do đó, phù hợp với (a − k)b? Đó là một số nguyên không âm (cid:22)(a − k)b a
ab − kb − a, ab − kb − 2a, . . . , ab − kb − tka có
31
với mỗi giá trị k ∈ {1, 2, . . . , a − 1}, dãy số nguyên không thể biểu diễn (cid:23) phần tử. Theo (cid:22)(a − k)b a
+ . . . +
+
(cid:23) (cid:23) (cid:23)
+
+ . . . +
=
đó, số lượng các số nguyên không thể biểu diễn ít nhất sẽ là (cid:22)(a − 2)b a (cid:22)(a − (a − 1))b a (cid:22)(a − 1)b a (cid:23) (cid:23) (cid:23)
(cid:22)2b a (cid:22)(a − 1)b a
=
(cid:23) (cid:22) b a a−1 (cid:88)
=
(a − 1)(b − 1)theo Bổ đề 1.6.1.
i=1 1 2
(cid:22)ib a
Để khẳng định rằng không có thêm một số nguyên nào không thể biểu
diễn, hãy chú ý rằng chúng ta đã xem xét tất cả các số nguyên không biểu diễn đồng dư modulo a với (a − 1)b, (a − 2)b, . . . , (a − (a − 1))b = 1b, 2b, . . . , (a − 1)b bởi vì chúng ta đã xem xét tất cả các số nguyên không thể biểu diễn có giá trị bằng ab − kb − qa = (a − k)b − qa = (a − k)b (mod a) với mỗi k ∈ {1, 2, . . . , a − 1}, và cho mỗi q ∈ {1, 2, . . . , tk} (trong đó tk có giá trị lớn nhất). Điều này cho thấy rằng chúng ta đã xem xét tất cả các số nguyên không âm không thể biểu diễn có giá trị nhỏ hơn hoặc bằng ab − b − a vì mỗi số nguyên không âm không thể biểu diễn cần phải đồng dư modulo a với một trong các số của dãy 1b, 2b, . . . , (a − 1)b theo
Bổ đề 1.5.2.
Ví dụ 1.6.3. Cho hai số nguyên dương nguyên tố cùng nhau a = 4, b = 5.
(a − 1)(b − 1) = 6 số nguyên không thể biểu diễn theo 4
1 2
Khi đó có
32
và 5. Đó là các số 1, 2, 3, 6, 7, 11. Số Frobenius trong trường hợp này là g(4, 5) = ab − a − b = 11.
Chương 2
Một số vấn đề mở rộng
Trong chương này, chúng tôi trình bày thêm một số cách chứng minh
2.1 Ba đồng xu và nhiều đồng xu
khác của Định lý 1.2.7 và Định lý 1.2.10.
Bài toán sẽ trở nên phức tạp hơn nếu ta có nhiều hơn hai đồng tiền.
Các nhà nghiên cứu mới giải được bài toán trong một số trường hợp đặc biệt. Johnson chỉ ra rằng có thể khử gcd(a1, a2) = k để tính g(a1, a2, a3).
Định lý 2.1.1 ([5]). Nếu a1, a2, a3 là các số nguyên tố cùng nhau và gcd(a1, a2) = k thì
,
g(a1, a2, a3) = kg
, a3
+ (k − 1)a3.
(cid:17)
a2 k
(cid:16)a1 k
k , a2
k , a2
d , a3
d
(cid:1) hay kg(cid:0) a1
d
(cid:1) = (cid:1) = a1a2 − a1 − a2, cho nên g(a1, a2, a3) = d(a1a2 − a1 − a2) +
Rõ ràng từ Định lý 2.1.1, nếu a3 ≥ g(cid:0) a1 kg(cid:0) a1 k , a2 (d − 1)a3.
Một số tác giả khác nghiên cứu các trường hợp đặc biệt khi d = 3. Chẳng hạn, nếu a1, a2, a3 là các số nguyên tố cùng nhau và a1 là ước của (a2 + a3) thì
.
ai
g(a1, a2, a3) = −a1 + max i=2,3
(cid:26) (cid:23)(cid:27)
(cid:22) a1a5−i a2 + a3
33
Trong số các trường hợp riêng, Roberts thu được kết quả sau.
Định lý 2.1.2 ([5]). (a) Nếu gcd(a3 − a1, a2 − a1) = 1 thì
g(a1, a2, a3) ≤ a1
a3 − a2 − 2 +
a1 a3 − a1
+ (a2 − a1 − 1)(a3 − a1 − 1) + a1 + a2 + a3.
(cid:18) (cid:23)(cid:19) (cid:22)
(b) Nếu a, j > 2 là các số nguyên thì
+ (j − 3)a
(mod j), a ≥ j2 − 5j + 3,
=
(a + j) + (j − 3)a nếu a ≡ −1
(mod j), a ≥ j2 − 4j + 2,
g(a, a + 1, a + j) (cid:106) a+1 j (cid:106) a+1 j
(cid:107) nếu a ≡ −1 (cid:107)
(c) 0 < a < b và m là các số nguyên thỏa mãn gcd(a, b) = 1, m ≥ 2 thì
g(m, m + a, m + b) ≤ m
b − 2 +
+ (a − 1)(b − 1).
(cid:16) (cid:107)(cid:17)
(cid:106)m b
Goldbert nghiên cứu g(a1, a2, a3) trong một trường hợp rất đặc biệt
sau.
g(m, m + a, m + b)
Định lý 2.1.3 ([5]). Cho 1 < a < b là các số nguyên với gcd(a, b) = d và gcd(d, m) = 1 với md2 > b(b − a − 2d) và dm = ax0 + by0, 0 ≤ x0 < b/d, y0 ≥ 0. Khi đó,
d − 1(cid:1) − a
=
nếu dx0 ≥ b − a,
d − 1(cid:1) − a(x0 + 1) nếu ngược lại.
(cid:26)(cid:0) a d + x0 + y0 + d − 3(cid:1) n + b (cid:0) a d + y0 + d − 3(cid:1) n + b (cid:0) a (cid:0) b
Dãy a1, . . . , an được gọi là độc lập nếu không có phần tử nào biểu diễn được thông qua các phần tử còn lại. Selmer tìm được một công thức khác
tổng quát cho bộ ba số độc lập.
g(a1, a2, a3) ≤ max{(s − 1)a2 + (q − 1)a3, (r − 1)a2 + qa3} − a1,
Định lý 2.1.4 ([5]). Nếu a1, a2 và a3 là các số độc lập nguyên tố từng đôi thì
g(a1, a2, a3) = max{(s − 1)a2 + (q − 1)a3, (r − 1)a2 + qa3} − a1.
34
trong đó s được xác định bởi a3 ≡ sa2 (mod a1), 1 < s < a1 và r được xác định bởi a1 + qs + r, 0 < r < s. Ngoài ra, nếu a2 ≥ t(q + 1) và a3 = sa2 − ta1, t > 0 thì
Remirez Alfonsin tìm ra hai cận trên như sau của số Frobenius trong
Định lý 2.1.4
Định lý 2.1.5 ([5]). Cho 0 < w1 < a3 và 0 < w2 < a3 là các số nguyên duy nhất tương ứng thỏa mãn a1w1 ≡ a2 (mod a3) và a2w2 ≡ −a1 (mod a3), và cho r1 và r2 lần lượt là các số nguyên dương lớn nhất thỏa mãn −a3 + r1w1 < 0 và a3 − w2r2 > 0. Khi đó (a) g(a1, a2, a3) ≤ max{a1(a3−r1w1)+a2(r1+1), a1w1+a2r1}−a1−a2−a3. (b) g(a1, a2, a3) ≤ max{a1 +a2(a3 +(1−r2)w2), a1r2 +a2w2}−a1 −a2 −a3.
Các cận trong Định lý 2.1.5 có thể không gần nhau, tuy nhiên có các
trường hợp mà một trong hai cận (hoặc cả hai) sinh ra một giá trị rất gần với g(a1, a2, a3). Kết quả này được minh họa trong các ví dụ sau.
g(4, 7, 9) = 10 ≤
Ví dụ 2.1.6. Cho a1 = 4, a2 = 7 và a3 = 9. Ta có w1 = 4, w2 = 2, r1 = 2 và r2 = 4. Khi đó,
(cid:26)max{25, 30} − 20 = 10 max{18, 30} − 20 = 10 theo Định lý 2.1.5(a) theo Định lý 2.1.5(b).
g(5, 14, 31) = 37 ≤
Ví dụ 2.1.7. Cho a1 = 5, a2 = 14 và a3 = 31. Ta có w1 = 11, w2 = 2, r1 = 2 và r2 = 15. Khi đó,
(cid:26)max{87, 83} − 50 = 37 max{47, 103} − 50 = 87 theo Định lý 2.1.5(a) theo Định lý 2.1.5(b).
pA(n) = #{(m1, . . . md) ∈ Zd : mọi mj ≥ 0, m1a1 + . . . + mdad = n},
Ta quay trở lại với hàm phân hoạch có giới hạn
trong đó A = {a1, . . . , ad}. Với lập luận tương tự như trong Mục 1.3, ta dễ dàng tìm được hàm sinh của pA(n):
· · ·
.
pA(n)zn =
1 − za1
1 − za2
1 − zad
n≥0
(cid:19) (cid:19) (cid:18) 1 (cid:19) (cid:18) 1 (cid:18) 1 (cid:88)
Sử dụng các phương pháp như trong Mục 1.3 thu được hàm pA(n) là số hạng tự do của một hàm sinh. Cụ thể,
.
pA(n) = số hạng tự do của hàm
1 (1 − za1)(1 − za2) · · · (1 − zad)zn
35
(cid:18) (cid:19)
Bây giờ ta khai triển hàm ở vế phải của đẳng thức bên trên. Để cho đơn giản, ta giả sử a1, . . . , ad là các số đôi một nguyên tố cùng nhau, tức là không có hai số nào có ước chung. Khi đó khai triên phân thức đơn giản
f (z) =
B2
=
+
+
B1 z − 1
Bd (z − 1)d
1 (1 − za1) . . . (1 − zad)zn A1 z a1−1 (cid:88)
ad−1 (cid:88)
có dạng
+
+
.
+ . . . +
A2 z2 + . . . + a2−1 C1k (cid:88) ξk a1
An zn + C2k ξk a2
(z − 1)2 + . . . + Cdk ξk ad
k=1
k=1
k=1
(2.1)
Dựa theo cách tính ở Mục 1.3, ta dễ dàng kiểm tra được
.
C1k = −
a1(1 − ξka2
1 a1 )(1 − ξka3
a1 ) · · · (1 − ξkad
a1 )ξk(n−1) a1
(2.2)
a1−1 (cid:88)
ad−1 (cid:88)
+ · · · +
+ · · · +
pa(n) =
Giống như trước đây, ta không cần tính các hệ số A1, . . . , An bởi vì chúng không đóng góp vào số hạng tự do của f (z). Để tìm các hệ số B1, . . . , Bd, ta có thể sử dụng các phần mềm tính toán như Maple hoặc Mathematica.
Bd (z − 1)d +
Cdk z − ξk ad
C1k z − ξk a1
k=1
a2−1 (cid:88)
ad−1 (cid:88)
k=1 a1−1 (cid:88)
−
− · · · −
.
= −B1 + B2 − · + (−1)dBd −
C1k ξk a1
C2k ξk a2
Cdk ξk ad
k=1
k=1
k=1
Một lần nữa, khi tính được các hệ số này, ta có thể tính được số hạng tự do của f bằng cách bỏ qua tất cả các thành phần số mũ âm và tính phần còn lại của hàm tại z = 0: (cid:18) B1 z − 1 (cid:19)(cid:12) (cid:12) (cid:12) (cid:12)z=0
a1−1 (cid:88)
.
1 a1
(1 − ξka2
a1 ) · · · (1 − ξkad
1 a1 )(1 − ξka3
a1 )ξkn a1
k=1
Thay công thức của C1k vào công thức tổng lấy trên tất cả các căn đơn vị thứ a1 ở trên, ta thu được
b−1 (cid:88)
Kết quả trên thúc đẩy định nghĩa tổng Fourier–Dedekind
.
sn(a1, a2, . . . , am; b) :=
1 b
(1 − ξka1
ξkn b )(1 − ξka2
) · · · (1 − ξkam
)
b
b
b
k=1
36
(2.3)
Với định nghĩa này, ta thu được kết quả sau.
pA(n) = −B1 + B2 − . . . + (−1)dBd + s−n(a2, a3, . . . , ad; a1)
+ s−n(a1, a3, a4, . . . , ad; a2) + . . . + s−n(a1, a2, . . . , ad−1; ad).
Định lý 2.1.8. Hàm phân hoạch có giới hạn với A = (a1, a2, . . . , ad), trong đó các số ak đôi một nguyên tố cùng nhau, được tính như sau
Ở đây, B1, B2, . . . , Bd là các hệ số phân thức đơn giản trong khai triển (2.1).
+
+
+
+
+
+
+
+
+
p{a,b,c}(n) =
(cid:17) (cid:17)
b ac
c ab
1 bc
n 2
3 b
3 c
a bc 1
(cid:16) 1 ab
+
+
(cid:16)3 a b−1 (cid:88)
1 12 1 b
(1 − ξkb
a ) ξkn a
1 ac 1 a ) (1 − ξkc
k=1
k=1 c−1 (cid:88)
,
+
1 c
(1 − ξka
c ) ξkn c
1 c ) (1 − ξkb
k=1
Ví dụ 2.1.9. Chúng ta tính các hàm phân hoạch có giới hạn đối với d = 3 và d = 4. Các công thức này rất hữu ích trong việc phân tích chi tiết hàm tuần hoàn vốn có trong hàm phân hoạch có giới hạn pA(n). Ví dụ, ta có thể biểu diễn đồ thị của p{a,b,c}(n) bằng hình "parabol lượn sóng" như hiển thị trong công thức của nó. n2 2abc a−1 1 (cid:88) a (cid:1) (cid:0)1 − ξka b (cid:0)1 − ξkc b (cid:1) ξkn b
+
+
+
+
(cid:17)
+
+
+
+
+
+
+
+
+
+
c abd
(cid:17)
+
+
+
+
+
+
+
+
+
+
+
+
n2 4 3 bc b ac
(cid:17)
1 abd 3 cd b cd
1 acd a bcd c ab
1 bcd b acd c ad
d acb d ac
d ab
c bd
d bc
p{a,b,c,d}(n) = (cid:16) 3 ab (cid:16) a bc
+
+
+
−
n3 6abcd 3 3 ad ac a a cd bd 1 d
1 c
1 b
(cid:16) 1 abc 3 bd b ad (cid:17)
+
n 12 1 24 1 8 1 a
(1 − ξkb
1 a ) (1 − ξkd a ) (1 − ξkc
a ) ξkn a
k=1 b−1 (cid:88)
+
1 b
(cid:16)1 a a−1 (cid:88)
1 (cid:1) (cid:0)1 − ξkd b
k=1
37
(cid:0)1 − ξkc b (cid:1) (cid:0)1 − ξka b (cid:1) ξkn b
c−1 (cid:88)
+
1 c
(1 − ξkd
1 c ) (1 − ξkb c ) (1 − ξka
c ) ξkn c
k=1 d−1 (cid:88)
+
.
1 d
1 (cid:1) (cid:0)1 − ξkb d
k=1
(cid:0)1 − ξka d (cid:1) (cid:0)1 − ξkc d (cid:1) ξkn d
Nhận xét 2.1.10. Như ta đã nhắc đến ở trên, bài toán Frobenius với d ≥ 3 khó hơn nhiều trường hợp d = 2. Tất nhiên, sau trường hợp d = 3,
bài toán Frobenius vẫn là bài toán mở mặc dù nhiều nhà toán học đã nỗ
lực nghiên cứu nó. Các tài liệu về bài toán Frobenius rất phong phú, và
vẫn còn nhiều chỗ để cải thiện. Người đọc quan tâm có thể tham khảo
chuyên khảo toàn diện [5]. Trong đó tham chiếu đến hầu như tất cả các
bài viết về bài toán Frobenius và đưa ra khoảng 40 bài toán mở và khẳng
k∈R zk, trong đó R là tập tất cả các số nguyên biểu diễn được thông qua một tập các số nguyên dương nguyên tố cùng nhau a1, a2, . . . , ad. Không khó để thấy rằng r(z) = p(z)/(1 − za1)(1 − za2) · · · (1 − zad) với p là một đa thức. Hàm sinh phân thức này chứa tất cả các thông tin về bài toán Frobenius. Ví dụ, số
định liên quan đến bài toán Frobenius. Để ví dụ, chúng tôi đề cập đến hai kết quả mang tính bước ngoặt vượt xa trường hợp d = 2. Kết quả đầu tiên liên quan đến hàm sinh r(z) := (cid:80)
− r(z). Do đó bài toán Frobenius rút
1 1 − z
Frobenius là tổng bậc của hàm
gọn thành tìm đa thức p trong tử số của r.
Một kết quả đáng chú ý với d = 3 được tìm ra bởi Marcel Morales và Graham Denham, đa thức thức p có 4 hoặc 6 số hạng. Ngoài ra, họ cũng đưa ra công thức nửa hiển của p. Định lý Morales–Denham kéo theo số Frobenius trong trường hợp d = 3 có được tính một cách nhanh chóng.
38
Dường như có sự ngăn cách giữa trường hợp d = 2 với trường hợp d = 3. Có vẻ như cũng có sự ngăn cách giữa trường hợp d = 3 với d = 4. Henrik Bresinsky đã chứng minh rằng với d ≥ 4, không có giới hạn tuyệt đối về số số hạng trong tử số p, điều này trái ngược hoàn toàn với với định lý Morales–Denham trong trường hợp d = 3.
2.2 Số Frobenius cho các tập đặc biệt
2.2.1 Số Frobenius cho cấp số cộng
Mặt khác, Alexander Barvinok và Kevin Woods đã chứng minh rằng với d cố định, hàm sinh phân thức r(z) có thể được viết dưới dạng tổng của các hàm phân thức, cụ thể ta có thể tính được r một cách hiệu quả nếu d cố định. Một hệ quả thu được là số Frobenius có thể được tính một cách hiệu quả khi d cố định, định lý này là của Ravi Kannan.
1, . . . , m + k − 1.
Brauer [3] tìm ra số Frobenius cho k số nguyên dương liên tiếp m, m +
Định lý 2.2.1 (Brauer, [3]). Cho a là một số nguyên dương. Khi đó,
g(a, a + 1, . . . , a + k − 1) =
+ 1
a − 1.
(cid:23) (cid:19)
(cid:18)(cid:22)a − 2 k − 1
Dãy a1, . . . , an được gọi là cấp số cộng nếu ai+1 = ai + d với mỗi i = 1, . . . , n − 1 với d là một số nguyên dương. Ramirez Alfonsin [5] tổng
quát hóa kết qura trên cho cấp số cộng tổng quát.
Định lý 2.2.2 (Ramirez Alfonsin, [5]). Cho các số nguyên dương a, d, s với gcd(a, d) = 1, khi đó
g(a, a + d, a + 2d, . . . , a + sd) =
+ 1
a + (d − 1)(a − 1) − 1.
s
(cid:23) (cid:19) (cid:18)(cid:22)a − 2
Chứng minh. Đặt yi = (cid:80)s j=i xj với i = 0, . . . , s. Rõ ràng một số nguyên L có biểu diễn (cid:80)s i=0(a + id)xi khi và chỉ khi L = ay0 + d(y1 + · + ys) với y0 ≥ · · · ≥ ys ≥ 0. Bây giờ, với y0 cho trước, các số nguyên biểu diễn được dưới dạng y1 + · · · + ys với y0 ≥ · · · ≥ ys chính là các số nguyên z thỏa mãn 0 ≤ z ≤ sy0. Do đó, L biểu diễn được thông qua a, a + d, . . . , a + sd khi và chỉ khi L = ay + dz với 0 ≤ z ≤ sy.
Chú ý rằng Định lý 2.2.2 chứa 2.2.1 khi s = k − 1 và d = 1. Trường
39
hợp tập A = {a1, a2} ở trên là một trường hợp riêng của công thức này.
2.2.2 Số Frobenius cho cấp số nhân
Ta cũng có công thức đóng của số Frobenius của một tập các số nguyên trong cấp số nhân {a, ar, ar2, . . . , ark}, trong đó a là một giá trị ban đầu và r là công bội. Vì gcd(a, ar, ar2, . . . , ark) phải bằng 1, nên ta có a = mk và r = n/m, trong đó m, n là hai số nguyên nguyên tố cùng nhau. Kết
quả chính trong phần này là định lý sau.
Định lý 2.2.3 ([4]). Cho các số nguyên dương m, n, k với gcd(m, n) = 1,
g(mk, mk−1n, mk−2n2, . . . , nk)
= nk−1(mn − m − n) +
.
m2(n − 1)(mk−1 − nk−1) m − n
khi đó
Ta ký hiệu A(m, n, k) là nửa nhóm sinh bởi {mk, mk−1n, mk−2n2, . . . , nk}.
Ta cũng ký hiệu g(mk, mk−1n, mk−2n2, . . . , nk) bởi G(m, n, k).
Bổ đề 2.2.4 ([4]). Cho m, n là số nguyên tố cùng nhau và k ≥ 1, G(m, n, k + 1) ≥ (n − 1)mk+1 + nG(m, n, k).
k+1 (cid:88)
(n − 1)mk+1 + nG(m, n, k) =
cimink+1−i, ci ∈ Z+.
i=0
Chứng minh. Ta phải chỉ ra (n − 1)mk+1 + nG(m, n, k) /∈ A(m, n, k + 1). Giả sử phản chứng rằng (n − 1)mk+1 + nG(m, n, k) ∈ A(m, n, k + 1). Khi đó
(n − 1)mk+1 + nG(m, n, k)
Lấy mod n cả hai vế ta thu được −mk+1 ≡ ck+1mk+1. Vì m, n nguyên tố cùng nhau, ta kết luận rằng ck+1 ≡ −1 (mod n). Hay ck+1 = bn − 1 với một số nguyên dương b. Khi đó ta có
=
cimink+1−i
+ ((b − 1)m + ck)mkn + (n − 1)mk+1
i=0
(cid:35) (cid:34)k−1 (cid:88)
G(m, n, k) =
cimink+1−i
+ ((b − 1)m + ck)mk.
i=0
40
nên (cid:35) (cid:34)k−1 (cid:88)
Nhưng điều này kéo theo G(m, n, k) ∈ A(m, n, k), mâu thuẫn. Ta kết luận rằng (n−1)mk+1+nG(m, n, k) /∈ A(m, n, k+1), và do đó G(m, n, k+1) ≥ (n − 1)mk+1 + nG(m, n, k).
G(m, n, k + 1) ≤ (n − 1)mk+1 + nG(m, n, k).
Bổ đề 2.2.5 ([4]). Cho m, n nguyên tố cùng nhau và k ≥ 1. khi đó
Chứng minh. Ta sẽ chứng minh rằng nếu y > (n − 1)mk+1 + nG(m, n, k), thì y ∈ A(m, n, k + 1). Cho y ≡ dmk+1 (mod n), d ∈ [0, n − 1]. Đặt z = y − dmk+1. Vì z ≡ 0 (mod n), ta có z = nw với w là một số nguyên không âm. Nhưng y > (n − 1)mk+1 + nG(m, n, k) kéo theo z > nG(m, n, k), nên w > G(m, n, k), và do đó w ∈ A(m, n, k). Nhưng điều này có nghĩa rằng y = nw + dmk+1 ∈ A(m, n, k + 1), và do vậy G(m, n, k + 1) ≤ (n − 1)mk+1 + nG(m, n, k).
G(m, n, t) = nt−1(mn − m − n) +
.
(m − 1)m2(mt−1 − nt−1) m − n
Chứng minh của Định lý 2.2.3. Ta chứng minh bằng cách quy nạp theo k. Với k = 1 điều này rút gọn thành kết quả của Sylvester, G(m, n, 1) = mn − m − n. Giả sử nó đúng với k = t và do đó
G(m, n, t + 1)
Theo hai bổ đề trên, ta có
= (n − 1)mt+1 + n
nt−1(mn − m − n) +
(cid:18) (cid:19)
= nt(mn − m − n) + (n − 1)
mt+1 +
(m − 1)m2(mt−1 − nt−1) m − n (cid:19) nm2(mt−1 − nt−1) m − n
,
= nt(mn − m − n) +
(n − 1)m2(mt − nt) m − 1
(cid:18)
chính là định lý với k = t + 1.
41
Ta còn có một công thức đơn giản hơn thể hiện tích đối xứng giữa các biến như sau. Cho các số nguyên a, b, k, với gcd(a, b) = 1, đặt Ak(a, b) =
{akak−1b, . . . , bk}. Khi đó
g(Ak(a, b)) = σk1(a, b) − σk(a, b) − (ak+1 + bk+1),
2.3 Một số ví dụ
trong đó σk(a, b) là tổng tất cả các số nguyên trong Ak(a, b).
Trong phần này, chúng tôi tham khảo nguồn internet và [1] để trình
bày lại hai ví dụ thực tế tương tự bài toán đổi tiền Frobenius.
Một trường hợp đặc biệt của bài toán đổi tiền đôi khi còn được gọi là
bài toán McNugget. Dạng McNugget của bài toán đổi tiền được giới thiệu
bởi Henri Picciotto trong quyển sách đại số của ông. Picciotto nghĩ về bài
toán trong những năm 1980 khi ông đang ăn tối cùng con trai tại một nhà
hàng McDonald và giải bài toán trên khăn ăn. Số McNugget là tổng số
cánh gà trong một số lượng bất kỳ các hộp cách gà McNugget trong cửa
hàng McDonald. Ở nước Anh, các hộp phụ thuộc vào kích thước sẽ có 6,
9 hoặc 20 cánh.
Theo định lý Schur, vì 6, 9 và 20 nguyên tố cùng nhau, bất kỳ số nguyên
đủ lớn đều có thể được biểu diễn thành tổ hợp tuyến tính của ba số này.
Do đó, tồn tại một số không phải số McNugget lớn nhất, và tất cả các số
nguyên lớn hơn số này là số McNugget. Cụ thể, tất cả các số hữu hạn,
1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43.
ngoại trừ
Do đó, số không phải số McNugget lớn nhất là 43. Kết quả rằng tất cả
các số nguyên lớn hơn 43 là số McNugget có thể được kiểm tra bằng cách
44 = 6 + 9 + 9 + 20
45 = 9 + 9 + 9 + 9 + 9
46 = 6 + 20 + 20
42
khảo sát các phân hoạch nguyên sau đây
47 = 9 + 9 + 9 + 20
48 = 6 + 6 + 9 + 9 + 9 + 9
49 = 9 + 20 + 20.
Bất kỳ số lớn hơn có thể thu được bằng cách cộng thêm một vài số 6 vào
một trong các phân hoạch trên.
Nói cách khác, vì lcm(9, 20) = 180 và 6 là ước của 180, bằng cách áp
dụng công thức số Frobenius cho trường hợp ba chiều trước đây, ta thu
g(6, 9, 20) = lcm(6, 9) + lcm(6, 20) − 6 − 9 − 20 = 18 + 60 − 35 = 43.
được
Ngoài ra, kiểm tra trực tiếp ta thấy rằng thật ra không thể mua được 43
• chỉ các hộp 6 và 9 cánh gà không thể tạo thành 43 cánh gà vì chúng
cánh gà, bởi vì:
• cộng thêm một hộp 20 cánh gà không thể tạo thành 43 cánh gà vì
chỉ tạo thành các bội của 3 (ngoại trừ chính số 3),
• nhiều hơn một hộp 20 cánh, cộng với các hộp 6 hoặc nhiều hơn hiển
phần dư là 23 không là bội của 3,
nhiên không dẫn tới 43 cánh.
Sau này cửa hàng McDonald giới thiệu thêm hộp 4 cánh gà, số lớn nhất
không phải số McNugget là 11. Ở các quốc gia khác mà hộp 9 cánh được
thay bằng hộp 11 cánh, thì không tồn tại số không phải số McNugget lớn
nhất vì không có số lẻ nào được tạo thành.
Trong trò chơi bóng bầu dục liên minh, có bốn loại điểm số: penalty
goal (3 điểm), drop goal (3 điểm), try (5 điểm) và converted try (7 điểm).
Bằng cách kết hợp các điểm này, bất kỳ tổng số điểm đều có thể ngoại trừ
1, 2, hoặc 4 điểm. Trong trò chơi bóng bầu dục bảy cầu thủ, mặc dù tất
cả bốn loại điểm số được cho phép, ít khi có điểm penalty goal, điểm drop
43
goal là ít xuất hiện nhất. Điều này có nghĩa rằng điểm số đội gần như luôn
luôn bao gồm bội số của try (5 điểm) và converted try (7 điểm). Các điểm
sau (ngoài 1, 2, và 4) không thể được thực hiện từ bội số của 5 và 7 và vì
vậy trong trò chơi bóng bầu dục bảy người hầu như không bao giờ được
44
thấy các điểm số: 3, 6, 8, 9, 11, 13, 16, 18 và 23.
KẾT LUẬN
Luận văn đã trình bày một cách có hệ thống về Bài toán đổi tiền của
Frobenius trong trường hợp hai số và ba số. Trong luận văn, tôi đã đạt
được một số kết quả sau:
1. Tiếp cận bài toán đổi tiền của Frobenius trong trường hợp hai số theo
nhiều cách khác nhau.
2. Trình bày một số kiến thức liên quan đến bài toán đổi tiền Frobenius
như hàm sinh, hàm phần nguyên, số Frobenius, . . .
3. Tổng hợp một số kết quả về bài toán đổi tiền Frobenius trong trường
hợp ba chiều và tổng quát.
4. Trình bày hai ví dụ thực tế của bài toán đổi tiền trong trường hợp
ba số và bốn số. Đó bài bài toán McNugget và bài toán điểm số trò
45
chơi bóng bầu dục.
Tài liệu tham khảo
Tiếng Việt
[1] Đỗ Thị Thu Hiền (2013), Về bài toán Diophantine tuyến tính của
Tiếng Anh
Frobenius, Luận văn thạc sỹ, Đại học Khoa học, Đại học Thái Nguyên.
[2] M. Beck and S. Robins (2007), Computing the continuous discretely:
integer point enumeration in polyhedra, Springer.
[3] A. Brauer (1942), “On a problem of partitions”, Am. J. Math., 64, pp.
299–312.
[4] D. C. Ong and V. Ponomarenko (2008), “The Frobenius Number of
Geometric Sequences”, INTEGERS: the Electronic Journal of Combi-
natorial Number Theory, 8, A33.
[5] J. L. Remirez Alfonsin (2006), The Diophantine Frobenius Problem,
Oxford University Press.
