생일 문제
같은 생일을 가진 둘을 찾아보세요
한 반에 학생이 23명 모여 있습니다. 1년은 365일이나 되니 생일이 겹치는 사람이 있을 리 없다고 누구나 생각합니다.
하지만 실제로 생일을 조사해 보면 생일이 똑같은 두 사람이 존재할 확률이 50%를 훌쩍 넘습니다. 365일 중 23명뿐인데 왜 반반을 넘어 필연처럼 겹칠까요?
이야기
Smithsonian Institution from United Stat
No restrictions · 위키미디어 공용
선생님이 서른 명 앞에서 이 내기를 겁니다. 「생일이 같은 사람이 있으면 내가 이깁니다.」 학생들은 웃습니다. 날짜가 365개인데 서른 명뿐이니까요. 그러고는 한 사람씩 생일을 부르기 시작하면 교실이 조용해집니다.
그런데 물음을 한 글자만 바꾸면 답이 완전히 달라집니다. 「나와 생일이 같은 사람이 있을까」로 물으면, 50%를 넘기려면 스물셋이 아니라 253명이 필요합니다. 열 배가 넘습니다. 같은 교실, 같은 사람들인데 말입니다.
까닭은 세는 것이 사람이 아니라 짝이기 때문입니다. 스물셋에서 짝을 지으면 23×22÷2 = 253쌍입니다. 나를 낀 짝은 그 가운데 스물둘뿐인데, 나머지 231쌍이 나 모르게 저희끼리 겨루고 있습니다.
셈은 거꾸로가 쉽습니다. 「아무도 안 겹칠 확률」을 구하면 364/365 × 363/365 × … 로 스물두 번 곱하는데, 그 값이 0.4927까지 떨어집니다. 그래서 겹칠 확률이 50.7%가 됩니다.
암호를 깨는 「생일 공격」이 여기서 나왔습니다. 아무 둘만 겹치면 되니 필요한 시도가 제곱근으로 줄어듭니다.
그래서 지금 쓰는 해시는 256비트입니다 — 안전 여유를 절반으로 계산해 정했습니다.
계단 넷 — 같은 사실을 네 깊이로
교실에서 직접 세어 본다
교실에서 23명의 생일을 칠판에 적어 봅니다. 365개 날짜 중에 겨우 23개만 고른 것이라 겹치기 힘들 것 같습니다.
하지만 "나와 같은 생일"을 찾는 것이 아니라 "누구든 둘이 겹치기만 하면 되는" 짝을 세어야 합니다. 23명이 모이면 서로 비교할 수 있는 쌍의 수가 쌍이나 되기 때문에 겹칠 확률이 순식간에 절반을 넘어섭니다.
몇 명이면 생일이 겹칠까요
우리 반 25명 중 생일 같은 짝꿍이 있을 확률이 동전 던져 앞면 나올 확률보다 높다
여사건으로 셈하기
확률을 계산할 때는 반대로 모두의 생일이 전부 다를 확률(여사건)을 먼저 구합니다.
첫 번째 사람은 365일 아무 날이나 되고, 두 번째는 364일, 세 번째는 363일... 23번째 사람은 343일이 남습니다. 전체 확률은 입니다. 따라서 적어도 두 사람의 생일이 겹칠 확률은 가 됩니다.
짝의 개수를 세어 보세요
사람은 스물세 명뿐이지만 둘씩 짝지어 비교하는 짝꿍 선은 253개나 그어진다
곱의 근사·지수
명이 모였을 때 모두 다를 확률은 입니다. 테일러 전개 를 적용하면 이 됩니다.
확률이 50%가 되는 인원수는 근사식 로 약 23명임이 명쾌하게 유도됩니다.
날 수를 바꿔 보세요
복잡한 생일 곱셈식이 루트 365 공식 하나로 깔끔하게 23명으로 풀려 나온다
충돌 확률과 해시
이 원리는 암호학에서 해시 함수의 안전성을 위협하는 생일 공격(Birthday Attack)의 수학적 기초입니다. 가지 출력값을 가진 해시 함수에서 충돌(Collision)을 찾으려면 번 시도할 필요 없이 약 번만 시도하면 50% 확률로 충돌 쌍이 발견됩니다.
따라서 128비트 보안을 달성하려면 해시 출력 길이가 최소 256비트 이상이어야 합니다.
해시 충돌을 재 보세요
철통같은 비밀번호도 생일 문제 마법을 쓰면 시도 횟수를 절반의 제곱근으로 깎아 부술 수 있다
풀어 보기
생일 문제와 충돌 확률. 1년을 365일이라 하자.
(1) 3명이 모였을 때 3명의 생일이 모두 다를 확률 식을 곱셈 꼴로 쓰시오.
(2) 4명이 모였을 때 두 명씩 짝지을 수 있는 총 쌍의 수 를 구하시오.
(3) 23명이 모였을 때 같은 생일이 존재할 확률이 50%를 넘는 까닭을 가능한 비교 쌍의 수(253쌍) 관점에서 설명하시오.
(1) , (2) 6쌍입니다.
답과 풀이 보기
(1) 입니다.
첫 사람은 아무 날이나 되고(), 둘째는 그 날을 뺀 364 일, 셋째는 362... 이렇게 하나씩 줄여 갑니다.
(2) 쌍입니다.
(1,2)(1,3)(1,4)(2,3)(2,4)(3,4) — 여섯입니다.
(3) 우리가 세는 것은 사람 수가 아니라 쌍의 수이기 때문입니다.
쌍이나 됩니다.
사람은 23 명뿐인데 견주어 볼 자리는 253 군데입니다. 사람이 명이면 쌍은 — 제곱으로 자랍니다.
각 쌍이 어긋날 확률이 이므로 253 쌍이 모두 어긋날 확률은 대략 — 절반 아래로 떨어집니다.
정확히 셈하면 모두 다를 확률이 0.4927 이므로 같은 생일이 있을 확률은 0.5073 — 50% 를 넘습니다.
⛔ 흔한 착각 — 「나와 같은 생일」을 떠올리기 때문에 이상해 보입니다. 그건 22 쌍뿐이라 확률이 약 6% 입니다.
문제가 묻는 것은 「누구든 두 사람」입니다. 그 순간 쌍이 253 개가 됩니다.
축구 경기장의 스물세 명(양 팀 11 명씩과 심판)에서 같은 생일이 나올 확률이 이미 반을 넘습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「짝의 수」가 폭발한다는 것이 열쇠입니다.
- 해시 충돌 — 암호에서 같은 값이 나오는 공격을 「생일 공격」이라 합니다
- DNA 감식 — 우연히 일치할 확률을 셈할 때 같은 논리를 씁니다
- 직접 확인 — 학급에서 생일을 물어보면 놀랄 만큼 자주 겹칩니다
이어지는 장
스물세 명만 모여도 생일이 겹칠 확률이 절반을 넘는다는 놀라운 사실은, 컴퓨터 과학에서 암호 해시 함수가 우연히 같은 값을 뱉어내는 충돌 공격의 수학적 토대가 됩니다 — 제141장 에서 이 확률이 현대 암호의 안전성을 시험하는 현장을 확인하세요.
영감을 받은 곳
리하르트 폰 미제스(Richard von Mises)가 1939년에 정립한 확률론 계산과 해럴드 대븐포트(Harold Davenport) 등의 조합론적 분석에서 유래했습니다.