Bài toán “Hàn Tín điểm binh” là thế nào?

Bài toán “Hàn Tín điểm binh” là một trò chơi dự đoán số rất thú vị. Giả sử bạn cầm trong tay một số lá cờ, khoảng dưới hoặc trên 100 lá. Trước hết, bạn chập thành từng nhóm 3 lá và ghi lại số dư khi phần còn lại không đủ 3 lá. Sau đó, lại chập thành từng nhóm 5 lá và ghi số dư của nhóm không đủ 5. Cuối cùng, chập thành từng nhóm 7 lá và ghi số dư của nhóm không đủ 7. Dựa vào số lá cờ dư ở các nhóm, người ta có thể đoán ra tổng số lá cờ đang có.

Ví dụ: chập 3 dư 1 lá, chập 5 dư 2 lá, chập 7 dư 1 lá, vậy có bao nhiêu lá cờ?

Phương pháp giải khá đơn giản và ngay từ thời cổ đại Trung Quốc đã có lời giải. Vào thời nhà Tống, Chu Mật gọi nó là “Bài toán Quỷ cốc” hoặc “Toán Cách tường”; Dương Huy gọi là “bài toán chém ống”. Nhưng tên gọi “Hàn Tín điểm binh” là phổ biến nhất. Cách giải được trình bày trong sách toán cổ “Tôn tử toán kinh”. Về sau, Tần Cửu Thiều thời nhà Tống đã cải tiến và phổ biến rộng rãi với tên “Thuật toán Đại diễn”, tức giảng giải về cách tính toán. Đó chính là nội dung mà trong lịch sử toán học gọi là định lý “thặng dư Trung Quốc”, một bài toán rất nổi tiếng.

Nội dung của phương pháp giải bài toán có thể biểu diễn bằng biểu thức dưới đây:

trong đó a, b, c là các số dư tương ứng khi chập 3, chập 5 và chập 7 lá cờ. Nếu con số tính được lớn hơn 105 thì trừ cho 105 đến khi được một số nhỏ hơn 105 thì dừng lại. Theo cách giải này, bài toán đoán số lá cờ ở trên có đáp án 1 x 70 + 2 x 21 + 2 x 15 - 105 = 37 lá.

Vậy tại sao trong bài toán “Hàn Tín điểm binh” lại cần bộ ba số 3, 5 và 7? Liệu có thể dùng những bộ ba số khác không? Để trả lời, ta cần nghiên cứu kỹ cách giải bài toán “Hàn Tín điểm binh”: “70a + 21b + 15c - 105”.

Ta cần xem xét mối quan hệ của bốn số 70, 21, 15 và 105 với các số 3, 5, 7.

1) 70 = 2 x 5 x 7; 70 = 3 x 23 + 1, nên 70 là bội số chung của 5 và 7, đồng thời khi chia cho 3 thì dư 1.

2) 21 là bội số chung của 3 và 7, 21 chia cho 5 thì dư 1.

3) 15 là bội số chung của 3 và 5, 15 chia cho 7 thì dư 1.

4) 105 là bội số chung nhỏ nhất của ba số 3, 5, 7.

Dựa vào mối quan hệ trên, “70a + 21b + 15c - 105” chính là số phải tìm. Bởi vì:

70a + 21b + 15c - 105 =

= (3 x 23 +1) x 1 + (3 x 7 x 2) + (3 x 5 x 2) - (3 x 5 x 7)

= 3 x 23 x 1 + 1 x 1 + 3 x 7 x 2 + 3 x 5 x 2 - 3 x 5 x 7

= 3 x (23 x 1 + 7 x 2 + 5 x 2 - 5 x 7) + 1

Vì vậy, 70a + 21b + 15c - 105 chia cho 3 có số dư là 1. Lý luận tương tự cho thấy đem số này chia cho 5 và cho 7 cũng sẽ có số dư tương ứng.

Vậy tại sao trong bài toán “Hàn Tín điểm binh” người ta dùng bộ ba số 3, 5, 7? Chúng ta biết rằng hai số bất kỳ trong ba số ấy đều nguyên tố cùng nhau, tức chỉ có ước chung là 1. Vì vậy, nếu tìm được một số có tính chất là bội số chung của hai số trong bộ ba, và khi chia cho số thứ ba lại dư 1, như các số 70, 21, 15, thì sẽ đáp ứng yêu cầu của bài toán “Hàn Tín điểm binh”.

Thế với các số không nguyên tố cùng nhau thì có tìm được các số tương tự 70, 21 và 15 không? Ví dụ chọn ba số 4, 6, 7, trong đó 4 và 6 không nguyên tố cùng nhau, có ước số chung lớn nhất là 2. Bội số chung của 6 và 7 đều là số chẵn; nếu đem chia cho 4 thì số dư cũng là số chẵn, không thể là 1. Vì vậy, ta không tìm được sự tương ứng với 70, 21, 15. Do đó, bài toán “Hàn Tín điểm binh” không sử dụng được với ba số không nguyên tố cùng nhau.

Ta có thể bỏ bộ ba 3, 5, 7 và dùng một bộ ba số nguyên tố cùng nhau khác. Ví dụ với 2, 3, 11, biểu thức giải là “33a + 22b + 12c - 66”. Trong đó, các số 33, 22, 12 và 66 thỏa mãn bốn mối quan hệ như đã nêu ở trên, và các bạn có thể dễ dàng tìm thấy số phải tìm là 37.