비둘기집 원리
비둘기 10마리가 9개의 둥지에 들어가면, 적어도 한 둥지에는 두 마리 이상이 부대끼게 되는 당연한 이치예요.
정의 비둘기집 원리는 넣으려는 물건의 수가 담을 상자의 수보다 많을 때, 적어도 한 상자에는 물건이 둘 이상 들어갈 수밖에 없다는 수학 법칙이에요. 당연해 보이지만 복잡한 수학과 컴퓨터 과학 문제를 명쾌하게 풀어내는 강력한 도구예요.
10마리 비둘기와 9개의 둥지
양말 서랍에 검은 양말과 흰 양말만 섞여 있다고 상상해 보세요. 불을 끄고 양말을 몇 켤레 꺼내야 무조건 색이 같은 한 쌍을 만들 수 있을까요? 정답은 3짝이에요. 양말 색깔이라는 '상자'는 2개뿐인데 양말을 3개 뽑았으니, 적어도 한 색깔은 2짝이 겹칠 수밖에 없기 때문이에요.
이것이 바로 비둘기집 원리의 기본 모습이에요. 비둘기가 10마리 있고 비둘기집이 9개 있다면, 아무리 비둘기를 골고루 나누어 넣으려 해도 어느 한 둥지에는 반드시 두 마리 이상이 들어가야 해요. 비둘기 9마리가 둥지 하나씩을 차지하고 나면, 남은 1마리는 이미 누군가 들어가 있는 둥지에 합류해야 하거든요.
너무 당연해서 시시하게 느껴질 수도 있어요. 하지만 이 당연함이 수학에서는 엄청나게 강력한 증명 도구가 돼요. 직접 모든 경우를 일일이 확인해보지 않고도, 어떤 상황이 '반드시 일어난다'는 것을 확실하게 증명해 주기 때문이에요.
서울에 머리카락 수가 똑같은 사람이 있을까?
인구 900만 명이 넘는 서울에서 머리카락 개수가 완전히 똑같은 사람이 존재할까요? 모든 시민의 머리털을 한 올 한 올 세어보지 않아도, 비둘기집 원리를 쓰면 1초 만에 '반드시 있다'고 답할 수 있어요.
사람의 머리카락 수는 많아야 보통 15만 개 정도예요. 아주 넉넉하게 잡아서 최대 50만 개라고 해볼게요. 그러면 머리카락 개수로 만들 수 있는 '둥지'는 0개부터 50만 개까지 총 50만 1개가 나와요.
그런데 서울 시민이라는 '비둘기'는 900만 명이 넘어요. 50만 개의 둥지에 900만 마리의 비둘기를 집어넣는 셈이죠. 따라서 서울에는 머리카락 수가 정확히 일치하는 사람들의 모임이 무조건 존재해요. 비둘기집 원리가 거대한 도시의 숨겨진 규칙을 단숨에 밝혀낸 셈이에요.
조금 더 정확히 말하면
비둘기집 원리는 19세기 수학자 디리클레가 체계적으로 정리해서 '디리클레의 서랍 원리'라고도 불러요. 이 원리는 단순히 '둘 이상 겹친다'에서 끝나지 않고 훨씬 넓게 확장돼요.
예를 들어 21마리의 비둘기를 10개의 둥지에 넣는다면 어떻게 될까요? 비둘기를 최대한 골고루 2마리씩 나눠 넣어도 1마리가 남아요. 그래서 이때는 적어도 한 둥지에 3마리 이상이 들어가게 돼요. 이를 '일반화된 비둘기집 원리'라고 불러요.
컴퓨터 과학에서도 이 원리는 핵심 역할을 해요. 아무리 뛰어난 압축 기술이라도 '모든 파일의 크기를 무조건 줄이는 마법의 압축 프로그램'은 절대 만들 수 없다는 사실을 증명할 때 쓰이죠. 둥지보다 비둘기가 많은 상황은 수학과 알고리즘 곳곳에서 중요한 한계를 알려준답니다.
🤔 흔한 오해
비둘기집 원리는 어느 둥지에 비둘기가 겹치는지까지 정확히 알려준다.
어느 둥지에 겹치는지는 알 수 없고, 단지 '겹치는 둥지가 최소 하나는 반드시 존재한다'는 사실만 보장해요.
🧺 일상에서 만나요
담을 상자보다 넣을 물건이 더 많으면, 적어도 한 상자에는 둘 이상의 물건이 겹칠 수밖에 없다는 수학 원리예요.