Mô phỏng nghịch lý ngày sinh nhật | Vì sao 23 người đã đủ cho 50%

Cách nó hoạt động

Bấm vào sân khấu để tạo một nhóm mới gồm 23 người. Họ lần lượt tham gia từng người một, và mỗi cặp mới lại có thêm một đường nối.
Hãy nhìn tấm lịch: ngày có hai người cùng sinh nhật sẽ sáng lên, và dòng thông báo cho biết ngày sinh nhật trùng nhau đó.
Nhấn Tự động thử để thử 1.000 nhóm, hoặc Thử mọi quy mô nhóm để xem xác suất tăng lên từ 2 đến 100 người.

Vì sao trực giác của ta sai

Trong một căn phòng, ta vô thức lập luận từ chính mình: xác suất có người trùng sinh nhật với tôi là bao nhiêu? Với 365 ngày, xác suất đó nhỏ, khoảng 6% khi có 22 người khác. Nhưng nghịch lý này hỏi liệu có hai người nào đó trùng sinh nhật hay không: A và B, B và C, A và C, v.v. Hai mươi ba người tạo thành 23 × 22 / 2 = 253 cặp, và mỗi cặp là một cơ hội trùng nhau. Số cặp tăng theo bình phương số người trong nhóm, nên xác suất tăng vọt.

Phép tính

Cách dễ nhất là tính xác suất không ai trùng sinh nhật, rồi lấy 100% trừ đi. Người thứ nhất lấy ngày nào cũng được. Người thứ hai có xác suất 364/365 rơi vào một ngày khác, người thứ ba có xác suất 363/365 tránh được hai người đầu, cứ thế tiếp tục. Với 23 người: 365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49,3%. Khi đó xác suất có ít nhất một lần trùng sinh nhật là 100% − 49,3% = 50,7%.

Người trùng sinh nhật với bạn

Xác suất có người trong nhóm trùng sinh nhật với chính bạn tăng chậm hơn nhiều: 1 − (364/365)ⁿ⁻¹, vì chỉ có n − 1 cặp có bạn. Với 23 người, xác suất này là 5,9%, và bạn cần 253 người khác để vượt qua 50%. Hãy chuyển câu hỏi sang Có người trùng sinh nhật với bạn để so sánh hai đường cong.

Tấn công ngày sinh nhật trong mật mã học

Nghịch lý này không chỉ là một trò vui trong bữa tiệc. Trong bảo mật máy tính, nó là cơ sở của tấn công ngày sinh nhật: để tìm hai đầu vào có cùng giá trị băm, tức một va chạm, kẻ tấn công cần ít lần thử hơn nhiều so với bạn nghĩ. Với một hàm băm có N giá trị khả dĩ, va chạm trở nên nhiều khả năng xảy ra sau khoảng √N lần thử chứ không phải N. Đó là lý do hàm băm và chữ ký số cần đầu ra đủ dài để ngay cả √N lần thử cũng nằm ngoài tầm với: với hàm băm 128 bit, tìm một va chạm cần khoảng 2⁶⁴ lần thử.

Hỏi thường xuyên

Cần bao nhiêu người để có 50% cơ hội trùng sinh nhật?

23. Khi đó xác suất là 50,7%. Với 30 người là 70,6%, với 41 người là 90,3%, với 57 người là 99,0%, và với 70 người là 99,9%.

Vì sao lại gọi là nghịch lý?

Nó không phải là một mâu thuẫn, chỉ là một điều bất ngờ: đáp án đi ngược trực giác. Phần lớn mọi người đoán rằng cần khoảng một nửa của 365, tức khoảng 180 người, vì họ so sánh mọi người với chính mình thay vì với nhau.

Còn ngày 29 tháng 2 và ngày sinh thực tế thì sao?

Giống như bài toán kinh điển, ứng dụng coi 365 ngày là đồng khả năng. Ngày sinh nhật thực tế không phân bố thật đều trong năm, và sự phân bố không đều khiến khả năng trùng sinh nhật cao hơn một chút, chứ không thấp hơn.

Khi nào chắc chắn có người trùng sinh nhật?

Khi có 366 người: chỉ có 365 ngày, nên theo nguyên lý Dirichlet (nguyên lý chuồng bồ câu), trong 366 người phải có ít nhất hai người trùng một ngày. Từ rất lâu trước đó, điều này đã gần như chắc chắn: với 100 người, xác suất là 99,99997%.

Có tải gì lên không?

Không. Mọi thứ được tính toán và vẽ trên canvas trong trình duyệt. Lưu sẽ tải xuống một PNG. Chỉnh sửa mở ảnh đó trong trình chỉnh sửa PictorX.