✨Bài toán đàn gia súc Archimedes

thumb|Lời giải nhỏ nhất cho bài toán đàn gia súc Archimedes với mỗi biểu tượng chỉ cho con gia súc Bài toán đàn gia súc Archimedes (tiếng Anh: Archimedes' cattle problem) là một bài toán giải phương trình Diophantine. Bài toán yêu cầu tính số bò trong đàn gia súc của Thần Mặt Trời. Bài toán được Gothold Ephraim Lessing phát hiện ra trong một văn bản Hy Lạp cổ, dưới dạng một bài thơ 44 dòng. Văn bản đó được tìm thấy ở trong thư viện Herzog August ở Wolfenbüttel, Đức năm 1773.

Việc giải bài toán dẫn đến giải một phương trình Pell có vô số nghiệm. Chính vì thế, người ta chỉ quan tâm đến nghiệm nguyên dương nhỏ nhất (các nghiệm còn lại đều biểu diễn bằng công thức tổng quát qua nghiệm nhỏ nhất này). Nhưng ngay cả nghiệm nhỏ nhất này cũng quá lớn (tới 206545 chữ số). Vì lý do đó mà trong nhiều năm, bài toán không có lời giải cuối cùng. Đến năm 1880, A. Amthor đã tìm ra lời giải tổng quát, với đáp số chính xác đến lũy thừa. Kết quả chính xác không thể tính ra chỉ bằng bút chì và giấy, vì số lượng chữ số quá lớn. Tuy vậy, ngày nay, các phần mềm máy tính cho phép viết kết quả chính xác này ra.

Lịch sử

Vào năm 1769, Gotthold Ephraim Lessing được bổ nhiệm làm thủ thư tại thư viện Herzog August ở Wolfenbüttel, nơi lưu trữ nhiều văn bản tiếng Hy Lạp và Latin. Vài năm sau, Lessing cho xuất bản một số bản dịch kèm theo lời bình. Trong số đó có một bài thơ Hy Lạp dài 44 dòng, thách đố người đọc tìm ra số gia súc trong đàn gia súc của Thần Mặt Trời. Phần đầu bài thơ nói rằng, Ác-si-mét đã gửi nó cho Eratosthenes để các nhà toán học ở Alexandria nghiên cứu. Vấn đề liệu Ác-si-mét có phải là tác giả của bài thơ hay không còn đang được tranh luận, mặc dù người ta không tìm thấy chút manh mối nào của bài thơ này trong bài viết của các nhà toán học Hy Lạp khác.

Lời giải tổng quát được A. Amthor tìm ra đầu tiên, vào năm 1880. Kết quả được ước tính có 206 545 chữ số với 3 chữ số đầu tiên là 776.

Những tính toán của Amthor được tiếp tục bởi nhóm Câu lạc bộ Toán học Hillsboro (Hillsboro, Illinois, Hoa Kỳ) từ năm 1889 đến 1893. Ba thành viên của câu lạc bộ gồm Edmund Fish, Geo. H. Richards, và A. H. Bell đã tính 31 chữ số đầu tiên và 12 chữ số cuối cùng của đáp số nhỏ nhất của bài toán:

7760271406486818269530232833209... 719455081800

Trong kết quả này, hai chữ số in đậm bị tính sai, kết quả đúng phải là 13. Kết quả được công bố trên bài báo

A. H. Bell "The "Cattle Problem." ByArchimedies[sic] 251 TCN" American Mathematical Monthly Volume 2 (1895) pages 140-141

Thời đại máy tính cho phép giải quyết bài toán trọn vẹn. Nghĩa là kết quả được tính chính xác đến từng chữ số. Điều đó được thực hiện lần đầu tiên ở đại học Waterloo, vào năm 1965 bởi H. C. Williams, R. A. German, và C. R. Zarnke. Họ dùng 2 máy tínhIBM 7040 và IBM 1620. H. C. Williams, R. A. German, và C. R. Zarnke "Solution of the cattle problem of Archimedes" Mathematics of Computation Volume XIX (1965) pages 671-674

Năm 1981, Harry L. Nelson của Phòng thí nghiệm quốc gia Lawrence Livermore (Lawrence Livermore National Laboratory) đã in kết quả gồm 206545 chữ số, tính bởi máy tính CRAY 1 (số lượng gia súc nhỏ nhất có thể của Thần Mặt Trời). Harry L. Nelson "A solution to Archimedes' cattle problem" Journal of Recreational Mathematics Volume 13 (1980-81) pages 162-176

Bài toán

Sau đây là bản dịch tiếng Việt từ bản dịch tiếng Anh (qua tiếng Đức) của bài toán, được Nesselmann xuất bản vào năm 1842 và Krumbiegel vào năm 1880:, dựa trên phương trình Pell.

Nhân các nghiệm tổng quát vừa tìm được với:

: $n\; =\; \backslash frac\{(w^\{4658j\}\; -\; w^\{-4658j\})^2\}\{(4657)(79072)\}\; \backslash ,$

trong đó

: $w\; =\; 300426607914281713365\; \backslash sqrt\{609\}\; +\; 84129507677858393258\; \backslash sqrt\{7766\}$

và j là số nguyên dương bất kì. w có thể biểu diễn tương đương

: $w^2\; =\; u+v\backslash sqrt\{(609)(7766)\}\; \backslash ,$

với {u, v} là nghiệm cơ bản của phương trình Pell

: $u^2-(609)(7766)v^2\; =\; 1\; \backslash ,$

Muốn số lượng gia súc là nhỏ nhất thì chọn j nhỏ nhất, j = 1.

Đáp số: số lượng gia súc của Thần Mặt Trời xấp xỉ $7.76\; \backslash times\; 10^\{206544\}$ (kết quả này được A. Amthor công bố đầu tiên).

Ngày nay, các máy tính có thể dễ dàng tính ra kết quả chính xác đến từng chữ số của bài toán này. Điều đó được thực hiện lần đầu tiên ở đại học Waterloo, vào năm 1965 bởi H. C. Williams, R. A. German, và C. R. Zarnke. Họ dùng kết hợp máy tính IBM 7040 và IBM 1620.

Phương trình Pell

Với dữ kiện thứ hai của bài toán.

Tổng số bò đực đen và bò đực trắng là số chính phương:

:$B+W\; =\; 7,460,514k\; +\; 10,366,482k\; =\; (2^2)(3)(11)(29)(4657)k\; \backslash ,$

suy ra k = (3)(11)(29)(4657)q², với q là số nguyên.

Tổng số bò đực đốm và bò đực vàng là số tam giác:

:$D+Y\; =\; \backslash frac\{t^2+t\}\{2\}$

suy ra:

:$t\; =\; \backslash frac\{-1\backslash pm\backslash sqrt\{1+8(D+Y)\{2\}\; =\; \backslash frac\{-1\backslash pm\backslash sqrt\{1+92059576k\{2\}$

Suy ra 1+92059576k là số chính phương, dẫn đến phương trình Pell sau (thay k = (3)(11)(29)(4657)q²)

:$p^2-(4)(609)(7766)(4657^2)q^2\; =\; 1\; \backslash ,$.