Bài Toán Xác Suất Không Đơn Giản

Trong văn phòng chúng tôi có 4 hộp bài tây, trước đây dùng để chơi một trò chơi bài cần 8 người, sử dụng tới 4 bộ bài. Sau mỗi ván chơi, mọi người thường gom chung các lá bài lại rồi chia đều vào 4 hộp. Gần đây phong trào chơi bridge (bài úp) nổi lên, trò này chỉ cần 1 bộ chuẩn 52 lá, vì vậy tôi quyết định tách riêng một bộ hoàn chỉnh ra. Trong lúc đang lười biếng không muốn đổ hết bài từ cả 4 hộp ra, tôi chợt nảy ra một câu hỏi thú vị:

Giả sử các lá bài đã được xáo trộn hoàn toàn và phân bố ngẫu nhiên đều vào 4 hộp (mỗi hộp đúng 54 lá), thì cần mở ít nhất bao nhiêu hộp để có xác suất trên 90% tìm được đủ một bộ bài hoàn chỉnh?

Lúc đó một người bạn cùng dọn bài phán chắc nịch: “Chắc chỉ cần mở 2 hộp là đủ rồi!” Trực giác mách bảo tôi rằng 2 hộp là quá ít, có lẽ phải cần tới 3 hộp mới tạm ổn. Nhưng thực tế lại khiến cả hai bất ngờ: từ 3 hộp bài đầu tiên, chúng tôi chỉ tìm được 53 lá độc nhất, lá thứ 54 phải đến hộp thứ 4 mới thấy!

Cảm thấy bài toán này vừa hay vừa không dễ như tưởng tượng, tôi liền lấy giấy bút thử phân tích. Sau một hồi mày mò, tôi đưa ra công thức ước lượng xác suất tìm được bộ bài hoàn chỉnh khi mở m hộp trong tổng số n hộp như sau:

$$ \left(1 - \left( \frac{n-m}{n} \right)^{n \right)}{54} $$

Thay m=2, n=4 vào tính được xác suất chỉ khoảng 3%, còn khi m=3 thì xác suất nhảy vọt lên 81%. Tuy nhiên hôm nay (1/5), khi suy nghĩ lại kỹ hơn, tôi nhận ra bài toán không đơn giản như vậy (như một người bạn tên ZF đã bình luận). Vì trình độ toán học có hạn, tôi quyết định dùng đến vũ khí lợi hại là ngôn ngữ C để lập trình tính toán:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include "stdio.h"
#define CARD 54
#define N 4
#define M 3
static int assemble_table[N+1];
static double probability_table[CARD*N][CARD*N];
void init_probability_table()
{
  int i,j;
  for (i=0;i<N+1;i++) assemble_table[i] = 0;
}
double draw_ncard(int total, int part, int n)
{
  if (total < part) return 0;
  if (n == 0) return 0;
  if (n > total) return 0;
  double p = 1.0;
  for (int i=0; i < n; i++) {
    p *= (double)(total - part - i)/(total - i);
  }
  return p;
}
double probability(int total, int part)
{
  double p = 0.0;
  if (total <= 0) return 0;
  if (part <= 0) return 0;
  if (total == part) return 1.0;
  if (probability_table[total-1][part-1] != 0.0) {
    return probability_table[total-1][part-1];
  }
  if (part == N && total == N) {
    return 1.0;
  }
  p += draw_ncard(total, part, N);
  for (int i = N-1; i >= 0; i--) {
    double t = draw_ncard(total, part, i);
    if (t != 0.0) {
      t *= probability(total - N, part - i);
      p += t;
    }
  }
  probability_table[total-1][part-1] = p;
  return p;
}
double calc()
{
  int total = N * CARD;
  int part = (N - M) * CARD;
  double p = probability(total, part);
  return 1 - p;
}
int main()
{
  init_assemble_table();
  init_probability_table();
  printf("%lf\n", calc());
  return 0;
}

Dù đoạn code trên viết khá thô sơ, nhưng kết quả thu được rất đáng tin cậy: Khi thay N=4, M=2 xác suất chỉ là 0.019088 (khoảng 1.9%), còn khi M=3 thì xác suất đạt 0.820296 (82%). Điều thú vị là kết quả từ công thức sai ban đầu không lệch quá xa, có lẽ vì số lượng lá bài (54) lớn hơn nhiều so với số hộp chia bài.

Một bài toán mở rộng dễ tính nhẩm: Trong 4 lá bài gồm 2 lá K và 2 lá A, nếu rút ngẫu nhiên 2 lá, xác suất được một đôi là bao nhiêu? Tôi hỏi thử vài người, đa phần ban đầu đều trả lời vội là 50% (¬_¬) Nhưng chỉ cần suy nghĩ thêm 1 phút, mọi người sẽ tìm ra đáp án chính xác. Bạn đọc có muốn thử sức không?