Trong một căn phòng chỉ có 23 người, khả năng để ít nhất hai người có cùng ngày sinh nhật (ngày và tháng) là bao nhiêu? Nhiều người sẽ đoán con số này sẽ rất thấp. Tuy nhiên, câu trả lời thực tế lại vượt quá 50%. Nếu số người tăng lên 57, tỷ lệ này sẽ tăng lên tới hơn 99%.
Hiện tượng này được gọi là Nghịch lý Ngày sinh (Birthday Paradox). Nó không phải là một nghịch lý theo nghĩa mâu thuẫn tính toán, mà là một "nghịch lý thị giác" đối với giác quan thông thường: kết quả toán học hoàn toàn chính xác nhưng lại đi ngược lại suy đoán tự nhiên của con người.
Tại sao não bộ chúng ta bị "đánh lừa"?
Lý do chính khiến hầu hết mọi người ước tính sai là vì chúng ta thường cá nhân hóa bài toán.
Khi nghe câu hỏi, bạn thường tự hỏi: "Tỷ lệ để ai đó trong phòng có cùng ngày sinh với chính tôi là bao nhiêu?". Nếu chỉ so sánh ngày sinh của 22 người còn lại với bạn, xác suất đúng là rất thấp. Để có 50% cơ hội tìm thấy một người trùng ngày sinh với riêng bạn, căn phòng cần tới 253 người.
Tuy nhiên, Nghịch lý Ngày sinh không yêu cầu trùng với một người cụ thể. Câu hỏi ở đây là: Có hai người bất kỳ nào trong phòng trùng ngày sinh với nhau hay không?
Cách dễ nhất là tính xác suất của biến cố đối: xác suất để không ai trùng sinh nhật với ai.
Giả sử đơn giản hóa: 365 ngày, mỗi ngày có khả năng như nhau, bỏ qua năm nhuận và sinh đôi.
- Người thứ 1: được chọn thoải mái → 365/365
- Người thứ 2: phải né ngày của người 1 → 364/365
- Người thứ 3: phải né 2 ngày → 363/365
- ...
- Người thứ n: → (365 − n + 1)/365
Nhân tất cả lại:
Với n = 23, biểu thức này cho ra 0,5073 — tức 50,73%.
Khi chuyển hướng sang việc so sánh "mọi người với nhau", số lượng cặp so sánh tăng lên rất nhanh. Với 23 người, số lượng cặp đôi có thể tạo ra để so sánh là 253 cặp. Với 253 cơ hội để xảy ra sự trùng hợp, việc tỷ lệ vượt qua mức 50% trở nên dễ hiểu hơn rất nhiều.
Tỷ lệ thay đổi thế nào theo sĩ số nhóm?
Sự bùng nổ của xác suất theo quy mô nhóm thể hiện rất rõ qua các con số:
Số người trong phòng (n) Xác suất có ít nhất 2 người trùng ngày sinh 10 11.7% 23 50.7% 30 70.6% 57 99.0% 70 99.9% Nghĩa là, chỉ cần một hội trường nhỏ với khoảng 70 người, khả năng tìm thấy hai người cùng ngày sinh đã gần như là chắc chắn.
Từ lớp học đến an ninh mạng
Nghịch lý Ngày sinh không chỉ là một câu đố vui toán học. Nguyên lý này đóng vai trò then chốt trong khoa học máy tính và mật mã học, cụ thể là về bài toán Tấn công Ngày sinh (Birthday Attack).
Trong an ninh mạng, các hàm băm (hash functions) được dùng để biến đổi dữ liệu thành chuỗi ký tự có độ dài cố định. Về lý thuyết, mỗi dữ liệu sẽ có một chuỗi băm riêng. Tuy nhiên, tương tự như việc tìm hai người trùng ngày sinh, việc tìm ra hai tập dữ liệu khác nhau nhưng tạo ra cùng một mã băm (gọi là "độ đụng độ" hay collision) dễ xảy ra hơn chúng ta tưởng rất nhiều.
Các kỹ sư an ninh mạng bắt buộc phải sử dụng các độ dài chuỗi băm đủ lớn để ngăn chặn kẻ tấn công lợi dụng Nghịch lý Ngày sinh nhằm phá khóa mã hóa.
Tài liệu tham khảo và đọc thêm
- https://betterexplained.com/articles/understanding-the-birthday-paradox/
- https://pi.math.cornell.edu/~mec/2008-2009/TianyiZheng/Birthday.html
- https://math.info/Misc/Birthday_Problem/
Không có nhận xét nào:
Đăng nhận xét