Bài toán Montmort hỏi: xáo kỹ hai bộ bài 52 lá rồi lật đồng thời từng cặp, xác suất không có cặp nào trùng nhau là bao nhiêu? Đáp số gần như chính xác bằng 1/e ≈ 36,79%, tức khả năng có ít nhất một cặp trùng là khoảng 63,2%. Điều lạ là con số này gần như không đổi dù bộ bài có 10 lá hay 10 000 lá, và trung bình luôn có đúng 1 cặp trùng.
Bài toán từ đầu thế kỷ 18
Pierre Rémond de Montmort, một nhà toán học Pháp, đưa bài toán này vào cuốn Essay d'analyse sur les jeux de hazard xuất bản năm 1708, một trong những sách đầu tiên viết riêng về xác suất. Phiên bản của ông dùng 13 lá: vừa lật từng lá vừa đếm "một, hai, ba… mười ba", và hỏi khả năng có ít nhất một lần lá lật ra đúng con số vừa đọc. Trong tiếng Pháp, bài toán được gọi là problème des rencontres, "bài toán những lần gặp nhau".
Montmort trao đổi thư từ về nó với Nicolaus Bernoulli, và về sau Leonhard Euler cũng viết riêng về bài toán này vào giữa thế kỷ 18. Ngày nay nó là ví dụ mở đầu quen thuộc cho khái niệm hoán vị không điểm cố định, còn gọi là "xáo lệch hoàn toàn" (derangement).
Phát biểu bằng một bộ bài
Có nhiều cách phát biểu tương đương, cách nào cũng dẫn tới cùng một con số:
- Xếp một bộ bài theo thứ tự cố định, bộ kia xáo kỹ, lật song song từng cặp, đếm số cặp trùng.
- Xáo một bộ bài, lật từng lá và đếm "Át, hai, ba… K" bốn vòng: có lần nào lá lật đúng tên vừa đọc không? (Phiên bản này có bốn lá mỗi hạng nên con số hơi khác, nhưng cùng tinh thần.)
- n người bỏ mũ vào một hộp, rồi mỗi người rút ngẫu nhiên một chiếc: xác suất không ai rút trúng mũ của mình.
Về toán, tất cả đều hỏi: lấy một hoán vị ngẫu nhiên của n phần tử, xác suất không phần tử nào nằm đúng chỗ cũ là bao nhiêu?
Đếm tay với bộ bài nhỏ
Gọi D(n) là số cách xếp n lá sao cho không lá nào ở đúng vị trí ban đầu.
- n = 1: một lá chỉ có một chỗ, luôn đúng chỗ. D(1) = 0.
- n = 2: hai lá A B, chỉ có B A là lệch hết. D(2) = 1.
- n = 3: trong 6 thứ tự của A B C, chỉ B C A và C A B là không lá nào đúng chỗ. D(3) = 2, xác suất 2/6 = 33,3%.
- n = 4: liệt kê 24 thứ tự của A B C D, có 9 thứ tự không lá nào đúng chỗ, 8 thứ tự có đúng một lá, 6 thứ tự có đúng hai lá, và chỉ 1 thứ tự cả bốn lá đúng chỗ (chính thứ tự ban đầu). Không có thứ tự nào có đúng ba lá đúng chỗ, vì ba lá đúng thì lá thứ tư cũng buộc phải đúng.
Có một công thức truy hồi gọn: D(n) = (n − 1) × [D(n − 1) + D(n − 2)]. Thử: D(4) = 3 × (2 + 1) = 9, D(5) = 4 × (9 + 2) = 44, D(6) = 5 × (44 + 9) = 265. Lý do: lá thứ nhất phải đi tới một trong n − 1 chỗ khác; giả sử nó tới chỗ của lá k, thì hoặc lá k đổi chỗ ngược lại với nó (còn lại n − 2 lá phải lệch hết), hoặc không (tương đương xếp lệch n − 1 lá).
Bảng xác suất: hội tụ về 1/e cực nhanh
| Số lá n | Số cách lệch hết D(n) | Tổng số thứ tự n! | Xác suất không trùng |
|---|---|---|---|
| 2 | 1 | 2 | 50,00% |
| 3 | 2 | 6 | 33,33% |
| 4 | 9 | 24 | 37,50% |
| 5 | 44 | 120 | 36,67% |
| 6 | 265 | 720 | 36,81% |
| 10 | 1 334 961 | 3 628 800 | 36,7879% |
| 52 | số 68 chữ số | 52! | 36,787944…% |
Từ 6 lá trở đi, xác suất đã khớp 1/e tới hai chữ số thập phân của phần trăm. Với 52 lá, nó khớp tới mức không máy tính bỏ túi nào phân biệt nổi. Thực ra D(n) luôn bằng n!/e làm tròn tới số nguyên gần nhất, một sự thật đẹp có thể kiểm bằng tay với các dòng trong bảng: 720 / 2,71828 ≈ 264,87, làm tròn được 265.
Vì sao lại là số e
Dùng phép bao hàm – loại trừ, xác suất không lá nào đúng chỗ bằng 1 − 1/1! + 1/2! − 1/3! + … ± 1/n!. Đây chính là n số hạng đầu của chuỗi khai triển e^−1. Các số hạng giảm rất nhanh vì giai thừa ở mẫu tăng rất nhanh, nên chỉ vài số hạng đầu đã gần như đủ. Đó là lý do bộ 6 lá và bộ 52 lá cho cùng một đáp số.
Trung bình có đúng một cặp trùng
Một kết quả còn gọn hơn: số cặp trùng trung bình luôn bằng đúng 1, với mọi n. Lý do chỉ cần một dòng: mỗi lá có xác suất 1/n nằm đúng chỗ, có n lá, cộng lại được n × 1/n = 1. Phép cộng kỳ vọng này đúng cả khi các sự kiện phụ thuộc nhau.
Phân phối số cặp trùng với bộ 52 lá gần như trùng khít phân phối Poisson với trung bình 1:
| Số cặp trùng | Xác suất (bộ 52 lá) |
|---|---|
| 0 | 36,79% |
| 1 | 36,79% |
| 2 | 18,39% |
| 3 | 6,13% |
| 4 | 1,53% |
| 5 trở lên | khoảng 0,37% |
Để ý hai dòng đầu bằng nhau: "không có cặp trùng nào" và "đúng một cặp trùng" có khả năng y hệt nhau. Lá trùng không hiếm như nhiều người nghĩ. Khoảng 2 trên 3 lần thử sẽ có ít nhất một cặp trùng.
Ứng dụng: rút thăm tặng quà và kiểm tra xáo bài
Rút thăm tặng quà
Một nhóm bạn viết tên vào giấy, mỗi người rút một tờ để tặng quà bí mật. Luật là không ai được rút trúng tên mình. Xác suất một lần rút ngẫu nhiên "trót lọt" là khoảng 37%, gần như không phụ thuộc số người. Tức trung bình phải rút lại chừng 2,7 lần mới được một lượt hợp lệ. Biết trước con số này thì không ai sốt ruột khi phải rút lại vài lần.
Một phép thử xáo bài đơn giản
Muốn biết mình xáo đã đủ kỹ chưa, xếp một bộ bài theo thứ tự, xáo, rồi đặt cạnh một bộ thứ hai cũng xếp theo đúng thứ tự đó và lật từng cặp. Ghi số cặp trùng. Lặp lại nhiều lần: nếu xáo tốt, trung bình phải gần 1, và khoảng 37% số lần không có cặp trùng nào. Nếu bạn xáo quá ít, các lá đầu và cuối bộ bài hay giữ chỗ cũ, số cặp trùng sẽ cao bất thường. Phép thử này thô, nhưng bắt được những lần xáo qua loa nhất.
Góc nhìn hôm nay: thí nghiệm hai bộ bài
- Lấy hai bộ bài, xếp một bộ theo thứ tự cố định, xáo bộ còn lại thật kỹ.
- Lật đồng thời từng cặp, đếm số lần hai lá giống hệt nhau cả chất lẫn hạng.
- Lặp lại 20 lần, ghi số cặp trùng mỗi lần.
- So với bảng: trung bình gần 1, khoảng 7 lần không trùng, 7 lần trùng một cặp, 4 lần trùng hai cặp.
Không có hai bộ bài thì dùng một bộ và đọc to "Át cơ, hai cơ… K cơ, Át rô…" theo đúng thứ tự xếp sẵn khi lật bộ đã xáo. Bài toán Montmort là một trong những ví dụ đầu tiên của tổ hợp được kể trong hầu hết giáo trình xác suất nhập môn; muốn đi sâu hơn có thể tìm đọc phần về phép bao hàm – loại trừ và phân phối Poisson.
Câu hỏi thường gặp
Bài toán Montmort là gì?
Là bài toán xác suất về số lần trùng khớp khi so một hoán vị ngẫu nhiên với thứ tự ban đầu, chẳng hạn lật song song hai bộ bài. Pierre Rémond de Montmort đưa nó vào sách năm 1708, nên còn gọi là bài toán Montmort hay problème des rencontres.
Xáo hai bộ bài, xác suất không có lá nào trùng chỗ là bao nhiêu?
Khoảng 36,79%, gần như chính xác bằng 1/e. Xác suất có ít nhất một cặp trùng vì vậy là khoảng 63,2%.
Derangement (xáo lệch hoàn toàn) là gì?
Là cách xếp lại n phần tử sao cho không phần tử nào ở đúng vị trí ban đầu. Số cách xếp như vậy bằng n!/e làm tròn tới số nguyên gần nhất, ví dụ với 4 phần tử là 9 cách.
Vì sao số cặp trùng trung bình luôn bằng 1?
Mỗi lá có xác suất 1/n nằm đúng chỗ, có n lá, nên tổng kỳ vọng là n × 1/n = 1. Phép cộng kỳ vọng đúng cả khi các sự kiện phụ thuộc nhau, nên không cần tính phân phối đầy đủ.
Rút thăm tặng quà thì bao nhiêu phần trăm không ai trúng tên mình?
Khoảng 37% nếu rút hoàn toàn ngẫu nhiên, gần như không đổi theo số người tham gia. Trung bình phải rút khoảng 2,7 lần mới có một lượt mà không ai trúng tên chính mình.
