Bài toán Hàn Tín Điểm Binh
Giới thiệu
Nhân hôm nay rảnh rổi, mình xin luận chuyện số học một chút.
Hoài Âm Hầu Hàn Tín là danh tướng trong lịch sử nhà Hán. Thời Hán Sở tranh hùng, Hàn Tín được Hán vương Lưu Bang phong làm Đại Nguyên Soái, thống lĩnh toàn bộ binh mã vượt Tam Tần, công phá quân Sở. Nói Hán vương thu được giang sơn lập nên nhà Hán thì có tới nửa là công chinh chiến của Hàn Tín.
Nắm vạn binh mã trong tay, cái khó không phải chỉ là làm sao bày mưu đánh trận, công thành phá địch, mà trước hết phải biết quản lý nhân mã, đảm bảo hậu cần, tổ chức, biên chế đội ngũ rồi mới nói tới chuyện đánh giặc.
Thời đó chưa có bộ phận thống kê, xử lý số liệu như bây giờ, thế nên việc hỏi « chúng ta có bao nhiêu quân mã », tưởng dễ mà lại không biết đếm ra làm sao. Vậy nên Hàn Tính mới nghĩ ra một thuật toán đơn giản như sau :
– Quân lính các đội , các phiên khi đi vào cửa doanh thì đi hàng ba người. Sau khi đi hết lượt thì ghi lại số người bị lẻ (c1) ra
– Quân lính các đội, băt đi ra ngoài hết, theo từng đội 5 người. Sau khi đi hết lượt thì ghi lại số người bị lẻ(c2) ra
– Sau đó những người lính này bắt đi vào lại theo đội 7 người. Hết lượt thì ghi lại số dư lẻ (c3) ra
Sau đó, công thức tính tổng số quân là :
70*c1+21*c2+15*c3 +k*105
Trong đó k là một số nguyên, tùy theo ước lượng của cả đội mà chọn lấy
Ví dụ : Lần đầu đếm lẻ 1 người . Lần tiếp đếm được 3 người, lần cuối đếm được lẻ 5 người
Vậy tổng số quân trong doanh là
70*1+21*3+15*5 +k*105
Ước chừng cả doanh trại có gần 1000 người, vậy chọn k =7, có được tổng số quân là 943 người. Kiểm lại : 943 chia 3 dư 1, chia 5 dư 3 và chia 7 dư 5 (nghiệm đúng)
Có bài vè lại rằng:
Tam nhân đồng hành thất thập hi
Ngũ thụ mai hoa trấp nhất chi
Thất tử đoàn viên chính bán nguyện
Trừ bánh linh ngũ tiện đắc tri
Dịch ra là
Ba người cùng đi ít bảy chục.
Năm cỗi mai hoa hăm mốt cành.
Bảy gã xum vầy vừa giữa tháng.
Trừ trăm linh năm biết số thành.
Thực ra bài vè này giống bài vè trừ quỷ hơn là thuật toán, nhưng quả thực nó chẳng có ý nghĩa gì đặc biệt ngoài việc giúp người ta ghi nhớ mấy con số quan trọng: 3, 70, 5, 21, 7, 15 và 105.
Không có giải thích gì nhiều hơn, chúng ta thấy những số này cũng quỷ mị giống như bài vè đề trên. Vậy tại sao thuật toán trên lại sinh ra được những số như vậy?
Đề bài: Lý thuyết đồng dư Trung Hoa
Tạm thời quên đi câu truyện về Hoài Âm Hầu Hàn Tín, ta hãy tiếp cận vấn đề với số học hiện đại.
Trong cuốn sách“Disquisitiones Arithmeticae” của nhà toán học Carl Fredrick Gauss, ông có đề câp tới lý thuyết gọi là “lý thuyết đồng dư Trung Hoa”. Trong đó, đề bài được đưa ra là :
Bài toán tổng quát (I):
Với n1, n2, n3…nr là các số nguyên tố cùng nhau, nếu số x thỏa mãn hệ phương trình đồng dư với các số dư lần lượt là c1, c2….cr
Lời giải tổng quát: Lý thuyết đồng dư Trung Hoa
Gauss , với tài năng thiên bẩm của mình, đưa ra lời giải tổng quát như sau (Lời giải và cách chứng minh thì đều có rồi, có điều chứng minh thì dài quá, mà mình không có hứng thú lắm nên tạm thời bỏ qua vậy)
Như lời giải Gauss đề ra, thì x sẽ là hệ nghiệm của phương trình
x = k*N + (c1N1d1+c2N2d2+…+crNrdr) với k là số nguyên bất kỳ
Áp dụng lại vào bài toán “Hàn Tín Điểm Binh”
Quay lại bài toán Hàn Tín điểm binh, ta có thể viết lại đề bài như sau:
Biết rằng tổng số quân sĩ trong doanh là một số nguyên (tất nhiên là nguyên dương, không ai lại đếm ra âm chín trăm lẻ bảy binh sĩ cả, có ai đó chỉ huy một đoàn Âm Binh Âm Tướng mà thôi ), nằm trong khoảng từ 1 tới 1000 (hay bao nhiêu đó, tùy vào ước lượng sơ ban đầu). Số này chia 3 dư 1, chia 5 dư 3 và chia 7 dư 5. Gọi số này là x, ta có hệ phương trình
Vậy , theo định lý đồng dư ở trên, x chắc chắn thuộc hệ nghiệm phương trình
Vậy giải hệ phương trình trên như thế nào ? Lấy k là bao nhiêu ? Thô sơ nhất mà nói, ta thấy x chia 105 dư k, vậy thì….. Ta thử k từ 1 tới 104, kiểu gì cũng tìm ra đáp số !? Cách làm này trong ngành công nghệ thông tin gọi là brute-force. Thế nhưng may sao, Gauss đưa ra một thuật toán giải quyết thông mình hơn nhiều.
Áp dụng lời giải này cho bài toán Hàn Tín điểm binh, ta giải như sau:
Có:
n1=3, n2=5 và n3=7
Vậy N= n1*n2*n3=3*5*7=105
Ở ví dụ ta đưa bên trên, số quân chia 3 dư 1, chia 5 dư 3 và chia 7 dư 5, nên
c1=1, c2=3 và c3=5
Áp dụng lời giải của Gauss:
Hay viết lại thành:
x chia cho 105 dư (1 x 70) + (3 x 21) + (5 x 15 )
Vậy x = 105 *k + (1 x 70) + (3 x 21) + (5 x 15 ) với k là một số nguyên (dương)
Cuối cùng ta tìm lại được công thức trong bài vè của Hàn tướng quân thời xưa !
Hệ nghiệm của phương trình này là:
208, 313, 418, 523, 628, 733, 838, 943…
Tất nhiên -208, -313,… cũng là nghiệm của phương trình, nhưng Hàn tướng quân mà nghe báo cáo quân ta có âm 208 người thì chắc cũng… từ ấn về quê mất thôi
Các con số 3, 5, 7, 105, 70, 21 và 15 dần dần được giải mã nguồn gốc .
Để khơi dậy một chút thú vị, cũng xin chia sẻ với mọi người rằng, thực ra Bài toán đồng dư do Gauss giới thiệu và đưa ra lời giải ở trên đã được chép tới trong sách “Tôn Tử Toán Kinh” . Sách này, như tên của nó, là do Tôn Vũ, một danh tướng kiệt xuất nước Ngô chép lại. Ngoài “Tôn Tử Toán Kinh”, ông cũng là tác giả của bộ binh thư nổi tiếng “Binh Pháp Tôn Tử”
Cũng quả thật kỳ lạ một điều, từ hàng ngàn năm trước, người ta đã nghĩ ra được những thuật toán phức tạp như thế này. Văn minh nhân loại quả thức đang bội phục.
Đáng tiếc là mình không đọc được tiếng Hán cổ để tham khảo Tôn Tử Toán Kinh xem người xưa giải toán như thế nào?
Nhận xét
Đăng nhận xét