2025. 4. 13. 12:47ㆍ전공 수학 맛보기/조합론 맛보기
우리가 여섯 켤레의 양말을 아무렇게나 서랍에 넣는다고 해 봅시다. 그런데 서랍이 다섯 칸밖에 없다면 어떤 일이 벌어질까요? 어느 서랍에는 반드시 두 켤레 이상의 양말이 들어가게 됩니다. 이 단순한 사실이 오늘 이야기할 비둘기 집 원리$(\text{Pigeonhole Principle})$입니다.
비둘기 집 원리는 다음과 같이 수학적으로 표현할 수 있습니다.
$n+1$개의 물체를 $n$개의 상자에 넣으면, 적어도 하나의 상자에는 두 개 이상의 물체가 들어간다.
이 원리는 너무 당연해 보이지만, 다양한 수학 문제에서 중요한 역할을 합니다. 몇 가지 예시를 들어보겠습니다.
Example 1. 400명이 모여 있을 때, 이들 중 두 사람 이상은 생일이 같음을 보여라.
사람의 생일은 윤년을 고려해도 총 366가지뿐인데, 400명은 이보다 많습니다. 즉, 400명의 생일을 366개의 ‘생일 상자’에 나눠 넣는 상황이 되어, 어떤 상자에는 반드시 두 명 이상이 들어가게 됩니다.
Example 2. 임의의 정수 10개를 고를 때, 9로 나눈 나머지가 같은 두 수가 존재함을 보여라.
임의의 정수 10개를 골라서 9로 나눈 나머지를 생각해 봅니다. 나머지는 $0, 1, 2, ..., 8$, 총 9가지뿐입니다. 10개의 수를 9개의 나머지 집에 넣어야 하니, 비둘기 집 원리에 따라 적어도 두 수는 같은 나머지를 가집니다.
Example 3. 가로 5칸, 세로 5칸인 격자판에 26개의 점을 아무 데나 찍을 때, 총 5개의 행 중 적어도 한 행에는 6개 이상의 점이 포함될 수밖에 없음을 보여라.
가로 5칸, 세로 5칸인 격자판에 26개의 점을 아무 데나 찍는다면, 총 5개의 행 중 적어도 한 행에는 6개 이상의 점이 포함될 수밖에 없습니다. 26개의 점이 5개의 ‘행 상자’에 배분되는 상황이기 때문입니다.
Example 4. 정수 집합 $\{1, 2, 3, ..., 100\}$에서 임의로 51개의 수를 선택했다. 이 중 두 수의 차가 1인 쌍이 반드시 존재함을 보여라.
$\{1,2\}, \{3,4\}, \{5,6\}, ..., \{99,100\}$과 같이 총 50개의 쌍을 생각할 수 있습니다. 이들은 서로 겹치지 않고, 각 쌍 안의 두 수는 차이가 1입니다. 이제 우리가 51개의 수를 선택하면, 비둘기 집 원리에 따라 적어도 하나의 쌍에 포함된 두 수가 모두 선택되었을 것입니다. 그 쌍의 두 수는 차이가 1이므로, 원하는 결과가 성립합니다.
이처럼 비둘기 집 원리는 기초적이지만 매우 중요한 원리입니다. 직접 대상을 찾기 어려운 경우, '반드시 어떤 것이 존재한다'는 것을 보여 주기 위한 핵심적인 논리로 자주 등장합니다. 조합론에서 이 원리는 문제 해결의 출발점이 되며, 특히 다음 글에서 다룰 램지 이론(Ramsey Theory)의 근간을 이루는 아이디어이기도 합니다.
비둘기 집 원리에 더 관심이 있으신 분들을 위해 아래에 비둘기집 원리를 응용한 문제를 하나 더 남겨드릴 테니, 한번 도전해보시길 추천드립니다. 궁금한 점이 있으시면 댓글로 편하게 남겨주세요. 감사합니다.
문제. 체스 마스터가 대회를 준비하기 위해 11주의 시간이 주어졌다고 하자. 그는 매일 적어도 한 판의 경기를 두기로 결심하지만, 피로를 피하기 위해 어떤 주에도 12판을 초과해서는 안 된다고 정했다. 이때, 연속된 며칠 동안 정확히 21판의 경기를 둔 시기가 반드시 존재함을 보여라.