Nếu bạn từng sưu tập những hình dán kèm trong gói bánh kẹo, có lẽ bạn còn nhớ cảm giác lúc đầu: gần như mỗi lần xé gói lại có hình dán mới, tưởng như sắp gom đủ đến nơi. Thế nhưng khi album gần đầy, bạn cứ nhận được những hình đã có, còn một hai tấm cuối cùng thì mãi chẳng thấy đâu. Đó không phải do xui xẻo mà vì xác suất vốn vận hành như vậy. Lời giải thích toán học cho hiện tượng này chính là “Bài toán người sưu tập phiếu (Coupon Collector’s Problem)”.
Nói đơn giản, bài toán người sưu tập phiếu là một bài toán xác suất đặt câu hỏi: “Khi một trong nhiều loại xuất hiện ngẫu nhiên, trung bình phải rút bao nhiêu lần mới gom đủ mọi loại, mỗi loại ít nhất một lần?” Điểm mấu chốt là đáp án lớn hơn nhiều so với tưởng tượng, và phần lớn số lần rút ấy dành cho việc chờ đợi vài loại cuối cùng.
Trong bài viết này, chúng ta sẽ lần lượt tìm hiểu bài toán người sưu tập phiếu là gì, nguyên lý tính số lần trung bình, các ví dụ cụ thể bằng con số, cũng như những nơi bài toán này được dùng trong đời sống, công nghệ và những điểm cần lưu ý.
Tấm cuối cùng là tấm đắt nhất: Bài toán người sưu tập phiếu
Bài toán người sưu tập phiếu là gì
Tên gọi của bài toán bắt nguồn từ các chương trình khuyến mãi bỏ một phiếu vào mỗi hộp ngũ cốc và tặng quà cho ai gom đủ mọi loại. Về mặt toán học, bài toán đặt ra các điều kiện sau.
(1) Số loại là cố định
Có tổng cộng n loại phiếu cần sưu tập, và người sưu tập biết trước con số này.
(2) Mỗi lần xuất hiện ngẫu nhiên một tấm
Mỗi khi mua một hộp, một trong n loại sẽ xuất hiện với xác suất như nhau, và những gì đã ra trước đó không ảnh hưởng đến kết quả tiếp theo.
(3) Có sự trùng lặp
Phiếu đã có vẫn có thể xuất hiện lại. Việc nhận cùng một phiếu nhiều lần chính là nguyên nhân khiến quá trình sưu tập kéo dài.
Nói theo cách của xúc xắc, đây cũng chính là câu hỏi: “Trung bình phải tung xúc xắc bao nhiêu lần thì cả sáu mặt mới xuất hiện ít nhất một lần?”
Số lần trung bình được tính như thế nào
Việc tính toán sẽ dễ hơn nếu chia quá trình sưu tập thành các giai đoạn, mỗi giai đoạn kéo dài “cho đến khi có thêm một loại mới”.
(1) Lúc đầu, thứ gì cũng mới
Khi chưa có gì, lần rút đầu tiên chắc chắn là loại mới, nên chỉ cần một lần.
(2) Càng sưu tập nhiều, xác suất ra loại mới càng giảm
Nếu đã có k loại, xác suất ra loại mới là (n – k) / n. Lặp lại một việc có xác suất thành công p cho đến khi thành công thì trung bình mất 1 / p lần, nên giai đoạn này cần trung bình n / (n – k) lần.
(3) Cộng tất cả các giai đoạn lại
Cộng trung bình của từng giai đoạn, ta được trung bình tổng là n × (1 + 1/2 + 1/3 + … + 1/n). Tổng trong ngoặc được gọi là số điều hòa, và khi n lớn lên, tổng số lần tăng xấp xỉ theo n × (logarit tự nhiên của n) + 0.577 × n. Nhà toán học người Pháp Pierre-Simon Laplace cũng đã đề cập đến bài toán này trong tác phẩm về lý thuyết xác suất năm 1812 của ông.
Tính thử với xúc xắc sẽ dễ hiểu hơn. Trung bình, mặt đầu tiên cần 1 lần, mặt mới thứ hai cần 6/5 lần, mặt thứ ba 6/4 lần, mặt thứ tư 6/3 lần, mặt thứ năm 6/2 lần và mặt thứ sáu cuối cùng 6/1 lần. Cộng tất cả lại được khoảng 14.7 lần, trong đó riêng việc chờ mặt cuối cùng đã chiếm trung bình 6 lần.
Như công thức cho thấy, ở giai đoạn cuối, tức khi chỉ còn đúng một loại, riêng loại đó đã cần chờ trung bình n lần. Càng có nhiều loại thì càng khó gặp loại mới, và chính cấu trúc này khiến thời gian sưu tập bị kéo dài.
Thực tế của việc sưu tập qua những con số
Khi nhìn kết quả tính toán bằng những con số cụ thể, ta sẽ thấy rõ nó khác trực giác đến mức nào.
- Xúc xắc (Die): Như đã tính ở trên, để thấy đủ sáu mặt cần tung trung bình khoảng 14.7 lần. Tưởng chừng sáu lần là đủ, nhưng thực tế gấp hơn hai lần.
- 10 loại phiếu (Ten Coupons): Cần trung bình khoảng 29.3 lần.
- 50 loại phiếu (Fifty Coupons): Cần trung bình khoảng 225 lần. Trong đó, gom 25 loại đầu tiên chỉ mất khoảng 34 lần, nhưng gom 25 loại còn lại mất khoảng 191 lần.
- 100 loại phiếu (One Hundred Coupons): Trung bình khoảng 519 lần, gấp hơn năm lần số loại.
Những con số này chỉ là trung bình, nên trên thực tế có nhiều người mất lâu hơn rất nhiều. Ngoài ra, nếu có “thẻ hiếm” mà một số loại được cố tình đưa vào với số lượng ít, thì số lần kỳ vọng sẽ còn lớn hơn so với khi mọi loại có xác suất như nhau.
Ứng dụng của bài toán người sưu tập phiếu và những điểm cần lưu ý
Bài toán này được dùng trong nhiều lĩnh vực, không chỉ dừng lại ở album hình dán.
(1) Khuyến mãi và thiết kế tiêu dùng
Các sản phẩm sưu tập xuất hiện ngẫu nhiên có cấu trúc khiến người mua phải mua đi mua lại cùng một sản phẩm để có được vài loại cuối cùng. Về phía người tiêu dùng, chỉ cần tính trước chi phí kỳ vọng cũng đủ giúp giảm mua sắm bốc đồng.
(2) Khoa học máy tính và thuật toán
Phép tính này được dùng khi ước lượng thời gian để các phần tử được chọn ngẫu nhiên đi qua mọi trường hợp ít nhất một lần, và là ví dụ tiêu biểu trong các giáo trình về thuật toán ngẫu nhiên.
(3) Trao đổi có thể là lời giải
Khi nhiều người cùng sưu tập và đổi cho nhau những món trùng, số lượng mỗi người phải mua giảm mạnh so với khi sưu tập một mình. Bởi món trùng dư ra của mình có thể chính là tấm mà người khác đang cần.
(4) Thước đo để ước lượng số lần còn lại
Nếu đã sưu tập được nhiều loại, chỉ cần áp dụng cách tính tương tự cho những loại còn lại. Ví dụ, nếu đã có 49 trong 50 loại, nghĩa là trung bình cần rút thêm 50 lần nữa mới có được tấm cuối cùng.
Tuy nhiên, các sản phẩm thực tế thường có tỉ lệ xuất hiện khác nhau giữa các loại hoặc không công bố tỉ lệ, nên phép tính chỉ nên được xem là điểm khởi đầu.
Bài toán người sưu tập phiếu cho thấy một sự thật đơn giản—càng sưu tập nhiều thì càng khó có thêm món mới—tạo ra khác biệt lớn đến nhường nào. Tấm cuối cùng mãi không xuất hiện không phải vì xui xẻo, mà là con đường xác suất đã định sẵn.
Trước khi bắt đầu sưu tập, hãy thử tính xem mình có thể cần bao nhiêu lần, và tìm những người bạn để chia sẻ món trùng—đó chính là bước đầu tiên của việc sưu tập một cách khôn ngoan.
