Bước tới nội dung

Bài toán ngày sinh

Bách khoa toàn thư mở Wikipedia

Trong lý thuyết xác suất, bài toán ngày sinh hay nghịch lý ngày sinh[1] nói đến xác suất để trong một nhóm người được chọn ngẫu nhiên, có hai người có cùng ngày sinh. Theo nguyên lý chuồng bồ câu, xác suất đạt 100% khi số người đạt 367 (vì có 366 ngày sinh khả dĩ, kể cả ngày 29 tháng 2). Tuy nhiên, xác suất 99.9% đạt được chỉ với 70 người và 50% với 23 người. Kết luận này chứa giả sử rằng mỗi ngày trong năm (trừ ngày 29 tháng hai) có xác suất ngang nhau. Lịch sử của bài toán này không rõ ràng. W. W. Rouse Ball nói rằng (không có trích dẫn) nó được bàn đến đầu tiên bởi Harold Davenport.[2] Tuy nhiên Richard von Mises nêu lên một phiên bản sớm hơn của cái ngày nay được gọi là bài toán ngày sinh.[3]

Nguyên lý toán học đằng sau bài toán này dẫn đến một kỹ thuật tấn công mật mã nổi tiếng gọi là birthday attack, sử dụng mô hình xác suất này để giảm độ phức tạp của việc phá hàm băm.

Đồ thị biểu hiện xác suất tính được để ít nhất hai người có chung một ngày sinh trong một số người nhất định.


Tham khảo

[sửa | sửa mã nguồn]
  1. ^ Đây không phải một nghịch lý theo nghĩa dẫn đến mâu thuẫn lô-gic mà nó được gọi là nghịch lý vì sự thật toán học trái ngược với trực giác ngây thơ: trực giác đoán rằng khả năng hai người có cùng sinh nhật trong một nhóm người nhỏ hơn 50% nhiều trong khi bài toán cho thấy không phải vậy.
  2. ^ W. W. Rouse Ball, 1960, Other Questions on Probability, in Mathematical Recreations and Essays, Macmillan', New York, p 45.
  3. ^ “The Birthday Problem”. Bản gốc lưu trữ ngày 6 tháng 11 năm 2014. Truy cập ngày 6 tháng 11 năm 2014.