Liệu Có Thể Rút Trúng Mảnh Giấy Của Chính Mình Không?

Vào một ngày cuối tuần, tôi trò chuyện với một người bạn đang chuẩn bị đi nhận việc tại Alibaba. Cậu ấy kể rằng trong khóa đào tạo nhân viên mới có một trò chơi rất thú vị. Mỗi học viên phải viết một điều ước nhỏ trong thời gian tới lên một mảnh giấy, sau đó bỏ vào hộp phiếu. Khi mọi người đã nộp xong, mỗi người sẽ rút ngẫu nhiên một mảnh giấy bất kỳ. Người rút trúng điều ước của ai thì phải âm thầm giúp người đó thực hiện điều ước đó, mà không được tiết lộ danh tính.

Đột nhiên tôi nảy ra một ý nghĩ: Nếu ai đó rút trúng điều ước chính mình viết thì sao nhỉ? :D

Xác suất rút trúng mảnh giấy của bản thân là 1/n (với n là số người tham gia), con số này không phụ thuộc vào việc bạn rút trước hay rút sau. Khi số người càng lớn, xác suất này ngày càng nhỏ, nhưng trong toàn bộ tập thể, xác suất có ít nhất một người rút trúng điều ước của chính mình lại không hề nhỏ chút nào. Cụ thể là bao nhiêu nhỉ? Tôi bèn thử tính toán một cách say sưa.

Đơn giản hóa bài toán, ta cần tìm xác suất để trong một hoán vị của các số tự nhiên từ 1 đến n, tồn tại ít nhất một số i đứng đúng vị trí thứ i của nó.

Tổng số hoán vị của n số là n! Ta chỉ cần tính số lượng các hoán vị mà không có số nào đứng đúng vị trí của mình.

Đặt f(n) là số cách xếp n-1 số vào n vị trí sao cho không có số nào đúng vị trí của nó. Ví dụ f(2)=1 (chỉ có thể xếp số 1 vào vị trí thứ hai), f(3)=3 (các trường hợp như 2 1 _, 3 _ 1, _ 3 2…)

Tiếp theo định nghĩa g(n) là số hoán vị của n số mà tất cả đều không đứng đúng vị trí. Ta có công thức truy hồi g(n+1) = n × f(n). Ví dụ g(3)=2×f(2)=2×1=2.

Phát triển thêm, ta có f(n+1) = g(n) + n×f(n). Đây là vì khi xếp n số vào n+1 vị trí, có hai trường hợp xảy ra: hoặc để trống một vị trí và xếp n số không đúng vị trí (g(n) cách), hoặc chọn một số đặt vào vị trí thừa rồi xếp n-1 số còn lại vào n vị trí (n×f(n) cách).

Kết hợp hai công thức trên, ta có g(n+1) = n×(g(n) + g(n-1)). Từ đây dễ dàng lập trình tính được các giá trị tiếp theo.

Gọi h(n) = g(n)/n! là xác suất cần tìm. Khi tính toán 100 giá trị đầu tiên, tôi phát hiện ra từ n=8 trở đi, xác suất này ổn định ở khoảng 0.3679. Điều này khiến tôi tò mò và tiếp tục phân tích công thức.

Biến đổi đại số, tôi tìm được biểu thức: h(n) = 1 - 1/1! + 1/2! - 1/3! + … + (-1)^n/n!

Đây chính là khai triển Maclaurin của 1/e! Khi n tăng lên, h(n) tiến rất nhanh về 1/e ≈ 0.367879. Điều này có nghĩa là:

• Khi n > 5, xác suất không ai rút trúng mảnh giấy của mình là khoảng 36.8%
• Ngược lại, xác suất có ít nhất một người rút trúng điều ước của chính mình lên đến 63.2%

Thật kỳ diệu làm sao! Dù số người nhiều hay ít, xác suất này hầu như không thay đổi. Không ngờ lại một lần nữa gặp lại số Euler e - điều này khiến tôi càng thêm say mê vẻ đẹp toán học. :D