# 비둘기집 원리

분야: 확률통계
학교급: 중등
교육과정: 정규 교육과정 외 — 집보다 비둘기가 많으면 한 집에 둘이 들어간다는 원리. '반드시 존재한다'를 증명하는 가장 짧은 도구다.
정식 URL: https://pi.devxdev.xyz/wiki/math/%EB%B9%84%EB%91%98%EA%B8%B0%EC%A7%91_%EC%9B%90%EB%A6%AC

---

<!-- prereq: 자연수, 나눗셈 -->

> 이 개념은 정규 교육과정에는 들어 있지 않지만, "집보다 비둘기가 많으면 어느 한 집에는 반드시 비둘기가 두 마리 이상 들어간다"는 원리로, "반드시 존재한다"는 사실을 증명하는 가장 짧고 강력한 도구다.

## 정의

비둘기집 원리(pigeonhole principle)는 다음과 같다.

> $n$개의 물건을 $k$개의 상자에 나누어 넣을 때, $n > k$이면 적어도 한 상자에는 물건이 2개 이상 들어간다.

이를 조금 더 일반화하면, $n$개의 물건을 $k$개의 상자에 나눌 때 적어도 한 상자에는

$$\left\lceil \frac{n}{k} \right\rceil$$

개 이상의 물건이 들어간다. 여기서 $\lceil \; \rceil$(올림 기호, "실링"이라 읽는다)은 그 안의 값을 소수점 아래에서 올려서 가장 작은 정수로 만든다는 뜻이다. 예를 들어 $\lceil 13/12 \rceil = \lceil 1.08\cdots \rceil = 2$이다.

## 직관

비둘기 13마리가 있고 비둘기집이 12개뿐이라고 하자. 모든 비둘기집에 비둘기를 한 마리씩만 넣어도 벌써 12마리가 다 들어갔는데, 아직 한 마리가 남는다. 그 한 마리는 어딘가로 들어가야 하므로, 결국 어느 한 집에는 두 마리가 들어가게 된다.

여기서 중요한 점은, 이 원리는 **어느 집**에 두 마리가 들어가는지는 전혀 말해 주지 않는다는 것이다. 그저 "반드시 어딘가에는 겹치는 집이 있다"는 존재성만 보장한다. 계산으로 정확한 위치를 찾는 게 아니라, 세는 것만으로 존재를 증명하는 방식이라 수학의 여러 분야에서 놀랍도록 자주 쓰인다.

## 유도

이 원리는 공식을 계산해서 얻는 것이 아니라, "만약 아니라면 어떻게 될까"를 따라가면 저절로 드러난다.

**1단계.** 물건이 $n$개, 상자가 $k$개이고 $n>k$라고 하자. 원리를 의심해 보자: "모든 상자에 물건이 최대 1개씩만 들어간다"고 가정해 보는 것이다.

**2단계.** 이 가정이 맞다면, 상자가 $k$개이므로 들어간 물건의 총 개수는 최대 $k \times 1 = k$개다.

**3단계.** 그런데 실제 물건의 개수는 $n$개이고, 처음에 $n>k$라고 했다. 즉 물건의 총 개수가 $k$개를 넘어야 하는데, 2단계에서는 최대 $k$개까지만 담을 수 있다고 나왔다. $n > k$인데 담긴 개수는 $k$ 이하라는 것은 모순이다.

**4단계.** 모순이 생겼으므로 1단계의 가정("모든 상자에 최대 1개씩")은 틀렸다. 따라서 적어도 한 상자에는 물건이 2개 이상 들어간다.

이 논리를 그대로 확장하면 일반화된 형태도 나온다. "모든 상자에 물건이 최대 $m$개씩만 들어간다"고 가정하면 총 개수는 최대 $km$개다. 이것이 $n$보다 작아지지 않으려면 $km \ge n$, 즉 $m \ge n/k$여야 하므로, $m$이 정수라는 사실까지 쓰면 적어도 한 상자에는 $\lceil n/k \rceil$개 이상이 들어가야 함을 알 수 있다.

## 예시

**예시 1.** 학생 13명이 있다. 이 중 태어난 달(1월~12월, 12가지)이 같은 두 학생이 반드시 존재함을 보이자. 학생 13명을 "물건", 12개의 달을 "상자"로 보면 $n=13$, $k=12$이고 $n>k$이므로 비둘기집 원리에 의해 적어도 한 달에는 2명 이상이 몰린다.

**예시 2.** 자연수 $40$개를 $7$개의 나머지($0,1,2,3,4,5,6$)로 분류하면, 적어도 한 나머지 그룹에는 $\lceil 40/7 \rceil = \lceil 5.71\cdots \rceil = 6$개 이상의 수가 들어간다. 이는 어떤 자연수를 $7$로 나눈 나머지가 $0$부터 $6$까지 $7$가지뿐이라는 사실( 나눗셈 )에서 상자의 개수 $k=7$이 정해지기 때문이다.

## 🌍 실생활 예시

압축(비둘기집 원리는 데이터 압축의 한계를 설명하는 데 쓰인다)을 예로 들면, 길이 $n$비트인 파일을 그보다 짧은 비트열로 무손실로 완벽하게 압축하는 방법은 절대 존재할 수 없다. 길이가 $n$인 파일은 $2^n$가지가 있는데, 그보다 짧은(예: $n-1$비트 이하) 비트열은 $2^n$가지보다 적다. 파일(물건)의 개수가 압축 결과(상자)의 개수보다 많으므로, 서로 다른 두 파일이 같은 압축 결과로 겹치는 경우가 반드시 생긴다. 그래서 "모든 파일을 항상 더 짧게 압축하는 프로그램"은 존재할 수 없다.

## ⚠️ 흔한 실수

- **잘못된 생각:** 물건 수 $n$과 상자 수 $k$가 같으면($n=k$) 그래도 어딘가는 겹칠 것이다.
  **왜 틀렸는지:** 원리는 $n>k$일 때만 겹침을 보장한다. $n=k$이면 각 상자에 정확히 하나씩 넣어서 겹치지 않게 나누는 것이 충분히 가능하다. 예를 들어 물건 12개를 상자 12개에 하나씩 넣으면 아무 상자도 겹치지 않는다.
- **잘못된 생각:** $n/k$의 값을 그대로(올림 없이) 쓰면 된다.
  **왜 틀렸는지:** $13/12 = 1.08\cdots$을 그대로 보면 "최소 1개"라고 착각하기 쉽다. 하지만 물건의 개수는 정수여야 하므로 소수점을 올려서 $\lceil 13/12 \rceil = 2$로 계산해야 정확한 최솟값이 나온다.
- **잘못된 생각:** 원리가 겹치는 상자가 정확히 어디인지, 몇 개나 겹치는지 다 알려준다.
  **왜 틀렸는지:** 원리는 오직 "적어도 하나는 겹친다"는 존재성만 보장할 뿐, 어느 상자인지·정확히 몇 개인지는 알려주지 않는다. 위치를 알아내려면 별도의 조사가 필요하다.

## 확인 문제

1. 양말 서랍에 검은색, 흰색, 회색 양말이 섞여 있다. 색을 보지 않고 양말을 꺼낼 때, 같은 색 한 쌍을 반드시 만들려면 최소 몇 개를 꺼내야 하는가? (색이 3가지임을 상자 수로 생각해 보라.)
2. 자연수 $50$개를 $9$로 나눈 나머지에 따라 분류하면, 나머지가 같은 자연수가 적어도 몇 개인 그룹이 반드시 존재하는가?
3. 어느 학교의 한 학년 학생이 $370$명이다. 1년은 최대 $366$일(윤년 포함)이다. 이 학년에 생일이 같은 두 학생이 반드시 존재하는 이유를 비둘기집 원리로 설명하라. 그리고 만약 학생이 $366$명이라면 그 결론이 항상 성립하는지도 생각해 보라.

정답 보기:

1. 상자(색)는 3개이므로 $n>k=3$을 만족하는 가장 작은 $n$은 $4$. 4개를 꺼내면 비둘기집 원리에 의해 반드시 같은 색이 2개 이상 나온다. (3개까지는 검은색·흰색·회색 각 1개씩만 뽑는 경우가 있어 짝이 안 생길 수 있다.)
2. $n=50$, $k=9$이므로 $\lceil 50/9 \rceil = \lceil 5.55\cdots \rceil = 6$. 적어도 한 나머지 그룹에는 6개 이상의 수가 있다.
3. $n=370$, $k=366$이고 $n>k$이므로 비둘기집 원리에 의해 생일이 같은 두 학생이 반드시 존재한다. 학생이 정확히 $366$명($n=k$)이라면 $n>k$가 아니므로 원리가 보장하지 않는다 — 실제로 서로 다른 366일에 한 명씩 태어났다면 아무도 겹치지 않을 수 있다.



## 📜 역사

비둘기집 원리는 독일의 수학자 디리클레(Peter Gustav Lejeune Dirichlet)가 19세기에 무리수를 분수로 근사하는 문제(디오판토스 근사)를 다루면서 사용한 것으로 알려져 있으며, 그래서 "디리클레의 상자 원리(Dirichlet's box principle)"라는 이름으로도 불린다. 원리 자체는 너무 단순해서 증명이라 부르기 어색할 정도지만, 존재성만으로 강력한 결론을 끌어내는 방식이 유용해 정수론을 비롯한 여러 분야에서 표준적인 논증 도구로 자리 잡았다.

## 관련 개념

- 자연수 — 물건과 상자의 개수를 세는 기본 단위
- 나눗셈 — 나머지로 상자를 분류하는 전형적인 응용
- 경우의 수와 확률의 기초 — 물건과 상자의 개수를 헤아리는 발상을 공유
- 조합 — 특정 경우의 수를 세어 비둘기집 원리와 함께 쓰이는 경우가 많음
- 포함배제의 원리 — 집합의 크기를 세어 존재를 증명하는 또 다른 도구

---

관련 개념:
- 나눗셈 (/wiki/math/%EB%82%98%EB%88%97%EC%85%88)
- 자연수 (/wiki/math/%EC%9E%90%EC%97%B0%EC%88%98)
- 경우의 수와 확률의 기초 (/wiki/math/%EA%B2%BD%EC%9A%B0%EC%9D%98_%EC%88%98%EC%99%80_%ED%99%95%EB%A5%A0%EC%9D%98_%EA%B8%B0%EC%B4%88)
- 조합 (/wiki/math/%EC%A1%B0%ED%95%A9)
- 포함배제의 원리 (/wiki/math/%ED%8F%AC%ED%95%A8%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC)