직관 — 빈자리를 모두 써도 하나가 남는다
작은 서랍 세 칸에 편지 네 통을 모두 넣어 보자. 한 칸에 한 통까지만 넣으면 세 통밖에 보관하지 못한다. 따라서 어느 칸에는 두 통 이상이 들어가야 한다.
편지는 대상, 서랍은 분류할 상자다. 아래 편지와 물건 배치는 가상 상황이며, 어느 상자를 택할 확률은 가정하지 않는다. 가능한 배치를 모두 적지 않아도 반드시 생기는 일을 증명하는 방법을 배운다. 생일이 같은 달인 사람, 나머지가 같은 두 정수, 가까운 두 점의 존재가 모두 이 원리로 증명된다.
비둘기집의 원리는 적어도 한 상자의 겹침을 보장한다
비둘기집의 원리는 개 상자에 개 이상의 대상을 빠짐없이 하나씩 배정하면, 적어도 한 상자에 둘 이상이 들어간다는 원리다. 는 양의 정수이며 대상 하나가 둘 이상의 상자에 동시에 들어가지는 않는다. 빈 상자는 있어도 된다. 교과서는 이를 '개의 비둘기집에 마리의 비둘기가 들어가면 적어도 한 비둘기집에는 2마리 이상이 있다'로 쓴다.
증명은 전체 개수를 비교하면 된다. 모든 상자에 많아야 하나씩만 들어간다면 대상 수는 많아야 개다. 대상이 개 이상이라는 조건과 모순이므로 그런 배정은 불가능하다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 대상의 수 | number of objects | 배정할 전체 대상 수, 양의 정수 | |
| 상자의 수 | number of boxes | 가능한 분류의 수, 양의 정수 | |
| 보장되는 개수 | guaranteed count | 적어도 한 상자에 들어갈 최소 보장값 | |
| 목표 개수 | target count | 한 상자에 모이기를 원하는 개수 | |
| 올림값 | ceiling | 실수 이상인 가장 작은 정수 |
식 (1)은 어디가 겹치는지까지 지정하지 않는다. 편지 네 통이 첫 서랍에 모두 들어가도 조건과 결론을 만족한다. ‘어느 상자에 둘 이상’과 ‘모든 상자에 둘 이상’은 다르다.
비둘기집의 원리에서 평균을 올리는 이유는 무엇일까?
개 대상을 상자에 넣으면 적어도 한 상자에 개 이상이 들어가고, 상자 안의 개수는 정수이므로 올림을 취한다. 일반화된 보장은
이다. 반대로 모든 상자에 많아야 개만 들어간다고 가정해 보자. 올림의 정의에서 이므로 이다. 그러나 상자에 넣은 전체 수가 많아야 이면 대상 개를 모두 넣을 수 없어 모순이다.
예를 들어 10개를 세 상자에 넣으면 이므로 적어도 한 상자에 4개 이상이 들어간다. 셋 모두 3개 이하면 개뿐이다. 으로 넣을 수 있으므로 5개 이상까지 보장할 수는 없다.
figures/capacity_boundary.py나눗셈 결과가 이미 정수이면 더 올리지 않는다. 12개를 세 상자에 넣을 때 올림값은 4이며 로 넣을 수 있어 5는 보장되지 않는다. 그림 2는 부터 12까지 의 값, 올림, 몫에 1을 더한 값을 나란히 놓았다. 강조한 올림 행이 실제 보장값이고, 몫에 1을 더한 값은 9와 12에서 보장값보다 크다.
figures/guarantee_steps.py교과서의 일반화된 비둘기집의 원리는 '개의 비둘기집에 마리 이상이 들어가면 적어도 한 집에 마리 이상이 있다'로 쓴다. 교과서의 이 이 글의 상자 수 이고, 교과서의 이 이 글의 보장값 다. 대상이 개 이상이면 이므로 식 (2)와 같은 내용이다.
비둘기집의 원리로 최소 몇 개가 필요한지 어떻게 구할까?
어느 상자에 개 이상을 보장하는 최소 대상 수는 이다. 개까지는 각 상자에 개씩 나누어 피할 수 있고, 하나를 더하면 식 (2)의 올림이 이 되기 때문이다.
‘최소 몇 개면 보장되는가’를 물으면 이처럼 두 가지를 보인다. 그 개수에서는 결론이 반드시 성립함을 증명하고, 바로 아래 개수에서는 결론을 피하는 배치를 하나 보인다. 이는 경우의 수를 전부 계산하는 것과 다른 문제이며, 반례가 보장할 수 없는 경계를 정확히 보여 준다.
트럼프 카드의 네 무늬에서 같은 무늬 세 장을 보장하려면 상자 4개, 목표 3개다. 식 (3)에 대입하면 장이다. 8장은 네 무늬를 두 장씩 뽑아 같은 무늬 세 장을 피할 수 있다.
비둘기집의 원리에서 상자는 어떻게 만들까?
문제에 상자가 주어지지 않으면 결론이 바로 나오도록 분류를 직접 만든다. 같은 상자에 들어간 두 대상이 원하는 관계를 갖도록 상자를 정하는 것이 핵심이다.
나머지가 같은 수를 한 상자에 넣는다
정수 여섯 개를 골랐을 때, 두 수의 차가 5의 배수인 쌍이 있음을 보이자. 정수를 5로 나눈 나머지는 0, 1, 2, 3, 4 중 하나이므로 다섯 상자로 분류할 수 있다. 정수 여섯 개를 넣으면 식 (1)에 따라 같은 나머지인 두 수가 있다.
두 수를 , 로 쓰자. 는 정수이고 은 공통 나머지다. 그러면
이므로 차는 5의 배수다. 이 주장은 특정 여섯 수의 실험이 아니라 가능한 나머지 분류 전체에 대한 증명이다. 두 수가 같은 값이어도 차 0은 5의 배수이며, 서로 다른 정수를 고르면 0이 아닌 배수인 차를 얻는다.
figures/remainder_boxes.py그림 3에서는 , 로 식 (4)를 확인할 수 있다. 숫자가 바뀌어도 여섯 정수와 다섯 나머지라는 조건이 유지되면 같은 결론이 보장된다. 정수와 유리수에서 다룬 음의 정수도 0 이상 5 미만의 나머지를 정해 같은 방식으로 분류한다.
합이 같은 짝을 한 상자에 넣는다
1부터 10까지의 자연수에서 서로 다른 여섯 개를 고르면 합이 11인 두 수가 있다. , , , , 의 다섯 상자를 만들면 고른 여섯 수 중 두 수가 같은 상자에 들어간다. 한 상자에는 두 수뿐이므로 그 둘이 바로 합이 11인 짝이다. 다섯 개만 고르면 1, 2, 3, 4, 5처럼 짝을 피할 수 있다.
넓이를 나누어 상자를 만든다
한 변의 길이가 2인 정사각형 안에 점 다섯 개를 찍으면 거리가 이하인 두 점이 있다. 그림 4처럼 정사각형을 한 변이 1인 작은 정사각형 네 개로 나누면, 다섯 점 중 두 점이 같은 작은 정사각형에 들어간다. 경계 위의 점은 닿은 작은 정사각형 중 하나에만 배정한다.
작은 정사각형 안의 두 점 사이 거리는 대각선의 길이를 넘지 않는다. 대각선은 피타고라스 정리로
다. 네 꼭짓점에 점을 찍고 다섯째 점을 중심에 찍으면 중심과 꼭짓점의 거리가 정확히 라서 결론을 ' 미만'으로 바꿀 수는 없다. 점이 네 개뿐이면 네 꼭짓점처럼 서로 2 이상 떨어뜨릴 수 있다.
figures/square_points.py한 칸에 세 점 이상을 모으려면 식 (2)의 일반화된 원리를 쓴다. 같은 네 칸에 점 아홉 개를 찍으면 이므로 어느 칸에는 세 점 이상이 있고, 여덟 개는 칸마다 두 개씩 두어 피할 수 있다. 교과서는 이렇게 모은 세 점이 이루는 삼각형의 넓이를 칸의 크기로 제한하는 문제를 다루며, 직접 해보기 5가 그 유형이다.
대상과 상자 수가 같으면 비둘기집의 원리를 어떻게 쓸까?
함께 놓일 수 없는 값을 찾아 상자 수를 하나 줄인다. 그러면 대상이 상자보다 많아져 식 (1)을 쓸 수 있다.
여섯 명이 모인 자리에서 두 사람은 많아야 한 번 악수하고 자기 자신과는 하지 않는다고 하자. 각 사람의 악수 횟수는 0부터 5까지 여섯 값 중 하나라서 사람 수와 같다. 그런데 악수 횟수가 0인 사람이 있으면 그 사람과 악수한 사람이 없으므로 5인 사람은 없다.
따라서 실제로 쓰이는 값은 0부터 4까지이거나 1부터 5까지로, 많아야 다섯 개다. 그림 5의 두 줄처럼 여섯 명을 다섯 상자에 넣으므로 악수 횟수가 같은 두 사람이 있다. 어떤 방식으로 악수해도 이 결론은 같다.
figures/handshake_boxes.py양의 정수 에 대해, 비둘기집의 원리는 개 대상을 개 상자에 빠짐없이 하나씩 배정하면 어느 상자에는 적어도 개가 들어감을 보장한다. 특정 상자나 모든 상자의 개수를 정하는 주장은 아니다.
비둘기집의 원리는 모든 상자에 같은 개수가 들어간다는 뜻인가요?
아니다. 비둘기집의 원리는 적어도 한 상자의 개수에 관한 보장이다. 10개를 세 상자에 으로 넣어도 어느 상자에 4개 이상이 있다는 결론은 성립한다.
비둘기집의 원리를 쓰려면 무작위로 넣어야 하나요?
아니다. 어떤 방식으로 배정하든 각 대상을 빠짐없이 한 상자에 넣으면 된다. 여섯 정수를 다섯 나머지로 분류하는 예에는 추첨이나 확률이 필요하지 않다.
비둘기집의 원리에서 대상과 상자 수가 같으면 겹칠 수 없나요?
아니다. 같을 때는 겹침을 보장할 수 없을 뿐, 겹치는 배치도 가능하다. 대상 셋과 상자 셋의 은 겹침이 없고 은 겹침이 있다.
비둘기집의 원리의 흔한 오해
- 평균을 반올림하면 가장 강한 보장값이다 — 을 반올림한 3보다 큰 4가 반드시 들어가는 상자가 있다. 개수는 정수이므로 식 (2)처럼 올림을 쓴다.
- 보장값은 언제나 몫에 1을 더한 값이다 — 12개를 세 상자에 넣으면 이지만 로 넣을 수 있어 5는 보장되지 않는다. 나누어떨어질 때는 그림 2처럼 올림값 4가 답이다.
- 같은 나머지인 두 수는 각각 5의 배수다 — 1과 11은 둘 다 나머지가 1이지만 각각 5의 배수는 아니다. 보장되는 것은 두 수의 차 이 5의 배수라는 결론이다.
직접 해보기
- 물건 23개를 네 상자에 모두 넣는다. 어느 상자에 적어도 몇 개가 들어감을 보장할 수 있는가? 그보다 1개 더는 보장할 수 없는 배치도 적어라.
- 생일의 달이 같은 사람 3명 이상이 있음을 보장하려면 최소 몇 명이 필요한가? 생일의 날은 구별하지 않는다.
- 정수 여덟 개 중 두 수의 차가 7의 배수임을 증명하라. 무엇이 대상이고 무엇이 상자인가?
- 1부터 20까지의 자연수에서 서로 다른 11개를 고르면 차가 1인 두 수가 있음을 보여라. 10개로는 왜 보장되지 않는가?
- 한 변의 길이가 3인 정사각형 안에 점 19개를 찍었다. 어느 세 점도 한 직선 위에 있지 않을 때, 세 점을 꼭짓점으로 하는 삼각형 가운데 넓이가 이하인 것이 있음을 보여라.
답과 풀이
- 개다. 의 합은 23이고 어느 상자도 7개 이상이 아니므로 7개까지는 보장되지 않는다.
- 식 (3)에서 상자는 12달, 목표는 3명이므로 명이다. 24명은 12달에 두 명씩 배정해 같은 달 세 명을 피할 수 있다.
- 대상은 정수 여덟 개, 상자는 7로 나눈 나머지 0부터 6까지다. 같은 나머지인 두 수를 , 로 쓰면 이므로 차는 7의 배수다.
- , , …, 의 10개 상자에 11개를 넣으면 두 수가 같은 상자에 들어가고, 그 둘의 차는 1이다. 홀수 1, 3, 5, …, 19의 10개는 어느 두 수의 차도 2 이상이라 보장되지 않는다.
- 한 변이 1인 작은 정사각형 9개로 나누면 이므로 식 (2)에서 , 곧 어느 칸에 세 점 이상이 있다. 그 칸의 세 점으로 삼각형을 만들고, 높이가 가운데인 꼭짓점을 지나는 가로선으로 삼각형을 둘로 자른다. 두 조각은 가로선 위의 같은 밑변을 나누어 쓰고 그 길이는 칸의 너비 1 이하, 두 조각의 높이의 합은 칸의 높이 1 이하다. 따라서 넓이는 이하다.
더 읽기
- 우리교과서 2022 개정 고등학교 이산 수학 — 이준열 외, 인쇄40–43쪽. 기본 원리와 일반화된 원리, 상자 수를 줄이는 적용, 도형을 나누어 상자를 만드는 적용을 확인했다.
- Math 413 Lecture 7 — The Pigeonhole Principle — Alexander Yong, University of Illinois, 2026. 대상을 적절한 상자에 분류하는 증명과 최소 보장을 위한 경계 사례를 읽었다. 뒤의 고급 예제는 이 글의 선수로 요구하지 않는다.
영상 노트
- 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에서 상자 수를 줄여 악수 문제를 풀고 새 연습을 확인한다.
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 교과서의 일반화 표기와 연결, 보장 공식 비교, 최소 개수 식, 짝·넓이로 상자 만들기, 일반화된 원리와 넓이를 함께 쓰는 연습, 대상과 상자 수가 같을 때 상자 줄이기, 중복 문단 정리, 질문·연습 보강 (에이전트 수정, 그림 2→5)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림