비둘기집 원리?
비둘기집 원리는 n개의 상자에 n + 1개의 물건을 넣는다고 하면 어느 한 상자에는 물건이 두 개 이상에 물건이 들어 있다는 원리이다.
서랍을 뜻하는 "pigeonhole"이 독일어가 아닌 지역을 거쳐가며 점차 오해가 생겨 비둘기집이라는 뜻을 가지게 되었다고 한다. 따라서 서랍 원칙, 구두 상자의 원리라고도 한다.
제한된 칸보다 많은 양을 넣는다면 넘친다는 사실은 조금만 생각해도 알 수 있는 내용이지만 생각보다 많은 알고리즘 예제에서 활용할 수 있다.
이 원리의 증명은 대표적인 존재 증명으로 비둘기가 두 개 이상 들어있는 상자의 존재는 알 수 있지만 어떤 상자에 비둘기가 두 개 이상 들어있는지는 알 수 없다.
증명하기
모든 비둘기가 상자안에 들어간다는 가정하에 이 원리는 간단한 귀류법을 통해 증명해낼 수 있다.
n개의 상자와 n+1개의 비둘기가 존재한다고 가정한다.
만약, 각 상자에 비둘기가 한 개 이하만 존재해야 한다면, 전체 상자에는 많아야 n개의 비둘기가 존재한다.
하지만 이 과정에서 비둘기가 n+1개 이므로 모순이 발생한다. 따라서 어느 한 상자에는 두 개 이상의 비둘기가 존재하게 된다.
관련 예제
-
13명의 사람이 있을 때 생일이 같은 달인 사람이 최소 2명 존재한다.
->비둘기: 사람들,상자: 1월 ~ 12월 -
영어 단어 27개를 뽑으면 그 중에 같은 문자로 시작되는 단어가 있다.
->비둘기: 영어 단어,상자: 알파벳 수 -
학교 전공이 4개이고 신입생이 5명이라면 적어도 2명은 같은 전공을 선택하게 된다.
->비둘기: 신입생 수,상자: 전공 수
