Nghịch lý Birthday là 1 trong những nghịch lý được áp dụng rất nhiều khi dùng để giải mã trong Crypto. Câu hỏi: "Cần ít nhất bao nhiêu người để xác suất có 1 cặp trong số đó trùng ngày-tháng sinh với nhau là > 50%?" Câu trả lời là 23 người. Nghe qua thì hơi khó tin, lần đầu nghe mình cũng không tin lắm :)) nhưng để chứng minh nó bằng các giải ngược thì khá đơn giản: Gọi A là biến cố không có ai trong 23 người cùng ngày sinh, ta cần tính 1- P(A). Ta có: Với mỗi người ta có cách chọn ngày sinh lần lượt là: 365, 365 - 1, ..., 365 - 22 Không gian mẫu: 365^23 Suy ra: 1- P(A) = 50.73% Vậy nên trong 1 lớp họp có hơn 30 người, xác suất có 2 người trùng ngày sinh lên tới gần 70%, nên thường trong 1 lớp sẽ có 2 người trung ngày sinh. Phát biểu: Chỉ cần thử 1.2 * sqrt(n) thì sẽ có tới 50% là có 1 cặp giống nhau. Áp dụng định lý này với phương pháp Brute-force:
Nơi mà người viết sẽ không biết ai đọc :)))
Nhận xét
Đăng nhận xét