Nghịch lý ngày sinh nhật

Nghịch lý

Hãy hỏi mọi người một bữa tiệc cần bao nhiêu khách để nhiều khả năng có hai người trùng sinh nhật, phần lớn sẽ trả lời khoảng 180, một nửa của 365. Đáp án thật là 23: khi đó xác suất là 50,7%. Với 57 khách, xác suất là 99%. Nó được gọi là nghịch lý không phải vì nó mâu thuẫn, mà vì nó đi ngược trực giác của chúng ta mạnh đến vậy.

Vì sao trực giác 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ỏ. Nhưng nghịch lý này nói về mọi cặp có thể có trong phòng, không phải về việc trùng với một người cụ thể: A và B, B và C, A và C, v.v. Với 23 người, bạn có thể tạo ra 253 cặp khác nhau, và cặp nào cũng có thể trùng sinh nhật.

Số cặp tăng theo bình phương

n người tạo thành n × (n − 1) / 2 cặp: 10 người tạo thành 45 cặp, 23 người 253 cặp, 57 người 1.596 cặp và 100 người 4.950 cặp. Mỗi cặp trùng sinh nhật với xác suất 1/365, nên 253 cặp cho trung bình 253/365 ≈ 0,69 cặp trùng nhau. Nhóm đông gấp đôi thì số cặp tăng khoảng gấp bốn, và đó là lý do xác suất trùng sinh nhật tăng vọt.

Phép tính từng bước

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 chiếm một ngày bất kỳ. Người thứ hai có xác suất 364/365 không trùng sinh nhật với người đó. Người thứ ba có xác suất 363/365 khác với 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%

Vì xác suất mọi người đều có sinh nhật khác nhau là 49,3%, biến cố đối của nó, có ít nhất một lần trùng sinh nhật, có xác suất 100% − 49,3% = 50,7%.

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

Xác suất có người trùng sinh nhật với chính bạn là một câu hỏi khác. Mỗi người trong n − 1 người còn lại tránh ngày sinh nhật của bạn với xác suất 364/365, nên xác suất có người trùng với bạn là 1 − (364/365)ⁿ⁻¹. Với 23 người, con số này chỉ là 5,9%, và bạn cần 253 người khác thì nó mới vượt quá 50%. Trong 253 cặp của một nhóm 23 người, chỉ có 22 cặp có bạn.

Quy tắc căn bậc hai và tấn công ngày sinh nhật

Với N giá trị đồng khả năng, một sự lặp lại trở nên nhiều khả năng xảy ra sau khoảng 1,2 × √N lần rút: √365 ≈ 19, và 1,2 × 19 ≈ 23. Điều này rất quan trọng trong bảo mật máy tính. Kẻ tấn công dùng tấn công ngày sinh nhật để tìm hai đầu vào có cùng giá trị băm mật mã, tức một va chạm, chẳng hạn để giả mạo chữ ký số. Nhờ nghịch lý ngày sinh nhật, họ cần ít lần thử hơn nhiều so với trực giác: khoảng 2⁶⁴ lần cho một hàm băm 128 bit thay vì 2¹²⁸. Đó là lý do các hàm băm hiện đại như SHA-256 có đầu ra dài.

Khám phá trong PictorX

Mở nghịch lý ngày sinh nhật và một nhóm 23 người hình thành trên một vòng tròn, lần lượt từng người một. Mỗi người mới đến thêm một đường nối tới từng người đã có mặt, và dòng chú thích đếm số cặp. Ngày sinh nhật của họ rơi xuống tấm lịch, và ngày có từ hai người trở lên sẽ sáng lên. Bên dưới, phép tính cho quy mô nhóm đó nằm cạnh tỉ lệ các nhóm đã thử có người trùng sinh nhật, và biểu đồ cho thấy xác suất với mọi quy mô nhóm, cho trường hợp có hai người trùng nhau và trường hợp có người trùng sinh nhật với bạn. Thêm từng người một, chọn từ 2 đến 366 người, thử tới 100.000 nhóm với tốc độ tới 10.000 nhóm mỗi giây, hoặc thử mọi quy mô nhóm và xem các chấm vẽ nên đường cong.