HOÀNG TỬ ẾCH VÀ XÁC SUẤT
Lưu Minh Đức
Phỏng dịch theo bản gốc
Kissing frog: a mathematician’s guide to mating
Chắc mọi người ai cũng đều biết câu chuyện Hoàng Tử Ếch. Đây là 1 phiên bản khác của câu chuyện ấy, hơi phức tạp hơn.
HOÀNG TỬ ẾCH
Một nàng công chúa đi lạc vào 1 khu rừng nọ. Đến 1 cái ao thì 1 mụ phù thủy hiện ra và nói “Đứng lại nào, con bé kia! Ta đã biến 1 hòang tử đẹp trai thành con ếch và giam cầm nó trong cái ao này cùng với 99 con ếch khác. Mỗi con ếch đều mang 1 số trên lưng và con số của hoàng tử là lớn nhất. Đấy là cách duy nhất để ngươi nhận ra nó từ trong lũ ếch. Nếu ngươi muốn rời khòi khu rừng đã bị ếm bùa này, ngươi phải tìm ra hoàng tử và hôn nó. Mỗi con ếch sẽ lần lượt nhảy lên khỏi hồ. Khi mỗi con ếch xuất hiện, ngươi phải quyết định hôn nó hay đá nó trở lại vào ao, và mỗi con ếch chỉ nhảy lên đúng 1 lần mà thôi. Nếu ngươi hôn phải ếch thật hoặc không chịu hôn con nào thì ngươi sẽ không thể rời khu rừng và hoàng tử thì vĩnh viễn ở lại trong hồ. Và với 1 tràng cười quỷ quyệt, mụ ta chìm trở lại xuống hồ. Rất may, công chúa của chúng ta rất giỏi toán và đã tìm được chiến lược tốt nhất để quyết định nên hôn chú ếch nào.
Chú ếch 1 nhảy ra với số 2 trên lưng và thế là bị đá trở laị vô hồ, chú ếch 2 mang số 12 (có khá hơn) nhưng cũng chung số phận với chú thứ nhất. Chú thứ 3 mang số -6 trên lưng (đâu có quy định các chú ếch chỉ mang toàn số dương!) và dĩ nhiên là vô hồ ngay. Công chúa lặp lại điều này với cả 37 chú ếch đầu tiên và nhận thấy rằng số lớn nhất đã xuất hiện là 23.2 (cũng không quy định là các chú ếch chỉ mang toàn số nguyên). Thế là cô đợi đến khi có chú ếch mang số lớn hơn 23.2 và hôn nó (dĩ nhiên chú ếch mang số 23.2 có thể chính là hoàng tử và cô có thể đã bỏ lỡ cơ hội duy nhất đó!). Chú ếch biến mất sau 1 tiếng nổ “bụp” và 1 hoàng tử đẹp trai xuất hiện. Thế là họ sống hạnh phúc mãi mãi (còn nếu bạn thích kết cục bất hạnh thì: mụ phù thủy hiện lên cười đắc thắng khi chú ếch vẫn y nguyên trước sự chú ý hết mực của công chúa. Ôi trời, vẫn còn chú ếch mang số lớn hơn chưa xuất hiện! ).
QUY TẮC 37%
Chiến lược của công chúa là trước tiên thu thập 1 số thông tin về các chú ếch (cô ấy ghi nhớ số lớn nhất trong số 37 chú đầu tiên) và rồi lựa chọn dựa trên thông tin này (cô hôn chú ếch mang số cao hơn tiếp theo). Nếu số ếch là khác, cô ấy nên thu thập thông tin từ bao nhiêu con trước khi quyết định hôn? Câu trả lời là 37% của số ếch tổng cộng. Tại sao lại 37%? Nếu bạn biết các quy tắc đếm và biết rằng nguyên hàm của 1/x là , bạn có thể theo các suy luận logic dưới đây để hiểu được kết luận này.
Chứng minh quy tắc 37%
Ta hãy xét bài toán tổng quát
Có N chú ếch. Cần phải đá hết bao nhiêu chú xuống hồ để xác suất hôn trúng hoàng tử là lớn nhất?
Giả sử cần đá M chú ếch đầu tiên xuống hồ và rồi hôn chú ếch đầu tiên mà có số cao hơn M chú ban đầu này. Để xác định M ta cần tìm ra khả năng hôn trúng hoàng tử là bao nhiêu, tùy thuộc vào chuyện anh ta có xuất hiện trong dãy từ M+1 đến N hay không.
Nếu anh ta nằm trong M chú đầu tiên, thảm họa, công chúa đã bỏ qua anh ta.
Nếu anh ta là chú ếch thứ M+1, thành công, công chúa chắc chắn sẽ hôn anh ta.
Nếu anh ta là chú ếch thứ M+2, công chúa sẽ hôn anh ta trừ trường hợp xui xẻo là chú ếch thứ M+1 lại mang số cao hơn M chú đầu tiên. Tuy nhiên khà năng trường hợp xui xẻo này xảy ra chỉ là 1/(M+1) (vì số các hoán vị của M+1 chú ếch trong đó chú ở vị trí M+1 mang số cao nhất cũng bằng số các hoán vị của M+1chú mà chú mang số cao nhất ở vị trí bất kỳ. Nếu vẫn chưa rõ, hãy tính cụ thể xác suất này ra, bạn sẽ hiểu ngay). Do đó xác suất mà công chúa hôn trúng hoàng tử sẽ là....
Tải file dưới đây về để thưởng thức tiếp câu chuyện. Download.
Bản gốc có thể tìm thấy theo các liên kết sau:
http://plus.maths.org/issue48/features/billingham/index.html
http://plus.maths.org/issue48/features/billingham/proof2.html