Câu chuyện Sơn Tinh – Thủy Tinh và bài toán không tưởng

—-

Nguyên văn: Bài toán Tổng và Tích (Sum and Product Puzzle) hay Bài toán không tưởng (Impossible Puzzle). Bạn đọc có thể dựa vào keyword trên để tìm đọc phiên bản gốc. Ở đây mình mạn phép phóng tác gắn vào truyền thuyết Sơn Tinh – Thủy Tinh nhằm tạo sự thú vị.

—-

Đời Hùng Vương thứ 18 có một người con gái xinh đẹp tuyệt trần, trí tuệ siêu phàm, tên là Mỵ Nương. Có hai chàng trai đến xin hỏi cưới, tên là Sơn Tinh và Thủy Tinh. Hai người đều to cao vạm vỡ, sức khỏe hơn người và đặc biệt là trí óc phi thường.

Qua nhiều lần thử tài bất phân thắng bại, Hùng Vương tuyên bố:

Đoạn, nhà vua nhẩm nghĩ trong đầu rồi lần lượt gọi Sơn Tinh và Thủy Tinh đến thì thầm nói. Xong xuôi, ai nấy đề về nhà ngẫm nghĩ.

Sáng hôm sau, Thủy Tinh gặp Sơn Tinh. Anh ta khoanh tay:

Sơn Tinh đăm chiêu một hồi lâu. Chàng nói:

Thủy Tinh ngạc nhiên, ngẫm nghĩ một hồi. Anh ta cũng reo lên:

Mỵ Nương nghe được đoạn hội thoại trên, nhanh trí chạy về nói với Hùng Vương đáp án. Vua cha lấy làm hài lòng lắm, tuyên bố Sơn Tinh và Thủy Tinh đều bị loại, Mỵ Nương ở vậy cả đời.

Mỵ Nương đã giải bài toán trên bằng cách nào khi không biết được 2 con số mà Hùng Vương đã nói với các chàng trai?

—-

Cho các bạn 5 phút suy nghĩ. À không, kể cả 5 phút bạn có nghĩ ra cách giải thì cũng không kịp làm được đâu.

Nếu ai đọc đến đây mà tò mò muốn xem cách giải, hãy đọc tiếp đoạn sau nhé!

—-

Trước khi đi vào lời giải, hãy bàn luận một chút về bài toán. Giải được bài toán này, Sơn Tinh và Thủy Tinh quả là những bộ óc thông minh. Tuy nhiên Mỵ Nương mới là giỏi nhất: nàng thậm chí còn không được biết nhiều dữ kiện bằng họ, vậy mà vẫn có thể giải được. Nghe vẻ rất phi lý đúng không?

Thoạt nghe qua, người đọc có thể nghĩ đây là một bài toán không thể giải được với chỉ bằng ấy dữ kiện. Tuy nhiên, chắc chắn nó có cách giải, không những thế, nhiều hơn một cách. Dưới đây là cách tiếp cận trực tiếp nhất, vét cạn nhất, tay to nhất (không giờ Mỵ Nương tay to đến thế!).

Ta quy ước cặp số X, Y sao cho X+Y=A gọi là một cặp khai triển của A.

—-

Đêm đầu tiên:

Sơn Tinh, Thủy Tinh và Mỵ Nương, ba người đều lấy giấy bút viết ra một bảng số.

Do hai số tự nhiên khác nhau, lớn hơn 1, tổng nhỏ hơn 100, vì thế tổng khả dĩ trong đoạn 5 đến 100.

Ba người khai triển tất cả các số trong cột số thành tổng. Với mỗi cặp khai triển, tính tích của chúng và đánh dấu tick vào kết quả trên trục số.

Đến đây thì Sơn Tinh và Mỵ Nương bế tắc. Chỉ có Thủy Tinh có thêm dữ kiện để suy nghĩ. Anh ta nhìn vào con số tổng mà Hùng Vương nói cho, dò trong bảng 1. Thủy Tinh nhận thấy: các cặp khai triển của số Hùng Vương nói cho đều cho ra các tích mà trên trục số có nhiều hơn 1 dấu tick!

Anh ta lập luận rằng: cặp nghiệm phải nằm đâu đó trong đây, tuy nhiên đều không cho ra tích duy nhất. Vì thế phía bên Sơn Tinh nhận được con số tích này chắc chắn không thể suy ra được cặp nghiệm.

Chính vì thế, sáng hôm sau, Thủy Tinh tuyên bố: “Sơn Tinh không thể biết được cặp số đó là gì”

—-

Sau khi nghe lời phát biểu của Thủy Tinh, Sơn Tinh như mở cờ trong bụng. “Thế là có thêm dữ kiện rồi”.

Sơn Tinh viết ra bảng số 2. Mỵ Nương và Thủy Tinh vì muốn theo dòng suy nghĩ của Sơn Tinh nên cũng làm theo.

Mỵ Nương đến đây thì bế tắc. Thủy Tinh đã biết chính xác tổng ấy rồi nên chỉ làm theo để theo suy nghĩ của Sơn Tinh thôi, tuy nhiên đến đây hắn cũng bí nốt.

Lúc này, Sơn Tinh nhìn vào con số được Hùng Vương tiết lộ, chính là tích của cặp nghiệm. Chàng tra trong Bảng 2. Thật bất ngờ, chỉ có một tổng có cặp khai triển cho tích là số mà anh nắm giữ! Đó chắc chắn là tổng của hai số cần tìm, tức là số mà Thủy Tinh nắm giữ.

Với tổng và tích đã biết, Sơn Tinh dễ dàng tìm được cặp số cần tìm.

Anh tuyên bố: “Ta đã biết đáp án!”

—-

Thủy Tinh rất ngạc nhiên, còn Mỵ Nương không hiểu chuyện gì đang xảy ra. Thủy Tinh bình tĩnh suy ngẫm lại. Anh ta viết thêm vào Bảng 2 một trục số tự nhiên. Tương tự Bảng 1, Thủy Tinh đánh dấu vào các số là tích của cặp khai triển có trong bảng 2.

Chú ý rằng trạng thái đánh dấu của Bảng 1 và Bảng 2 là khác nhau. Do đã loại bớt nhiều số trong khoảng 5 đến 100, có thể một số nào đó trên trục của Bảng 1 là 2 tick, nhưng xuống Bảng 2 chỉ còn 1 tick, v.v…

Sau đó Thủy Tinh nhìn vào các khai triển của số mà anh nắm giữ. Trong số các cặp khai triển, chỉ có duy nhất 1 cặp là cho ra tích có 1 tick trên Bảng 2!

Vì Sơn Tinh đã tuyên bố giải ra được bài toán, nên đây là nghiệm duy nhất. Nếu không có tuyên bố của Sơn Tinh, cho dù Thủy Tinh có làm các bước trên mà tìm được 1 cặp khai triển cho ra tích duy nhất thì cũng chưa thể khẳng định được gì.

Đó chính là cặp nghiệm cần tìm. Đến đây, Thủy Tinh tuyên bố đã giải được bài toán.

—-

Còn lại mỗi Mỵ Nương bé bỏng. Ban nãy cô cũng viết Bảng 2 và tính thêm trục để theo dòng suy luận của Thủy Tinh. Tuy nhiên vì không được biết ít nhất tổng hoặc tích nên Mỵ Nương vẫn chưa thể giải ra được. Nhưng đến khi Thủy Tinh tuyên bố giải xong, Mỵ Nương vỗ đùi cái đét, thì ra đó chính là dữ kiện cuối cùng giúp cô ế cả đời.

Không có gì bất ngờ, chỉ có duy nhất một tổng như vậy (bởi nếu có một cặp nghiệm nữa thì Sơn Tinh hay Thủy Tinh đều đã không thể giải được trước đó).

Sơn Tinh và Thủy Tinh giải ra trước nhưng vì thủ tục nhập cung rườm rà nên đang đợi để được vào chầu vua. Còn Mỵ Nương tuy giải ra sau nhưng là con ông cháu cha nên được gặp thẳng Hùng Vương. Thế là Mỵ Nương là người chiến thắng!

—-

Người đời sau nghe được câu chuyện này, không thể tin được với tư duy của con người thời ấy mà có thể nhẩm ra được bao nhiêu bảng số nhanh đến vậy. Mãi đến sau này, khi khai quật bia mộ Mỵ Nương, người ta mới tìm được đoạn code sau đây, tương truyền rằng do Mỵ Nương thức đêm mà viết ra để chạy cho nó nhanh.

Đáp án cuối cùng là gì? Còn lâu mới nói, các bạn tự đoán nhé!

Code C# (Click để xem. Nguồn: fb Tuấn Đào.

Link comment gốc:

https://www.facebook.com/tapluan/posts/1552624211424882?comment_id=1552864461400857)

Ông cha ta đã dịch code của Mỵ Nương ra làm nhiều thứ tiếng, làm thành một chương trong cuốn 300 bài code thiếu nhi. Dev ta đời đời lấy đó làm răn.

Link code bởi nhiều thứ tiếng: (Comment của bạn Nguyễn Thành Đô dưới bài viết):

https://rosettacode.org/wiki/Sum_and_Product_Puzzle

—-

Đây là một bài toán khó, thuần về số học, có một chút logic. Nếu chịu khó lập luận logic hơn để loại trừ đi nhiều trường hợp, vận dụng kiến thức về số nguyên tố, bình phương,… ta sẽ được một cách giải mà không phải “vét cạn” như trên. Tuy nhiên, nếu code để máy tính toán, ta cũng chẳng quan tâm phải tối ưu input để làm gì, vài trăm số thế này với máy tính là chuyện nhỏ.

Bài toán thú vị, lợi dụng tính đặc biệt của các cặp số. Tuy nhiên, nó ít có tính ứng dụng vào các lĩnh vực trong cuộc sống, chỉ phù hợp để khoa học thường thức.

Bài viết được lấy cảm hứng từ một bài viết trên page Tạp Luận. Câu hỏi trên Tạp Luận được biến thể đi khó hơn.

Link bài viết: https://www.facebook.com/tapluan/posts/1552624211424882

—-

1:23 AM 07/08/2020