생일 문제 birthday problem

몇 사람이 모이면 생일이 같은 두 사람이 있을 확률이 절반을 넘을까? 23명이면 약 0.507이다. 겹침은 생각보다 훨씬 빨리 생긴다.

m가지 중에서 하나씩 뽑을 때 처음 겹칠 때까지 평균 √(πm/2) 번쯤 뽑는다. 해시 충돌이 원래 입력 찾기보다 쉬운 이유가 이것이다.

다른 이름: 생일 역설