Bài toán hoán vị nâng tỷ lệ sống sót từ 0,4 phần trăm lên 35 phần trăm trong trò chơi sinh tử

Căn phòng tử thần Catenati và phép thử sinh tồn khắc nghiệt

Bị mắc kẹt trên hành tinh lạ của chủng tộc Catenati khi tàu Enterprise khẩn cấp rời đi, Trung úy Uhura cùng 7 thuyền viên đối mặt với án tử hình vì cáo buộc xâm nhập. Do luật pháp thừa nhận yếu tố bất định, quan tòa Catenati quyết định thi hành hình phạt theo xác suất thông qua buồng roulette sinh học, nơi số phận của 8 con người bị trói buộc chặt chẽ:

• Trong phòng có 8 nút bấm xếp hàng, mỗi nút phản ứng sinh học chính xác với một thành viên trong nhóm.
• Bên ngoài, mỗi nút được dán nhãn ngẫu nhiên tên của một người, do đó nhãn tên và dấu hiệu sinh học thực tế không nhất thiết trùng khớp nhau.
• Từng người lần lượt bước vào phòng theo thứ tự do tòa chỉ định, được phép bấm tối đa 4 nút (tức một nửa tổng số nút). Màn hình sẽ hiển thị tên người thực sự sở hữu nút đó.
• Nhiệm vụ bắt buộc là mỗi người phải tìm đúng nút của chính mình. Chỉ cần một người thất bại hoặc bấm nút thứ năm, cả 8 người sẽ bị xử tử ngay lập tức. Toàn đội chỉ được tự do khi tất cả cùng thành công.
• Sau lượt bấm, người chơi bị cách ly vào buồng giam riêng và hoàn toàn không thể truyền tin hay phát tín hiệu cho những người vào sau.

Chekov nhanh chóng làm phép tính xác suất và kinh hãi thốt lên: khả năng mỗi cá nhân chọn ngẫu nhiên trúng nút của mình chỉ là $\frac{4}{8} = \frac{1}{2}$. Do các quyết định hoàn toàn độc lập, xác suất để toàn bộ 8 người cùng sống sót chỉ còn $(\frac{1}{2})^8 = \frac{1}{256} \approx 0.39\%$ – một cơ hội mong manh chưa đầy 0,4%, biến thử thách này thành trò roulette tử thần gần như cầm chắc án tử.

Phân bổ đều lượt bấm: Trực giác có cứu được phi đoàn?

Trước tỷ lệ sống sót 0,39% quá đỗi ít ỏi, một thành viên nêu ý kiến: nếu cả nhóm cùng quy ước một sơ đồ phân chia để đảm bảo mỗi nút bấm đều được một số lượng người bằng nhau chọn, liệu cơ hội sống sót chung có được cải thiện đáng kể?

Uhura suy ngẫm và nhận định rằng phương án phân bổ đồng đều này gần như vô hiệu, xác suất tổng thể vẫn khó vượt qua ngưỡng 1%. Nền tảng toán học giải thích điều này như sau:

Khi mỗi thành viên tự chọn 4 nút ngẫu nhiên và độc lập, tổng số cách chọn của 8 người lên tới $(C_8^4)^8 = 70^8$. Trong đó, số cách để một cá nhân tìm đúng nút của mình là $C_7^3 = 35$ (chọn đúng nút của bản thân và 3 nút bất kỳ trong 7 nút còn lại). Tỷ lệ thành công của mỗi người vẫn cố định là $\frac{35}{70} = \frac{1}{2}$.

Dù nhóm có lập thỏa ước để mỗi nút bấm nhận đúng 32 lượt chọn (trung bình mỗi nút có 4 người nhấn), họ cũng chỉ loại trừ bớt một số kịch bản trùng lặp kém tối ưu. Do bức tường cách ly ngăn cản mọi luồng trao đổi thông tin, sự ràng buộc phân bổ tĩnh không thể xóa bỏ tính độc lập trong các quyết định ngẫu nhiên của từng người. Xác suất tổng thể chỉ nhích lên một con số vô cùng khiêm tốn và vẫn kẹt dưới 1%.

Giải pháp lật ngược thế cờ: Thuật toán dò chu kỳ và cú bứt phá lên 35%

Để tìm thấy cơ hội sống sót thực sự, phi đoàn không thể dựa vào các lựa chọn độc lập. Uhura đã đề xuất một chiến lược mang tính đột phá: áp dụng thuật toán dò chu kỳ hoán vị để gắn kết hành vi của toàn bộ thuyền viên thành một hệ thống thống nhất.

Quy trình thực thi chiến thuật cụ thể như sau:

1. Trước khi bước vào buồng quay, nhóm quy ước đánh số thứ tự từ 1 đến 8 cho 8 thuyền viên, đồng thời đánh số 8 vị trí nút bấm trong phòng từ 1 đến 8.
2. Khi thuyền viên mang số $i$ vào phòng, người đó sẽ tiến thẳng tới nút ở vị trí $i$ và nhấn nút.
3. Màn hình hiển thị tên thuyền viên $j$ sở hữu nút đó. Nếu $j = i$, thuyền viên $i$ đã tìm thấy đúng nút của mình và THÀNH CÔNG.
4. Nếu $j \neq i$, thuyền viên $i$ tiếp tục di chuyển sang bấm nút ở vị trí $j$. Quy trình này được lặp lại kỷ luật (đọc số trên màn hình và bấm vào vị trí tương ứng) cho đến khi tìm thấy tên mình hoặc hết 4 lượt bấm.

Bằng cách tuân theo chỉ dẫn hiển thị, mỗi người đang tự bước vào đúng chu kỳ hoán vị chứa chính mình. Vì nhãn nút tạo thành các vòng khép kín rời nhau, thuyền viên $i$ chắc chắn tìm thấy nút của mình khi và chỉ khi chu kỳ chứa vị trí $i$ có độ dài không vượt quá 4!

Điểm then chốt mang tính quyết định: Toàn bộ 8 thuyền viên sẽ đồng loạt thành công nếu sơ đồ nút bấm trong phòng không chứa bất kỳ chu kỳ nào dài hơn 4. Quyết định của từng người không còn rời rạc mà đã được liên kết hoàn hảo với cấu trúc toán học của căn phòng.

Tính toán xác suất cụ thể cho trường hợp 8 người:

Tổng số hoán vị có thể có của 8 nút bấm là $8! = 40320$. Các cấu hình khiến nhóm thất bại là những hoán vị chứa chu kỳ độ dài 5, 6, 7 hoặc 8:

• Số hoán vị chứa chu kỳ độ dài 5: $\frac{8!}{5} = 8064$
• Số hoán vị chứa chu kỳ độ dài 6: $\frac{8!}{6} = 6720$
• Số hoán vị chứa chu kỳ độ dài 7: $\frac{8!}{7} = 5760$
• Số hoán vị chứa chu kỳ độ dài 8: $\frac{8!}{8} = 5040$

Tổng số hoán vị dẫn đến thất bại là:

$$8064 + 6720 + 5760 + 5040 = 25584$$

Số hoán vị thành công (hoàn toàn không có chu kỳ nào dài hơn 4) là:

$$40320 – 25584 = 14736$$

Xác suất toàn bộ phi đội sống sót trở về được nâng lên mức:

$$P = \frac{14736}{40320} = \frac{307}{840} \approx 36.55\%$$

Từ con số 0,39% gần như vô vọng, toán học thuần túy đã đưa tỷ lệ sống sót lên hơn 36,5%, tức tăng gấp hơn 90 lần!

Cội nguồn lý thuyết: Trò chơi tuổi thơ và giải mã hoán vị vòng

Để giải thích cho phi đoàn hiểu rõ nguyên lý, Uhura đã nhắc lại một trò chơi vận động thời thơ ấu mang tên “Ngôi sao 6 cánh”. Sân chơi có 6 góc đánh dấu từ $A$ đến $F$, tương ứng là căn cứ của 6 người chơi từ $a$ đến $f$.

Mỗi vòng bắt đầu khi 6 đứa trẻ đứng ngẫu nhiên vào các vị trí $A$ đến $F$. Người mang số $a$ sẽ chạy đến chiếm vị trí của bạn đang ở căn cứ $A$. Bạn nhỏ bị mất chỗ lập tức chạy đến căn cứ tương ứng với nhà mình, tạo thành một chuỗi khép kín. Vòng lặp tiếp diễn với những bạn chưa chạy cho đến khi tất cả được sắp xếp xong.

Uhura nhận ra cấu trúc này chính là mô hình hoán vị vòng (cycle permutation). Khi một tập hợp gồm $N$ phần tử bị xáo trộn ngẫu nhiên, nó luôn phân rã thành các chu kỳ rời nhau có độ dài từ 1 đến $N$.

Xét bài toán 6 người: xác suất để không có chu kỳ nào có độ dài lớn hơn 3 là bao nhiêu?

Tổng số cách xếp ngẫu nhiên 6 người vào 6 vị trí là $6! = 720$ hoán vị. Một hoán vị bị coi là “xấu” nếu chứa chu kỳ độ dài 4, 5 hoặc 6. Vì tổng số là 6, một hoán vị chỉ có thể chứa tối đa 1 chu kỳ có độ dài $> 3$.

• Chu kỳ độ dài 4: Chọn 4 người có $C_6^4 = 15$ cách, tạo chu kỳ có $(4-1)! = 6$ cách, 2 người còn lại có $2! = 2$ cách. Số trường hợp là $15 \times 6 \times 2 = 180$ (tính nhanh: $\frac{6!}{4} = 180$).
• Chu kỳ độ dài 5: Chọn 5 người có $C_6^5 = 6$ cách, tạo chu kỳ có $(5-1)! = 24$ cách, người còn lại đứng yên ($1! = 1$). Số trường hợp là $6 \times 24 \times 1 = 144$ (tính nhanh: $\frac{6!}{5} = 144$).
• Chu kỳ độ dài 6: Xếp 6 người vào một chu kỳ lớn có $(6-1)! = 120$ cách (tính nhanh: $\frac{6!}{6} = 120$).

Tổng số hoán vị xấu là:

$$180 + 144 + 120 = 444$$

Số hoán vị tốt (không chứa chu kỳ nào dài hơn 3) là:

$$720 – 444 = 276$$

Xác suất cần tìm đạt mức:

$$P = \frac{276}{720} = \frac{23}{60} \approx 38.33\%$$

(Thử nghiệm trên sân chơi 4 góc: Tổng số hoán vị $4! = 24$. Các chu kỳ bất lợi $> 2$ gồm chu kỳ 3 ($\frac{24}{3} = 8$) và chu kỳ 4 ($\frac{24}{4} = 6$). Tổng số hoán vị xấu là 14. Tỷ lệ không có chu kỳ $> 2$ là $\frac{24 – 14}{24} = \frac{10}{24} \approx 41.67\%$).

Mối nguy từ kẻ phá hoại và sự bảo mật của quy ước

Nếu một lính gác Catenati nảy sinh nghi ngờ và lén đảo lộn nhãn dán trên các nút bấm trước giờ thực hiện, liệu kế hoạch của nhóm thám hiểm có bị phá sản?

Nếu tên lính chỉ tráo đổi các nhãn dán một cách ngẫu nhiên, hắn hoàn toàn không làm thay đổi xác suất tổng thể! Cấu trúc không gian hoán vị vẫn giữ nguyên tỷ lệ 36,55% các hoán vị có chu kỳ $\le 4$.

Tuy nhiên, nếu tên lính biết được sơ đồ đánh số của nhóm (biết ai mang số nào và vị trí nút nào tương ứng với số nào), hắn có thể chủ đích sắp xếp các nhãn dán thành một chu kỳ dài 8 phần tử. Khi đó, tỷ lệ sống sót sẽ rơi thẳng về 0%!

Chính vì vậy, bí mật cốt tử mà phi đoàn phải giữ kín tuyệt đối là quy ước đánh số thứ tự cá nhân và sơ đồ gán vị trí nút bấm, không để lộ bất kỳ dấu hiệu nào cho đối phương.

Quy mô mở rộng vô tận và hằng số sinh tồn 30% kỳ diệu

Điều gì sẽ xảy ra nếu thử thách không dừng lại ở 8 người mà mở rộng lên 100 người, 1.000 người, hay tổng quát $N$ người (với $N$ là số cực kỳ lớn và mỗi người được bấm $\frac{N}{2}$ nút)?

Nếu bấm ngẫu nhiên, xác suất thành công sẽ là $(\frac{1}{2})^N \to 0$ và lao dốc rất nhanh. Với 100 người, con số này chỉ còn $(\frac{1}{2})^{100} \approx 7.88 \times 10^{-31}$ – một xác suất gần như bằng không trong thực tế.

Nhưng với chiến thuật chu kỳ của Uhura, khi $N$ tiến tới vô cùng, tổng xác suất thất bại được biểu diễn qua chuỗi harmonic:

$$\text{Tỷ lệ thất bại} = \sum_{k = N/2 + 1}^{N} \frac{1}{k}$$

Khi $N \to \infty$, chuỗi rời rạc này tiến tới tích phân xác định:

$$\int_{N/2}^{N} \frac{1}{x} dx = \ln(N) – \ln\left(\frac{N}{2}\right) = \ln(2) \approx 0.69315$$

Từ đó, xác suất sống sót tối thiểu tiệm cận về một hằng số:

$$1 – \ln(2) \approx 1 – 0.69315 = 0.30685 \approx 30.69\%$$

Một kết quả làm kinh ngạc giới toán học: dù số lượng thành viên có tăng lên hàng triệu người, chỉ cần mỗi người được thử 50% số nút, tỷ lệ sống sót của toàn bộ tập thể không bao giờ giảm xuống dưới 30,69%!

Sự kỳ diệu này xuất phát từ việc chiến thuật chu kỳ gom toàn bộ các trường hợp thất bại vào chung một nhóm hoán vị. Thay vì mỗi cá nhân thất bại ở các kịch bản khác nhau làm triệt tiêu xác suất chung, giờ đây hoặc tất cả cùng thắng (khi không có chu kỳ lớn hơn $N/2$), hoặc tất cả cùng thua. Sự tương quan chặt chẽ này đã giải cứu phi đội khỏi thảm họa tuyệt đối.

Bài học thực tiễn: Sức mạnh của sự tương quan trong lý thuyết xác suất và thuật toán

Thử thách buồng quay roulette của Uhura chính là một biến thể sinh động của bài toán “100 tù nhân” kinh điển, do nhà khoa học máy tính Peter Bro Miltersen đề xuất năm 2003. Trong tư duy thường ngày, trực giác con người thường đánh giá rủi ro dựa trên giả định các cá nhân hoạt động độc lập, khiến xác suất thành công chung suy giảm theo hàm mũ và nhanh chóng sụp đổ. Tuy nhiên, bằng cách thiết lập một cấu trúc phụ thuộc thông minh thông qua chu kỳ hoán vị, tập thể có thể chia sẻ chung số phận: hoặc tất cả cùng thành công, hoặc tất cả cùng thất bại.

Nguyên lý tương quan này hiện nay không chỉ là một vẻ đẹp toán học thuần túy, mà còn được ứng dụng rộng rãi trong khoa học máy tính hiện đại, từ thiết kế thuật toán phân tán, tối ưu hóa giao thức đồng thuận trong mạng lưới phi tập trung, cho đến các phương thức phân phối khóa mật mã an toàn mà không cần phụ thuộc vào một kênh liên lạc trung tâm.

Bài viết tham khảo Quanta Magazine (quantamagazine.org).