Vì sao câu đố chia sữa lại giúp bảo vệ tài khoản ngân hàng? Diophantus và phương trình nghiệm nguyên

Từ câu đố chia sữa 8, 5, 3 lít tới Diophantus, phương trình nghiệm nguyên, đóng gói, xếp lịch và phép tính tạo khóa RSA trong bảo mật trực tuyến.

18 phút đọcTrung cấpEyeBlogs

Đọc bản tiếng Anh →

Minh họa do ALumiEye vẽ: ba bình 8, 5, 3 lít nối tới ổ khóa biểu tượng và đẳng thức 7 × 23 − 40 × 4 = 1. Tiêu đề: Vì sao câu đố chia sữa lại giúp bảo vệ tài khoản ngân hàng? Diophantus và phương trình nghiệm nguyên. Hình mô tả mối liên hệ toán học, không phải giao diện ngân hàng.
Mục lục

Có một câu đố chia sữa quen thuộc: bình 8 lít đầy sữa, bình 5 lít và bình 3 lít đều rỗng. Không bình nào có vạch chia. Không được đổ sữa đi, không thêm dụng cụ, mỗi lần rót phải chờ bình nguồn cạn hoặc bình đích đầy. Làm sao chia thành hai phần, mỗi phần 4 lít?

Bài toán chia sữa giải được trong 7 lượt rót, kết thúc ở hai phần 4 lít. Còn mối nối với tài khoản ngân hàng nằm ở toán học phía sau: phép ghép các bội nguyên cũng xuất hiện khi tính khóa RSA, một công cụ có thể tham gia bảo mật kết nối trực tuyến. Câu đố không phải cơ chế bảo vệ tài khoản, và không phải ngân hàng nào cũng dùng cùng một bộ thuật toán. Bài này sẽ chỉ ra chính xác phép tính chung ấy, không đồng nhất nó với mật khẩu, mã OTP hay toàn bộ hệ thống ngân hàng.

Mẹo chia sữa là giữ sẵn 2 lít trong bình 3 lít. Khi bình 5 lít đầy, bình nhỏ chỉ nhận thêm 1 lít, để lại đúng 4. Từ lời giải này, ta đi qua phương trình nghiệm nguyên gắn với tên Diophantus, đóng gói hàng, xếp lịch chu kỳ, rồi tới phép tính tìm một số mũ bí mật trong RSA. Diophantus không được xem là tác giả câu đố hay người phát minh mật mã hiện đại.

Bài toán chia sữa 8, 5, 3 lít giải thế nào?

Gọi ba bình là A, B và C, lần lượt chứa tối đa 8, 5 và 3 lít. Ta ghi lượng sữa theo đúng thứ tự ấy. Chẳng hạn, (3, 2, 3) nghĩa là A có 3 lít, B có 2 lít, C có 3 lít. Tổng luôn là 8.

Một lượt rót kết thúc khi ta có điều kiện dừng chắc chắn: nguồn hết sữa hoặc đích đầy. Không được tự dừng ở chỗ ước lượng là 4 lít. Nếu cho phép nhìn bằng mắt rồi dừng tùy ý, ta đã lén đem một chiếc thước đo vào bài toán.

Lượt Thao tác A: bình 8 L B: bình 5 L C: bình 3 L
0 Ban đầu 8 0 0
1 A rót đầy B 3 5 0
2 B rót đầy C 3 2 3
3 C rót hết về A 6 2 0
4 B rót hết sang C 6 0 2
5 A rót đầy B 1 5 2
6 B rót đầy C, chỉ thêm được 1 L 1 4 3
7 C rót hết về A 4 4 0

Đừng cố nhớ cả bảng. Hãy nhìn hai chỗ: lượt 2 để lại 2 lít trong bình vừa; lượt 4 chuyển phần ấy sang bình nhỏ. Ta dùng chỗ trống còn lại để đo, thay vì dùng vạch trên thành bình. Bình 3 lít đang có 2 lít chính là một dụng cụ nhận thêm đúng 1 lít.

Đó cũng là điều hay xảy ra khi nấu ăn. Một chiếc ca đã biết dung tích có thể đo bằng phần chứa được hoặc phần còn thiếu. Câu đố không có vạch, nhưng vẫn có hai mốc chính xác: đầy và cạn.

Tám trạng thái ba bình 8, 5, 3 lít, đọc từ trái sang phải rồi xuống hàng: (8,0,0), (3,5,0), (3,2,3), (6,2,0), (6,0,2), (1,5,2), (1,4,3), (4,4,0). Hai phần 4 lít cuối cùng được đánh dấu.
Hình 1. Một đường rót ngắn nhất, tính bằng đoạn Python gần cuối bài. Mỗi hình giữ nguyên thứ tự bình 8, 5, 3 lít; con số phía trên là lượng sữa hiện có, không phải vạch chia.

Diophantus liên quan gì đến ba bình sữa?

Diophantus làm toán tại Alexandria, thường được đặt vào khoảng thế kỷ III. Tiểu sử của ông ít chắc chắn hơn các công thức mang tên ông: niên đại chủ yếu được suy ra từ những tác phẩm nhắc đến ông và những người ông trích dẫn. Vì vậy, ghi một năm sinh cụ thể sẽ tạo ra độ chính xác mà tư liệu không có.[1]

Công trình nổi tiếng của ông là Arithmetica, một tập hợp bài toán số học được xử lý bằng đại số. Thay vì chỉ tính một biểu thức đã biết, ông tìm những số chưa biết sao cho nhiều điều kiện cùng đúng. Đó là bước quen thuộc khi ta chuyển lời văn thành câu “gọi số cần tìm là x”.[1]

Có một khác biệt cần giữ rõ. Diophantus chấp nhận nhiều nghiệm hữu tỉ dương, tức những số viết được thành phân số, như một nửa chiếc bánh. Còn tên “phương trình Diophantine” ngày nay thường chỉ phương trình đa thức mà ta tìm nghiệm nguyên. Tên gọi hiện đại rộng hơn một bài toán của riêng ông, và không phải mọi nghiệm ông tìm đều là số nguyên.[1]

Với người bán sữa, phân số lít không vô lý. Nhưng trong câu đố, các bình có dung tích nguyên lít, lượng sữa ban đầu nguyên lít, và ta chỉ rót đến đầy hoặc cạn. Những thao tác ấy khiến lượng sữa sau mỗi bước vẫn là số nguyên lít. Ràng buộc này đến từ dụng cụ và luật chơi, không phải vì chất lỏng không chia nhỏ được.

Đó là chiếc cầu tới Diophantus: không chỉ hỏi một phương trình có đáp án hay không, mà hỏi đáp án được phép thuộc loại nào. Bạn mua ba suất phở có thể trả tiền lẻ, nhưng không thể đặt 2,4 suất nếu quán chỉ bán nguyên tô. Cùng một phép tính, thêm điều kiện “nguyên” thì bài toán đổi khác.

Nếu muốn theo mạch lịch sử ấy đi tiếp, bài Fermat và ghi chú bên lề sách kể chuyện một người đọc Arithmetica nhiều thế kỷ sau. Ở đây, ta ở lại với điều nhỏ hơn: hai chiếc bình có thể tạo ra những lượng nào?

Vì sao đổi dung tích có thể khiến bài toán vô nghiệm?

Thử thay ba bình bằng 12, 8 và 4 lít, bình lớn đầy, hai bình kia rỗng. Muốn chia đôi, ta cần hai phần 6 lít. Lần này không có trình tự khéo léo nào cứu được.

Mọi dung tích đều chia hết cho 4. Ban đầu lượng sữa trong từng bình cũng chia hết cho 4. Khi rót, cả lượng sữa sẵn có lẫn chỗ trống của bình nhận đều là bội của 4. Lượng chuyển đi, lấy theo bên nào hết trước, vẫn là bội của 4. Sau một lượt, sau hai lượt, hay sau bao nhiêu lượt cũng vậy.

Đó là một bất biến: điều không đổi qua thao tác, giống việc đổi tiền bằng các tờ 20.000 và 50.000 đồng thì tổng tiền vẫn là bội của 10.000. Bình có thể đổi chỗ, lượng có thể đổi, nhưng không bình nào chứa đúng 6 lít vì 6 không chia hết cho 4.

Con số 4 ở đây là ước chung lớn nhất, viết tắt ƯCLN: đơn vị lớn nhất dùng để chia vừa mọi dung tích. Với các bình 8, 5, 3, ƯCLN là 1, nên rào cản này không ngăn được mục tiêu 4 lít. Với 12, 8, 4, ƯCLN là 4 và mục tiêu bị chặn ngay từ đầu.

Tổng quát hơn, nếu cả dung tích lẫn lượng ban đầu đều là bội của một số nguyên dương g, mọi lượng về sau cũng là bội của g. Đây là điều ta vừa chứng minh bằng phép rót, không phải kết luận từ việc thử vài ví dụ.

ƯCLN bằng 1 đã bảo đảm rót được chưa?

Chưa, nếu giữ đúng bài toán ba bình kín này. Xét ba bình 10, 6, 3 lít, bắt đầu ở (10, 0, 0) và muốn tới (5, 5, 0). ƯCLN của cả ba dung tích là 1. Nhưng hai bình nhỏ chỉ chứa tổng cộng 9 lít, nên bình lớn luôn còn ít nhất 1 lít: nó không bao giờ cạn.

Trong khi đó, hai bình nhỏ đều có dung tích là bội của 3. Rót từ bình lớn thì bình nhỏ nhận đến đầy; rót về bình lớn thì bình nhỏ cạn. Rót qua lại hai bình nhỏ cũng giữ lượng là bội của 3. Bởi vậy bình 6 lít không thể có 5 lít, dù phép kiểm tra ƯCLN của cả ba bình không phản đối.

Đoạn tìm kiếm cùng luật rót chỉ thấy sáu trạng thái: (10,0,0), (4,6,0), (7,0,3), (7,3,0), (1,6,3) và (4,3,3). Không có đích. Ví dụ này cho thấy một điều kiện cần không tự biến thành điều kiện đủ. Có tiền đủ trả bữa ăn chưa có nghĩa quán còn mở cửa.

Cũng vì thế, không nên lấy nguyên tiêu chuẩn của bài hai bình có vòi nước và được đổ bỏ để áp vào ba bình sữa. Thêm nguồn nước và chỗ đổ đi là thay luật, làm thay đổi những trạng thái có thể tới.

Từ chia sữa tới phương trình nghiệm nguyên

Ta tạm rời động tác rót, chỉ xét phép tính với dung tích 5 và 3. Có thể ghép những bội nguyên của chúng để được 4 không?

5x−3y=4.5x-3y=4.

Có: x=2x=2, y=2y=2, vì 2×5−2×3=42\times5-2\times3=4. Ở đây x, y là hệ số của phép cộng trừ, không phải lượng sữa đang nằm trong từng bình. Dấu trừ cũng không bảo ta đổ bỏ sữa; nó chỉ mô tả phần được lấy bớt khi so sánh các lượng.

Phương trình kiểu ax+by=cax+by=c, với x và y phải nguyên, là phương trình Diophantine tuyến tính. “Tuyến tính” ở đây nghĩa là mỗi lần thêm một đơn vị x thì tổng tăng cùng một lượng a, như mua thêm một túi gạo cùng loại thì hóa đơn tăng đúng giá một túi.[2]

Tính chất cốt lõi rất gọn: với a, b nguyên và không đồng thời bằng 0, phương trình có nghiệm nguyên khi và chỉ khi c chia hết cho ƯCLN của a và b. Chẳng hạn 6x+4y=56x+4y=5 không có nghiệm nguyên, vì vế trái luôn chẵn còn vế phải lẻ.[2]

Lý do của chiều ngược dựa trên đẳng thức Bézout: ƯCLN của hai số luôn biểu diễn được bằng một tổ hợp nguyên của chúng. Như tìm ra một “đồng tiền cơ sở” bằng cách cộng trừ hai mệnh giá. Với 5 và 3, ta có 1=2×3−51=2\times3-5; nhân cả hai vế lên tạo ra mọi bội nguyên của 1.[2]

Nghiệm nguyên khác nghiệm nguyên không âm thế nào?

Một cửa hàng chỉ bán túi 3 kg và 5 kg. Bạn muốn mua đúng 14 kg. Gọi x là số túi 3 kg, y là số túi 5 kg, ta có 3x+5y=143x+5y=14 và phải thêm x,y≥0x,y\geq0. Lời giải là ba túi nhỏ và một túi lớn.

Đổi mục tiêu thành 1 kg. Phương trình 3x+5y=13x+5y=1 vẫn có nghiệm nguyên, chẳng hạn x=2x=2, y=−1y=-1. Nhưng không thể mua âm một túi. Thế nên không có phương án mua chỉ bằng những túi đóng sẵn, dù điều kiện ƯCLN bằng 1 vẫn đúng.

Bài vừa gà vừa chó cũng có ranh giới ấy. Phương trình có thể cho 14,5 con chó, nhưng người đếm vật nuôi không nhận đáp án đó. Bài chia sữa thêm một tầng nữa: ngay cả một trạng thái cuối hợp dung tích cũng phải có đường đi tới.

Phương trình nghiệm nguyên dùng ở đâu ngoài câu đố chia sữa?

Khi đại lượng chỉ nhận từng đơn vị rời nhau, đáp án gần đúng có thể không dùng được. Không thể giao 2,4 thùng hàng nếu khách chỉ nhận nguyên thùng. Ba ví dụ dưới đây đi từ việc mua hàng tới lịch vận hành và một bước tạo khóa mật mã. Các con số đều là ví dụ minh họa, không phải dữ liệu của doanh nghiệp.

Đóng gói: đủ số lượng rồi, phương án nào ít kiện hơn?

Một cửa hàng có hai loại kiện, chứa 3 và 5 chai. Đơn hàng cần đúng 24 chai, không được tháo kiện. Nếu x là số kiện nhỏ và y là số kiện lớn, điều kiện là 3x+5y=243x+5y=24, với x, y nguyên không âm.

Có hai cách: 8 kiện nhỏ, hoặc 3 kiện nhỏ và 3 kiện lớn. Cả hai giao đủ hàng, nhưng cách thứ hai chỉ có 6 kiện thay vì 8. Nếu mỗi kiện tốn cùng một khoản xử lý, đó là phương án ít công hơn trong mô hình này.

Ta vừa thêm một câu hỏi vào phương trình: trong các nghiệm hợp lệ, nghiệm nào làm x + y nhỏ nhất? Đây là một dạng tối ưu nguyên, giống việc chọn số hộp sao cho vừa đủ hàng mà ít lần bê nhất. Phương trình nói “đủ 24 chai”; điều kiện nguyên không âm nói “kiện có thật”; mục tiêu nói “chọn cách nào”.

Ngoài đời, chi phí hai loại kiện có thể khác nhau, xe có giới hạn tải, kho có thể hết kiện lớn. Khi ấy phải bổ sung điều kiện, không thể lấy đáp án 6 kiện làm lời khuyên cho mọi đơn hàng. Bài toán đóng gói lớn thuộc một mô hình rộng hơn; đẳng thức Bézout không tự giải hết phần tối ưu.

Xếp lịch: hai máy bao giờ cùng có mặt để bảo dưỡng?

Giả sử một máy kết thúc chu kỳ vào các phút 0, 6, 12, 18… Máy còn lại kết thúc vào phút 4, 12, 20, 28… Muốn dừng cả hai đúng lúc hoàn tất chu kỳ, ta cần một thời điểm nằm trong cả hai danh sách. Nhìn bằng mắt thấy phút 12, nhưng với chu kỳ dài hơn ta muốn tính thay vì liệt kê.

Gọi thời điểm ấy là t. Ta có t=6xt=6x và t=4+8yt=4+8y, nên:

6x−8y=4.6x-8y=4.

Nghiệm x=2x=2, y=1y=1 cho t = 12 phút. Hai máy gặp lại nhau sau mỗi 24 phút: 12, 36, 60… Khoảng 24 là bội chung nhỏ nhất của 6 và 8, giống hai chiếc kim có nhịp khác nhau nhưng định kỳ trở lại cùng một vị trí tương đối.

Bây giờ cho máy thứ hai bắt đầu ở phút 3 thay vì 4. Phương trình thành 6x−8y=36x-8y=3. Vế trái luôn chẵn nên không thể bằng 3: không có lần trùng nào nếu giữ nguyên lịch. Ta biết điều đó trước khi thử hàng nghìn chu kỳ, nhờ điều kiện ƯCLN đã giải thích ở trên.[2]

Cách ghi “t chia cho 6 dư 0, chia cho 8 dư 4” gọi là đồng dư, tức chỉ quan tâm vị trí trong một chu kỳ. Nó giống đồng hồ: qua 12 giờ thì mặt số lặp lại. Khi dùng để vận hành thật, vẫn phải kiểm tra thời gian bảo dưỡng, khoảng cho phép và sai lệch nhịp máy; gặp nhau ở một thời điểm chưa có nghĩa đủ thời gian làm việc.

RSA: một phương trình nghiệm nguyên giúp tạo khóa thế nào?

Một ứng dụng xa hơn nằm trong bước tạo khóa RSA. Ở đây cần tìm một số d sao cho nhân với một số e rồi lấy phần dư theo một số m sẽ được 1. Số d gọi là nghịch đảo modulo của e theo m: giống một nút “hoàn tác phép nhân”, nhưng hoạt động trên vòng số dư chứ không phải phép chia thông thường.[2]

Lấy ví dụ nhỏ, tìm d để 7d7d chia cho 40 dư 1. Điều ấy tương đương tìm hai số nguyên d, k thỏa:

7d−40k=1.7d-40k=1.

Ta có d = 23, k = 4, vì 7×23−40×4=161−160=17\times23-40\times4=161-160=1. ƯCLN(7,40) bằng 1 nên nghịch đảo tồn tại. Thuật toán Euclid mở rộng tìm các hệ số ấy một cách có hệ thống: chia lấy dư, rồi lần ngược để viết số dư cuối thành tổ hợp của hai số ban đầu.[2]

Cụ thể, 40=5×7+540=5\times7+5, 7=1×5+27=1\times5+2, rồi 5=2×2+15=2\times2+1. Lần ngược lại, ta có 1=5−2(7−5)=3×5−2×71=5-2(7-5)=3\times5-2\times7. Thay 5=40−5×75=40-5\times7 vào thì 1=3×40−17×71=3\times40-17\times7. Hệ số của 7 là −17; cộng 40 vào được 23, vì hai số này cho cùng phần dư khi chia cho 40. Ta không phải thử lần lượt mọi d.

Trong cách dựng RSA nhập môn, chọn hai số nguyên tố p = 5, q = 11, ta có n = 55 và φ(n)=(p−1)(q−1)=40\varphi(n)=(p-1)(q-1)=40. Chọn e = 7, tìm d = 23 bằng đúng phép tính trên. Quan hệ giữa hai số mũ là một phần làm cho phép mã hóa rồi giải mã trả lại thông điệp.[4]

Đây chỉ là chiếc cầu để nhận ra phương trình nghiệm nguyên trong công nghệ, không phải hướng dẫn tự xây hệ mật mã. Nghịch đảo được tính nhanh khi biết m, còn an toàn của RSA không đến từ việc phép tính này khó. Ví dụ 5 và 11 quá nhỏ để bảo mật; RSA dùng thực tế còn cần cách chọn khóa, mã hóa thông điệp và lược đồ đệm đúng chuẩn. Bài RSA và chữ ký số cho JWT giải thích phần hệ thống ấy kỹ hơn.

Từ khóa RSA tới tài khoản ngân hàng còn những bước nào?

Khi mở một dịch vụ ngân hàng trực tuyến, ta cần phân biệt hai câu hỏi: kết nối có đi tới đúng dịch vụ không, và người đang yêu cầu giao dịch có quyền làm việc đó không? Một chữ ký số giúp kiểm tra một thông điệp có được tạo bởi bên giữ khóa bí mật tương ứng hay không, giống kiểm tra con dấu trên một giấy xác nhận. Nó không tự chứng minh người cầm điện thoại là chủ tài khoản.[4]

Trong những hệ thống dùng RSA để ký hoặc xác thực, phép tìm nghịch đảo vừa xem là một phần của bước tạo khóa. Khóa ấy chỉ có ích khi được đặt trong quy trình đúng: kiểm tra danh tính bên phát hành, bảo vệ khóa bí mật và sử dụng lược đồ mật mã chuẩn. Một hệ thống cụ thể cũng có thể chọn thuật toán khác; không thể nhìn biểu tượng ổ khóa rồi suy ra ngân hàng đang dùng RSA.

Mật khẩu, OTP và giới hạn giao dịch giải những câu hỏi bổ sung. Biết tính 7×23≡1(mod40)7\times23\equiv1\pmod{40} không giúp chống lại mọi kiểu lừa đảo hay việc tự đưa mã xác nhận cho người khác. Câu đố chia sữa dẫn tới một công cụ toán học dùng trong bảo mật, chứ không phải toàn bộ lời giải bảo vệ tài khoản. Đó là ý nghĩa và cũng là giới hạn của mối liên hệ trên tiêu đề.

Ba ứng dụng không có nghĩa Diophantus đã nghĩ tới đóng gói hiện đại, lịch máy hay RSA. Mối nối nằm ở loại câu hỏi: tìm những số nguyên thỏa điều kiện. Khi câu hỏi đổi từ “có nghiệm” sang “ít kiện nhất”, “lần gặp đầu tiên” hoặc “khóa dùng an toàn”, ta phải thêm công cụ và giả thiết tương ứng.

Vì sao bảy lượt là ít nhất, không chỉ là một lời giải?

Hãy coi mỗi cách phân bố sữa là một địa điểm. Từ (8,0,0) rót đầy bình vừa thì đi tới (3,5,0). Một lượt rót hợp lệ là một con đường nối hai địa điểm. Danh sách địa điểm và đường nối gọi là đồ thị, giống sơ đồ các ga tàu với đường đi giữa chúng.

Với bài 8–5–3, có 24 bộ số nguyên không âm thỏa tổng bằng 8 và không vượt dung tích từng bình. Nhưng chỉ 16 bộ đi tới được từ điểm ban đầu theo luật đầy hoặc cạn. Chẳng hạn (2,4,2) đủ sữa và vừa bình, nhưng cả ba bình đều không đầy, không cạn. Nó không thể là kết quả của một lượt rót theo luật này.

Muốn tìm đường ngắn nhất, ta kiểm tra tất cả nơi đến được sau một lượt, rồi sau hai lượt, rồi ba lượt. Cách ấy gọi là tìm kiếm theo chiều rộng (breadth-first search, BFS), như tìm một người qua các vòng bạn bè: người quen trực tiếp trước, bạn của bạn sau. Khi mỗi đường đều tính một lượt, lần đầu gặp đích chính là số lượt ít nhất.[3]

Kết quả chạy cho đúng mô hình trong bài là 7 lượt. Không phải vì máy tính “thử khéo” hơn, mà vì nó kiểm tra theo từng tầng, không bỏ qua một đường ngắn hơn. Tối ưu số lượt rót khác tối ưu số kiện hàng, nhưng cả hai đều buộc ta nói rõ một điều: đang đếm chi phí nào?

Ba điều câu đố không cho phép lẫn vào nhau

Không có vạch không có nghĩa không đo được. Dung tích đầy và chỗ trống đã là mốc đo. Nhưng ta không được giả sử biết vị trí nửa bình bất kỳ, nhất là khi hình dạng bình không đều.

Số nguyên không có nghĩa chất lỏng rời rạc. Sữa vẫn chia nhỏ được. Những lượng nguyên xuất hiện vì đầu vào và thao tác của mô hình. Nếu dung tích là 2,5 lít, ta có thể chọn nửa lít làm đơn vị rồi viết lại bằng số nguyên.

Tên Diophantus không phải giấy chứng nhận tác giả câu đố. Bài này nối một câu đố quen với một hướng nghiên cứu mang tên ông. Không có nguồn ở đây nói ông từng chia sữa bằng ba bình.

Tự tay tìm đường rót và vẽ lại bảy lượt

Đoạn Python dưới đây duyệt đủ các trạng thái đi tới được, truy ngược một đường ngắn nhất rồi tạo đúng Hình 1. Nó chỉ dùng thư viện chuẩn và Pillow để vẽ. Không có bước ngẫu nhiên nên không cần seed; thứ tự thử các cặp bình được cố định.

Lưu đoạn code thành chia_sua.py, chạy trong thư mục bạn muốn lưu ảnh. Ảnh ra là bay-luot-rot.png. Phần vẽ không tham gia tìm lời giải: nếu đổi dung tích mà không tìm được đích, chương trình báo thay vì vẽ một đường rót tưởng tượng.

chia_sua.py
from collections import deque
from PIL import Image, ImageDraw, ImageFont
cap, start, goal = (8, 5, 3), (8, 0, 0), (4, 4, 0)
queue, parent = deque([start]), {start: None}
while queue:
s = queue.popleft()
for i in range(3):
for j in range(3):
amount = min(s[i], cap[j] - s[j]) if i != j else 0
if not amount:
continue
nxt = list(s)
nxt[i] -= amount
nxt[j] += amount
nxt = tuple(nxt)
if nxt not in parent:
parent[nxt] = s
queue.append(nxt)
if goal not in parent:
raise SystemExit("Không có đường rót tới đích")
path, state = [], goal
while state is not None:
path.append(state)
state = parent[state]
path.reverse()
print("Trạng thái đi tới được:", len(parent))
print("Số lượt ít nhất:", len(path) - 1)
print(" -> ".join(map(str, path)))
# Dùng Arial có sẵn trên macOS; máy khác đổi hai đường dẫn font Unicode.
regular = "/System/Library/Fonts/Supplemental/Arial.ttf"
bold = "/System/Library/Fonts/Supplemental/Arial Bold.ttf"
bg, panel, ink = "#10151e", "#19212d", "#efe3cc"
muted, milk, gold = "#afb8c6", "#d8cbb2", "#e8b05a"
im = Image.new("RGB", (1600, 990), bg)
draw = ImageDraw.Draw(im)
def text(xy, value, size=28, color=ink, strong=False):
f = ImageFont.truetype(bold if strong else regular, size)
draw.text(xy, value, font=f, fill=color, anchor="mm")
text((800, 58), "Bảy lượt rót, hai phần bằng nhau", 44, strong=True)
text((800, 112), "Lượng sữa tính bằng lít; chỉ dừng khi bình nguồn cạn hoặc bình đích đầy.", 26, muted)
for step, volumes in enumerate(path):
x, y = 34 + (step % 4) * 395, 165 + (step // 4) * 395
draw.rounded_rectangle((x, y, x + 365, y + 350), 10, fill=panel)
text((x + 182, y + 37), "Ban đầu" if step == 0 else f"Lượt {step}", 30, strong=True)
for j, (capacity, volume) in enumerate(zip(cap, volumes)):
left, bottom, width = x + 40 + j * 100, y + 240, 65
height = capacity * 15
draw.rounded_rectangle((left, bottom - height, left + width, bottom), 5, fill=panel)
if volume:
fill = gold if step == 7 and volume == 4 else milk
draw.rectangle((left + 4, bottom - volume * 15 + 3, left + width - 4, bottom - 4), fill=fill)
draw.line([(left, bottom - height), (left, bottom), (left + width, bottom), (left + width, bottom - height)], fill=ink, width=3)
text((left + width / 2, bottom + 23), f"{capacity} L", 22, muted)
text((left + width / 2, bottom - height - 20), str(volume), 25, strong=True)
text((x + 182, y + 310), str(volumes), 26, gold if step == 7 else ink)
text((800, 965), "Tính bằng tìm kiếm theo chiều rộng; đã duyệt đủ 16 trạng thái đi tới được.", 25, muted)
im.save("bay-luot-rot.png")

Kết quả: 16 trạng thái đi tới được, 7 lượt ngắn nhất, với dãy đúng như bảng đầu bài. Bạn có thể đổi ba dung tích sang 12, 8, 4, điểm xuất phát sang (12,0,0) và đích sang (6,6,0): chương trình báo không có đường. Thử 10, 6, 3 cũng cho một ví dụ không tới được đích (5,5,0), dù ƯCLN của ba dung tích bằng 1.

Quay lại bình sữa không có vạch

Bình 3 lít cuối cùng đã rỗng. Hai bình còn lại cùng có 4 lít, không ai phải ước lượng bằng mắt. Lời giải đến từ việc giữ một lượng sữa ở đúng chỗ, để phần còn trống của bình trở thành dụng cụ đo.

Từ câu đố ấy, ta có ba câu hỏi riêng: con số mong muốn có bị số học cấm không, có trình tự thao tác hợp lệ không, và trình tự ngắn nhất dài bao nhiêu. Phương trình nghiệm nguyên giúp với câu đầu. Bản đồ trạng thái và cách tìm đường giải hai câu sau. Đơn hàng nguyên kiện, hai lịch máy và phép tìm nghịch đảo trong RSA cũng đòi tách điều kiện số học khỏi những yêu cầu riêng của công việc.

Diophantus không cần xuất hiện trong một giai thoại chia sữa để mối nối này có ý nghĩa. Tên ông nhắc ta hỏi thêm một điều trước khi giải phương trình: những nghiệm nào được phép nhận? Trên trang giấy có thể là số nguyên. Trên bàn, đáp án còn phải rót được vào bình.

Vẽ minh họa hình học miễn phí cho học sinh và giáo viên: EyeViz.

Tài liệu tham khảo

  1. [1]J. J. O’Connor và E. F. Robertson. Diophantus of Alexandria. MacTutor History of Mathematics, University of St Andrews.
  2. [2]Các tác giả CP-Algorithms. Linear Diophantine Equation. CP-Algorithms.
  3. [3]Các tác giả CP-Algorithms. Breadth First Search. CP-Algorithms.
  4. [4]R. L. Rivest, A. Shamir và L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126, 1978.