Nói đến kết quả đẹp trong khoa học máy tính, khó có thể bỏ qua nghịch lý ngày sinh.

Nghịch lý ngày sinh: Xác suất tìm được hai người có cùng ngày sinh trong 23 người chọn ngẫu nhiên ít nhất là .

Một năm có 365 (hoặc 366) ngày mà chỉ cần chọn ngẫu nhiên ra 23 người ta đã có thể tìm được hai người có cùng ngày sinh với xác suất ít nhất . Thật khó tin phải không? Thực ra đây không hẳn là nghịch lý vì điều này không có gì trái ngược với thực tế. Nên coi đây là định lý thì đúng hơn là nghịch lý.

Tổng quát hóa của nghịch lý này được phát biểu như sau:

 
Chọn có hoàn lại ở đây được hiểu là lấy ra rồi sau đỏ bỏ vào lại trong tập hợp gốc. Trong bài phân tích ra thừa số nguyên tố, chúng ta đã tìm hiểu một cách chứng minh. Ở đây mình trình bày một cách chứng minh khác với hằng số tệ hơn trong Theorem 1 một chút nhưng đơn giản hơn. Cách chứng minh này được trình bày trong một post của Emanuele Viola. Kí hiệu

 
Chứng minh: Đầu tiên chọn ra số từ tập . Giả sử không có cặp số nào trong số chọn ra có cùng giá trị. Chọn tiếp ra số nữa. Xác suất để KHÔNG có số nào trong số chọn ra trong lần 2 này có cùng giá trị với số chọn ra trong lần 1 là:

Do đó, xác suất để ít nhất một số chọn ra lần 2 bằng một số trong tập số chọn ra lần 1 là > .

Comments: Chứng minh trên có thể được mở rộng ra trong trường hợp ta chọn số từ tập , thì xác suất tìm được hai số trùng nhau ít nhất là .

Ứng dụng: Ứng dụng nổi bật nhất của nghịch lý ngày sinh là trong thuật tóa Pollard's rho mà chúng ta đã có dịp tìm hiểu trước đây. Một ứng dụng khác là trong thiết kế không gian khóa của bảng băm. Giả sử hệ thống của bạn có khoảng 100 triệu người dùng. Vì lí do bảo mật, bạn không muốn lưu tên đăng nhập của người dùng mà muốn thiết kế một hàm băm để băm tên đăng nhập thành một xâu kí tự. Đương nhiên bạn không muốn hai tên đăng nhập khác nhau cùng được băm vào một khóa. Vậy, bạn cần phải chọn khóa đầu ra là ít nhất bao nhiêu bít để đảm bảo điều này (với xác suất cao), giả sử hàm băm của bạn băm mỗi tên đăng nhập thành một số ngẫu nhiên. Áp dụng nghịch lý ngày sinh, bạn có thể tính được nếu sử dụng 32 bít đầu ra, xác suất hai người được băm vào một khóa khá cao. Nếu đầu ra là 64 bít, xác suất này giảm xuống chỉ còn cỡ , một con số bạn có thể tin tưởng được.

Nghịch lý ngày sinh cũng lí giải tại sao mà các hàm băm mật mã (cryptographic hash functions) như họ các hàm băm SHA thường có số bít đầu ra khá lớn, 256 bít hoặc 512 bít, vì các hàm băm này thường được dùng để băm số lượng rất lớn dữ liệu mà vẫn đảm bảo không có hai đoạn dữ liệu nào có cùng mã băm đầu ra. Gần đây, Google công bố đã tìm ra hai đoạn dữ liệu khác nhau mà có cùng mã băm sau khi băm bằng SHA-1. Nếu bạn làm bảo mật thì có lẽ nên tránh hàm băm này,