비둘기집의 원리

2월 29일까지 생각하면 생일은 366가지이다. 그래서 367명이 모이면 생일이 같은 두 사람이 반드시 있다. 그런데 반드시는 아니어도, 생일이 같은 두 사람이 있을 확률이 절반을 넘으려면 몇 명이면 될까? 많은 사람이 180명쯤이라고 짐작하지만, 실제로는 23명이면 된다. "반드시 있다"와 "있을 가능성이 크다"는 어떻게 다르고, 두 질문은 각각 어떤 방법으로 답할까?

1.5.1상자보다 물건이 많으면

비둘기 \(n + 1\)마리가 비둘기집 \(n\)개에 들어가면, 적어도 한 집에는 두 마리 이상이 들어간다. 모든 집에 한 마리 이하씩이면 많아야 \(n\)마리이기 때문이다. 이 당연해 보이는 사실을 비둘기집의 원리라 한다. 이 원리는 무엇이 어디에 있는지는 알려 주지 않고, 그런 것이 반드시 있다는 것만 알려 준다. 그래서 원리를 쓸 때 어려운 부분은 무엇을 비둘기로, 무엇을 집으로 삼을지 찾는 일이다.

1부터 100까지의 자연수 가운데 51개를 고르면, 그 가운데 한 수가 다른 수를 나누는 두 수가 반드시 있다. 모든 자연수는 \(2^k\times(\text{홀수})\)로 단 한 가지로 쓸 수 있고, 1부터 100 사이의 홀수는 50개이다. 홀수 부분을 집으로 삼으면 51개의 수 가운데 두 수가 같은 집에 들어가고, 홀수 부분이 같은 두 수는 \(2\)의 거듭제곱만 다르므로 작은 수가 큰 수를 나눈다. 50개만 고르면 51부터 100까지처럼 그런 두 수가 없게 고를 수 있으므로, 51은 가장 작은 수이다.¹

1.5.2확률로 보는 생일 문제

생일이 같은 두 사람이 있을 확률은 여사건, 곧 모든 사람의 생일이 다를 확률을 1에서 빼서 구한다. 첫 사람은 아무 날이나, 둘째 사람은 첫 사람과 다른 364일 가운데, 셋째 사람은 363일 가운데 생일이 있어야 한다. 그래서 \(n\)명의 생일이 모두 다를 확률은 \(\dfrac{365}{365}\times\dfrac{364}{365}\times\cdots\times\dfrac{365 - n + 1}{365}\)이다. 사람 수에 비해 확률이 빨리 커지는 까닭은 비교할 두 사람의 쌍이 \({}_n\mathrm{C}_2\)개로, 사람 수의 제곱처럼 늘기 때문이다. 23명이면 쌍이 253개나 된다.

1.5.3예제 풀이

23명의 생일이 모두 다를 확률이 약 0.493이므로, 생일이 같은 두 사람이 있을 확률은 \(1 - 0.493 = 0.507\)로 절반을 넘는다. 비둘기집의 원리로 반드시 있다고 말하려면 366명이 필요하지만, 가능성이 절반을 넘는 데는 23명이면 충분하다.

30명을 12달에 넣으면 어떤 달에는 적어도 \(\lceil 30/12\rceil = 3\)명이 태어났다. 모든 달에 2명 이하라면 많아야 24명이기 때문이다. 그래서 30명의 반에는 같은 달에 태어난 사람이 반드시 3명 이상 있다. 즉 비둘기집의 원리는 물건이 상자보다 많을 때 반드시 겹치는 상자가 있다는 것을 알려 주고, 확률은 그보다 훨씬 적은 수에서도 겹칠 가능성이 크다는 것을 알려 준다.

아래 탐구 카드에서 몇 명이 모이면 생일이 같은 두 사람이 있을지 실험해 보고, 서로 나누어떨어지지 않게 수를 몇 개까지 고를 수 있는지 알아보자.

1. 비둘기집의 원리는 1834년 독일의 디리클레가 수론에서 처음 체계적으로 써서 디리클레의 서랍 원리라고도 부른다. 그는 이 원리로, 어떤 무리수든 분모가 작은 분수로 아주 가깝게 어림할 수 있음을 증명했다.