Bài toán sưu tầm đủ bộ (coupon collector): cần mở bao nhiêu thẻ

Bài toán sưu tầm đủ bộ (coupon collector) hỏi: một bộ có n lá khác nhau, mỗi lần nhận một lá ngẫu nhiên đều nhau, trung bình phải nhận bao nhiêu lá mới đủ cả bộ? Đáp số là n × H(n), trong đó H(n) = 1 + 1/2 + 1/3 + … + 1/n. Với bộ 50 lá, con số là khoảng 225 lá, gấp 4,5 lần số lá trong bộ, và phần lớn số đó dành cho vài lá cuối cùng.

Ai cũng từng gặp bài toán này

Gom đủ bộ thẻ cầu thủ trong gói bánh, đủ bộ nhân vật trong hộp quà, đủ bộ hình dán của một cuốn album: ai sưu tầm cũng thấy chung một cảm giác. Mấy chục lá đầu đến rất nhanh, gần như lá nào mở ra cũng mới. Rồi tới một lúc, mở mười gói chỉ thêm được một lá, còn lại toàn trùng. Lá cuối cùng thì như không bao giờ tới.

Cảm giác đó không phải do nhà sản xuất "giấu" lá hiếm. Ngay cả khi mọi lá có tỉ lệ ngang nhau tuyệt đối, toán học vẫn cho ra đúng hình dạng ấy.

Lời giải từng bước

Chia cuộc sưu tầm thành từng chặng. Chặng thứ nhất: chưa có lá nào, lá đầu tiên chắc chắn mới, tốn 1 lần. Chặng thứ hai: đã có 1 lá, xác suất lá tiếp theo là lá mới bằng (n − 1)/n. Một việc có xác suất thành công p mỗi lần thì trung bình cần 1/p lần, nên chặng này tốn trung bình n/(n − 1) lần. Chặng thứ ba tốn n/(n − 2). Cứ thế, chặng cuối cùng, khi chỉ còn thiếu một lá, xác suất mỗi lần là 1/n nên tốn trung bình n lần.

Cộng hết lại: n/n + n/(n − 1) + … + n/1 = n × (1 + 1/2 + … + 1/n) = n × H(n). Số H(n) gọi là số điều hoà thứ n, tăng rất chậm, xấp xỉ ln n + 0,577.

Ví dụ tính tay: tung xúc xắc đủ sáu mặt

Một con xúc xắc sáu mặt là "bộ sưu tầm" sáu lá. Số lần tung trung bình để thấy đủ sáu mặt là 6 × (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) = 6 × 2,45 = 14,7 lần. Từng chặng: mặt đầu tốn 1 lần, mặt thứ hai 6/5 = 1,2, thứ ba 1,5, thứ tư 2, thứ năm 3, và mặt cuối cùng tốn trung bình tới 6 lần, gần bằng một nửa toàn bộ thời gian. Lấy xúc xắc ra tung thử vài lượt, bạn sẽ thấy số mười mấy lần là rất quen.

Bảng số cho các cỡ bộ sưu tầm

Cột cuối là H(n): bộ càng lớn thì càng phải nhận nhiều lần cỡ bộ. Album 640 hình cần trung bình hơn 4 500 hình nếu chỉ dựa vào mở gói, mà không trao đổi với ai.

Nửa đầu nhanh, nửa sau chậm

Với bộ 50 lá, hãy tách tổng 225 lần thành hai phần:

• 25 lá đầu tiên: chỉ tốn trung bình khoảng 34 lần nhận.
• 25 lá còn lại: tốn khoảng 191 lần.
• Riêng 5 lá cuối: khoảng 114 lần, tức hơn một nửa toàn bộ công sức.
• Riêng lá cuối cùng: trung bình 50 lần, bằng cả cỡ bộ.

Đây là lý do lời khuyên quen thuộc của dân sưu tầm, "đến cuối thì đổi hoặc mua lẻ chứ đừng mở gói", có cơ sở toán học vững chắc.

Biến động: con số 225 chỉ là trung bình

Thời gian sưu tầm dao động rất mạnh. Với bộ 50 lá, độ lệch chuẩn là khoảng 62 lần. Dùng phép bao hàm – loại trừ, có thể tính xác suất đã đủ bộ sau k lần nhận:

Để ý rằng ở đúng mức trung bình 225, mới có 58% số người đã đủ bộ. Như nhiều đại lượng có "đuôi dài", trung bình bị những lần xui kéo lên cao hơn trung vị. Muốn chắc 9 phần 10, phải chuẩn bị tinh thần cho khoảng 300 lá.

Gói nhiều lá, trao đổi và lá hiếm

Gói có sẵn nhiều lá khác nhau

Thẻ thường bán theo gói, mỗi gói vài lá không trùng nhau trong cùng gói. Điều này giúp một chút, nhưng không nhiều. Mô phỏng với bộ 50 lá, gói 5 lá khác nhau: trung bình cần khoảng 43,7 gói, tức chừng 218 lá, so với 225 nếu nhận từng lá. Lợi được khoảng 3%. Lý do là trùng lặp chủ yếu xảy ra giữa các gói, không phải trong một gói.

Hai người cùng sưu tầm

Nếu hai người cùng gom chung rồi chia, bài toán thành "sưu tầm đủ hai bộ". Donald Newman và Lawrence Shepp phân tích bài toán này năm 1960 trong bài báo có tên "The Double Dixie Cup Problem". Kết quả là bộ thứ hai rẻ hơn bộ thứ nhất rất nhiều. Tính số với bộ 50 lá: một bộ cần trung bình 225 lá, hai bộ cần khoảng 325 lá, ba bộ khoảng 412 lá. Tức là bộ thứ hai chỉ tốn thêm khoảng 100 lá chứ không phải 225. Lá trùng của người này là lá thiếu của người kia. Đổi thẻ cho nhau vì vậy là cách hiệu quả nhất để rút ngắn đường.

Khi lá không ngang nhau

Mọi con số trên đều giả định các lá có tỉ lệ bằng nhau. Nếu có một lá hiếm, chẳng hạn chỉ chiếm 1 phần 500 số lá phát ra, thì riêng lá đó đã cần trung bình 500 lần nhận, lớn hơn hẳn phần còn lại. Khi đó tổng thời gian gần như do lá hiếm nhất quyết định. Đây là lý do sưu tầm những bộ có độ hiếm khác nhau rất khó đoán trước, và là lý do nên tìm hiểu tỉ lệ công bố của nhà sản xuất (nếu có) trước khi bắt đầu.

Góc nhìn hôm nay: ứng dụng ngoài bộ sưu tầm

Bài toán sưu tầm xuất hiện ở nhiều nơi không liên quan tới thẻ:

• Trong ứng dụng xây bộ bài, khi mỗi lượt được thưởng một lá ngẫu nhiên từ danh sách 50 lá, người chơi trung bình phải qua khoảng 225 lần thưởng mới thấy đủ, nếu không có cơ chế chống trùng. Nhiều nhà thiết kế vì thế ưu tiên lá chưa có.
• Kiểm thử phần mềm ngẫu nhiên: muốn chắc mọi nhánh trong 100 nhánh được chạy ít nhất một lần bằng đầu vào ngẫu nhiên đều, cần cỡ 519 lần chạy.
• Sinh học: ước lượng phải giải trình tự bao nhiêu đoạn để phủ đủ một bộ gen dùng cùng một họ lập luận.

Thí nghiệm dễ làm cùng trẻ: tung xúc xắc tới khi đủ sáu mặt, ghi số lần, lặp lại 10 lượt rồi tính trung bình, so với 14,7. Muốn đọc thêm, bài toán có trong hầu hết giáo trình xác suất nhập môn ở phần kỳ vọng và biến ngẫu nhiên hình học.