확률·통계비둘기집의 원리#342

비둘기집의 원리

Pigeonhole Principle

비둘기집의 원리는 상자보다 많은 대상을 넣으면 어느 상자에는 둘 이상 들어감을 보장한다. 상자마다 같은 수가 들어간다는 뜻은 아니다. 일반화된 올림 경계와 최소 개수를 구하고, 나머지·짝·넓이로 상자를 만들어 존재를 증명한다.

읽는 시간
약 8분
선수 개념
곱의 법칙

직관 — 빈자리를 모두 써도 하나가 남는다

직관

작은 서랍 세 칸에 편지 네 통을 모두 넣어 보자. 한 칸에 한 통까지만 넣으면 세 통밖에 보관하지 못한다. 따라서 어느 칸에는 두 통 이상이 들어가야 한다.

편지는 대상, 서랍은 분류할 상자다. 아래 편지와 물건 배치는 가상 상황이며, 어느 상자를 택할 확률은 가정하지 않는다. 가능한 배치를 모두 적지 않아도 반드시 생기는 일을 증명하는 방법을 배운다. 생일이 같은 달인 사람, 나머지가 같은 두 정수, 가까운 두 점의 존재가 모두 이 원리로 증명된다.

비둘기집의 원리는 적어도 한 상자의 겹침을 보장한다

비둘기집의 원리는 kk개 상자에 k+1k+1개 이상의 대상을 빠짐없이 하나씩 배정하면, 적어도 한 상자에 둘 이상이 들어간다는 원리다. kk는 양의 정수이며 대상 하나가 둘 이상의 상자에 동시에 들어가지는 않는다. 빈 상자는 있어도 된다. 교과서는 이를 'nn개의 비둘기집에 n+1n+1마리의 비둘기가 들어가면 적어도 한 비둘기집에는 2마리 이상이 있다'로 쓴다.

증명은 전체 개수를 비교하면 된다. 모든 상자에 많아야 하나씩만 들어간다면 대상 수는 많아야 kk개다. 대상이 k+1k+1개 이상이라는 조건과 모순이므로 그런 배정은 불가능하다.

N>k ⟹ 어느 상자의 대상 수≥2.(1)N>k\ \Longrightarrow\ \text{어느 상자의 대상 수}\ge2. \tag{1}
정의
기호이름원어뜻
NN대상의 수number of objects배정할 전체 대상 수, 양의 정수
kk상자의 수number of boxes가능한 분류의 수, 양의 정수
qq보장되는 개수guaranteed count적어도 한 상자에 들어갈 최소 보장값
mm목표 개수target count한 상자에 모이기를 원하는 개수
⌈x⌉\lceil x\rceil올림값ceiling실수 xx 이상인 가장 작은 정수

식 (1)은 어디가 겹치는지까지 지정하지 않는다. 편지 네 통이 첫 서랍에 모두 들어가도 조건과 결론을 만족한다. ‘어느 상자에 둘 이상’과 ‘모든 상자에 둘 이상’은 다르다.

비둘기집의 원리에서 평균을 올리는 이유는 무엇일까?

NN개 대상을 kk상자에 넣으면 적어도 한 상자에 N/kN/k개 이상이 들어가고, 상자 안의 개수는 정수이므로 올림을 취한다. 일반화된 보장은

q=⌈Nk⌉,어느 상자의 대상 수≥q(2)q=\left\lceil\frac{N}{k}\right\rceil,\qquad \text{어느 상자의 대상 수}\ge q \tag{2}

이다. 반대로 모든 상자에 많아야 q−1q-1개만 들어간다고 가정해 보자. 올림의 정의에서 q−1<N/kq-1<N/k이므로 k(q−1)<Nk(q-1)<N이다. 그러나 kk상자에 넣은 전체 수가 많아야 k(q−1)k(q-1)이면 대상 NN개를 모두 넣을 수 없어 모순이다.

예를 들어 10개를 세 상자에 넣으면 10/3=31310/3=3\frac13이므로 적어도 한 상자에 4개 이상이 들어간다. 셋 모두 3개 이하면 3×3=93\times3=9개뿐이다. (4,3,3)(4,3,3)으로 넣을 수 있으므로 5개 이상까지 보장할 수는 없다.

세 상자에 각각 3개를 넣으면 합은 9다. 대상 10개를 모두 넣으려면 어느 상자는 4개 이상이어야 하며, 아래의 (4,3,3)은 그 최소 보장값을 실제로 달성하는 배치다.
그림 1 세 상자에 각각 3개를 넣으면 합은 9다. 대상 10개를 모두 넣으려면 어느 상자는 4개 이상이어야 하며, 아래의 (4,3,3)은 그 최소 보장값을 실제로 달성하는 배치다. figures/capacity_boundary.py

나눗셈 결과가 이미 정수이면 더 올리지 않는다. 12개를 세 상자에 넣을 때 올림값은 4이며 (4,4,4)(4,4,4)로 넣을 수 있어 5는 보장되지 않는다. 그림 2는 N=7N=7부터 12까지 N/3N/3의 값, 올림, 몫에 1을 더한 값을 나란히 놓았다. 강조한 올림 행이 실제 보장값이고, 몫에 1을 더한 값은 9와 12에서 보장값보다 크다.

세 상자에 N개를 넣을 때(N=7,…,12) N/3, 올림 lceil N/3rceil, 몫에 1을 더한 lfloor N/3rfloor+1을 비교했다. 보장값은 올림 행이며, 나누어떨어지는 9와 12에서는 몫에 1을 더한 값이 1만큼 크다.
그림 2 세 상자에 NN개를 넣을 때(N=7,…,12N=7,\ldots,12) N/3N/3, 올림 ⌈N/3⌉\lceil N/3\rceil, 몫에 1을 더한 ⌊N/3⌋+1\lfloor N/3\rfloor+1을 비교했다. 보장값은 올림 행이며, 나누어떨어지는 9와 12에서는 몫에 1을 더한 값이 1만큼 크다. figures/guarantee_steps.py

교과서의 일반화된 비둘기집의 원리는 'nn개의 비둘기집에 nk+1nk+1마리 이상이 들어가면 적어도 한 집에 k+1k+1마리 이상이 있다'로 쓴다. 교과서의 nn이 이 글의 상자 수 kk이고, 교과서의 k+1k+1이 이 글의 보장값 qq다. 대상이 k(q−1)+1k(q-1)+1개 이상이면 ⌈N/k⌉≥q\lceil N/k\rceil\ge q이므로 식 (2)와 같은 내용이다.

비둘기집의 원리로 최소 몇 개가 필요한지 어떻게 구할까?

어느 상자에 mm개 이상을 보장하는 최소 대상 수는 k(m−1)+1k(m-1)+1이다. k(m−1)k(m-1)개까지는 각 상자에 m−1m-1개씩 나누어 피할 수 있고, 하나를 더하면 식 (2)의 올림이 mm이 되기 때문이다.

Nmin⁡=k(m−1)+1.(3)N_{\min}=k(m-1)+1. \tag{3}

‘최소 몇 개면 보장되는가’를 물으면 이처럼 두 가지를 보인다. 그 개수에서는 결론이 반드시 성립함을 증명하고, 바로 아래 개수에서는 결론을 피하는 배치를 하나 보인다. 이는 경우의 수를 전부 계산하는 것과 다른 문제이며, 반례가 보장할 수 없는 경계를 정확히 보여 준다.

트럼프 카드의 네 무늬에서 같은 무늬 세 장을 보장하려면 상자 4개, 목표 3개다. 식 (3)에 대입하면 4×(3−1)+1=94\times(3-1)+1=9장이다. 8장은 네 무늬를 두 장씩 뽑아 같은 무늬 세 장을 피할 수 있다.

비둘기집의 원리에서 상자는 어떻게 만들까?

문제에 상자가 주어지지 않으면 결론이 바로 나오도록 분류를 직접 만든다. 같은 상자에 들어간 두 대상이 원하는 관계를 갖도록 상자를 정하는 것이 핵심이다.

나머지가 같은 수를 한 상자에 넣는다

정수 여섯 개를 골랐을 때, 두 수의 차가 5의 배수인 쌍이 있음을 보이자. 정수를 5로 나눈 나머지는 0, 1, 2, 3, 4 중 하나이므로 다섯 상자로 분류할 수 있다. 정수 여섯 개를 넣으면 식 (1)에 따라 같은 나머지인 두 수가 있다.

두 수를 a=5u+ra=5u+r, b=5v+rb=5v+r로 쓰자. u,vu,v는 정수이고 rr은 공통 나머지다. 그러면

a−b=(5u+r)−(5v+r)=5(u−v)(4)a-b=(5u+r)-(5v+r)=5(u-v) \tag{4}

이므로 차는 5의 배수다. 이 주장은 특정 여섯 수의 실험이 아니라 가능한 나머지 분류 전체에 대한 증명이다. 두 수가 같은 값이어도 차 0은 5의 배수이며, 서로 다른 정수를 고르면 0이 아닌 배수인 차를 얻는다.

가상의 여섯 정수 1, 4, 8, 11, 15, 19를 5로 나눈 나머지 상자에 배정했다. 1과 11, 4와 19가 각각 같은 상자에 들어간다. 각 수를 정확히 한 상자에 넣었다.
그림 3 가상의 여섯 정수 1, 4, 8, 11, 15, 19를 5로 나눈 나머지 상자에 배정했다. 1과 11, 4와 19가 각각 같은 상자에 들어간다. 각 수를 정확히 한 상자에 넣었다. figures/remainder_boxes.py

그림 3에서는 11−1=1011-1=10, 19−4=1519-4=15로 식 (4)를 확인할 수 있다. 숫자가 바뀌어도 여섯 정수와 다섯 나머지라는 조건이 유지되면 같은 결론이 보장된다. 정수와 유리수에서 다룬 음의 정수도 0 이상 5 미만의 나머지를 정해 같은 방식으로 분류한다.

합이 같은 짝을 한 상자에 넣는다

1부터 10까지의 자연수에서 서로 다른 여섯 개를 고르면 합이 11인 두 수가 있다. {1,10}\{1,10\}, {2,9}\{2,9\}, {3,8}\{3,8\}, {4,7}\{4,7\}, {5,6}\{5,6\}의 다섯 상자를 만들면 고른 여섯 수 중 두 수가 같은 상자에 들어간다. 한 상자에는 두 수뿐이므로 그 둘이 바로 합이 11인 짝이다. 다섯 개만 고르면 1, 2, 3, 4, 5처럼 짝을 피할 수 있다.

넓이를 나누어 상자를 만든다

한 변의 길이가 2인 정사각형 안에 점 다섯 개를 찍으면 거리가 2\sqrt2 이하인 두 점이 있다. 그림 4처럼 정사각형을 한 변이 1인 작은 정사각형 네 개로 나누면, 다섯 점 중 두 점이 같은 작은 정사각형에 들어간다. 경계 위의 점은 닿은 작은 정사각형 중 하나에만 배정한다.

작은 정사각형 안의 두 점 사이 거리는 대각선의 길이를 넘지 않는다. 대각선은 피타고라스 정리로

12+12=2(5)\sqrt{1^2+1^2}=\sqrt2 \tag{5}

다. 네 꼭짓점에 점을 찍고 다섯째 점을 중심에 찍으면 중심과 꼭짓점의 거리가 정확히 2\sqrt2라서 결론을 '2\sqrt2 미만'으로 바꿀 수는 없다. 점이 네 개뿐이면 네 꼭짓점처럼 서로 2 이상 떨어뜨릴 수 있다.

한 변의 길이가 2인 정사각형을 한 변이 1인 네 칸으로 나누고 점 다섯 개를 찍었다. 같은 칸에 들어간 두 점을 강조했으며, 그 거리는 칸의 대각선 √2 이하다.
그림 4 한 변의 길이가 2인 정사각형을 한 변이 1인 네 칸으로 나누고 점 다섯 개를 찍었다. 같은 칸에 들어간 두 점을 강조했으며, 그 거리는 칸의 대각선 2\sqrt2 이하다. figures/square_points.py

한 칸에 세 점 이상을 모으려면 식 (2)의 일반화된 원리를 쓴다. 같은 네 칸에 점 아홉 개를 찍으면 ⌈9/4⌉=3\lceil9/4\rceil=3이므로 어느 칸에는 세 점 이상이 있고, 여덟 개는 칸마다 두 개씩 두어 피할 수 있다. 교과서는 이렇게 모은 세 점이 이루는 삼각형의 넓이를 칸의 크기로 제한하는 문제를 다루며, 직접 해보기 5가 그 유형이다.

대상과 상자 수가 같으면 비둘기집의 원리를 어떻게 쓸까?

함께 놓일 수 없는 값을 찾아 상자 수를 하나 줄인다. 그러면 대상이 상자보다 많아져 식 (1)을 쓸 수 있다.

여섯 명이 모인 자리에서 두 사람은 많아야 한 번 악수하고 자기 자신과는 하지 않는다고 하자. 각 사람의 악수 횟수는 0부터 5까지 여섯 값 중 하나라서 사람 수와 같다. 그런데 악수 횟수가 0인 사람이 있으면 그 사람과 악수한 사람이 없으므로 5인 사람은 없다.

따라서 실제로 쓰이는 값은 0부터 4까지이거나 1부터 5까지로, 많아야 다섯 개다. 그림 5의 두 줄처럼 여섯 명을 다섯 상자에 넣으므로 악수 횟수가 같은 두 사람이 있다. 어떤 방식으로 악수해도 이 결론은 같다.

여섯 명의 악수 횟수를 0부터 5까지의 상자에 넣은 두 예. 위 줄은 0인 사람이 있어 5의 상자가 비고, 아래 줄은 0인 사람이 없어 0의 상자가 빈다. 어느 줄이든 다섯 상자에 여섯 명이 들어가 강조한 상자처럼 겹친다.
그림 5 여섯 명의 악수 횟수를 0부터 5까지의 상자에 넣은 두 예. 위 줄은 0인 사람이 있어 5의 상자가 비고, 아래 줄은 0인 사람이 없어 0의 상자가 빈다. 어느 줄이든 다섯 상자에 여섯 명이 들어가 강조한 상자처럼 겹친다. figures/handshake_boxes.py
핵심

양의 정수 N,kN,k에 대해, 비둘기집의 원리는 NN개 대상을 kk개 상자에 빠짐없이 하나씩 배정하면 어느 상자에는 적어도 ⌈N/k⌉\lceil N/k\rceil개가 들어감을 보장한다. 특정 상자나 모든 상자의 개수를 정하는 주장은 아니다.

비둘기집의 원리는 모든 상자에 같은 개수가 들어간다는 뜻인가요?

아니다. 비둘기집의 원리는 적어도 한 상자의 개수에 관한 보장이다. 10개를 세 상자에 (10,0,0)(10,0,0)으로 넣어도 어느 상자에 4개 이상이 있다는 결론은 성립한다.

비둘기집의 원리를 쓰려면 무작위로 넣어야 하나요?

아니다. 어떤 방식으로 배정하든 각 대상을 빠짐없이 한 상자에 넣으면 된다. 여섯 정수를 다섯 나머지로 분류하는 예에는 추첨이나 확률이 필요하지 않다.

비둘기집의 원리에서 대상과 상자 수가 같으면 겹칠 수 없나요?

아니다. 같을 때는 겹침을 보장할 수 없을 뿐, 겹치는 배치도 가능하다. 대상 셋과 상자 셋의 (1,1,1)(1,1,1)은 겹침이 없고 (3,0,0)(3,0,0)은 겹침이 있다.

비둘기집의 원리의 흔한 오해

  • 평균을 반올림하면 가장 강한 보장값이다 — 10/310/3을 반올림한 3보다 큰 4가 반드시 들어가는 상자가 있다. 개수는 정수이므로 식 (2)처럼 올림을 쓴다.
  • 보장값은 언제나 몫에 1을 더한 값이다 — 12개를 세 상자에 넣으면 ⌊12/3⌋+1=5\lfloor12/3\rfloor+1=5이지만 (4,4,4)(4,4,4)로 넣을 수 있어 5는 보장되지 않는다. 나누어떨어질 때는 그림 2처럼 올림값 4가 답이다.
  • 같은 나머지인 두 수는 각각 5의 배수다 — 1과 11은 둘 다 나머지가 1이지만 각각 5의 배수는 아니다. 보장되는 것은 두 수의 차 1010이 5의 배수라는 결론이다.

직접 해보기

  1. 물건 23개를 네 상자에 모두 넣는다. 어느 상자에 적어도 몇 개가 들어감을 보장할 수 있는가? 그보다 1개 더는 보장할 수 없는 배치도 적어라.
  2. 생일의 달이 같은 사람 3명 이상이 있음을 보장하려면 최소 몇 명이 필요한가? 생일의 날은 구별하지 않는다.
  3. 정수 여덟 개 중 두 수의 차가 7의 배수임을 증명하라. 무엇이 대상이고 무엇이 상자인가?
  4. 1부터 20까지의 자연수에서 서로 다른 11개를 고르면 차가 1인 두 수가 있음을 보여라. 10개로는 왜 보장되지 않는가?
  5. 한 변의 길이가 3인 정사각형 안에 점 19개를 찍었다. 어느 세 점도 한 직선 위에 있지 않을 때, 세 점을 꼭짓점으로 하는 삼각형 가운데 넓이가 12\frac12 이하인 것이 있음을 보여라.
답과 풀이
  1. ⌈23/4⌉=6\lceil23/4\rceil=6개다. (6,6,6,5)(6,6,6,5)의 합은 23이고 어느 상자도 7개 이상이 아니므로 7개까지는 보장되지 않는다.
  2. 식 (3)에서 상자는 12달, 목표는 3명이므로 12×(3−1)+1=2512\times(3-1)+1=25명이다. 24명은 12달에 두 명씩 배정해 같은 달 세 명을 피할 수 있다.
  3. 대상은 정수 여덟 개, 상자는 7로 나눈 나머지 0부터 6까지다. 같은 나머지인 두 수를 a=7u+ra=7u+r, b=7v+rb=7v+r로 쓰면 a−b=7(u−v)a-b=7(u-v)이므로 차는 7의 배수다.
  4. {1,2}\{1,2\}, {3,4}\{3,4\}, …, {19,20}\{19,20\}의 10개 상자에 11개를 넣으면 두 수가 같은 상자에 들어가고, 그 둘의 차는 1이다. 홀수 1, 3, 5, …, 19의 10개는 어느 두 수의 차도 2 이상이라 보장되지 않는다.
  5. 한 변이 1인 작은 정사각형 9개로 나누면 19=9×2+119=9\times2+1이므로 식 (2)에서 ⌈19/9⌉=3\lceil19/9\rceil=3, 곧 어느 칸에 세 점 이상이 있다. 그 칸의 세 점으로 삼각형을 만들고, 높이가 가운데인 꼭짓점을 지나는 가로선으로 삼각형을 둘로 자른다. 두 조각은 가로선 위의 같은 밑변을 나누어 쓰고 그 길이는 칸의 너비 1 이하, 두 조각의 높이의 합은 칸의 높이 1 이하다. 따라서 넓이는 12×1×1=12\frac12\times1\times1=\frac12 이하다.

더 읽기

영상 노트

영상 노트
  • 00:00 편지 네 통과 세 서랍으로 식 (1)을 증명한다.
  • 00:35 상자마다 최대 개수를 가정해 식 (2)의 올림을 유도하고 그림 1로 보장값 4를 확인한다.
  • 01:20 그림 2에서 반올림·몫에 1을 더한 값과 비교하고 교과서의 일반화 표기를 잇는다.
  • 02:00 식 (3)으로 카드 아홉 장을 구하고 여덟 장의 반례를 보인다.
  • 02:40 그림 3의 나머지 상자로 식 (4)를, 합이 11인 짝 상자를 만든다.
  • 03:30 그림 4의 넓이 나누기와 식 (5)로 거리 경계를 보이고, 네 칸에 점 아홉 개면 세 점이 모이는 일반화로 잇는다.
  • 04:10 그림 5에서 상자 수를 줄여 악수 문제를 풀고 새 연습을 확인한다.

지도에서의 위치

합의 법칙확률·통계곱의 법칙확률·통계비둘기집의 원리지금 이 페이지
선수 개념
이 페이지
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 교과서의 일반화 표기와 연결, 보장 공식 비교, 최소 개수 식, 짝·넓이로 상자 만들기, 일반화된 원리와 넓이를 함께 쓰는 연습, 대상과 상자 수가 같을 때 상자 줄이기, 중복 문단 정리, 질문·연습 보강 (에이전트 수정, 그림 2→5)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림