N+1개의 물건을 N개의 상자에 넣으면,
적어도 하나의 상자에는 두 개 이상의 물건이 들어간다.
오늘은 당연하면서도 다양한 곳에 적용할 수 있는 비둘기집 원리에 대해 알아보겠다.
증명
N+1개의 물건과 N개의 상자가 있을 때, 각 상자에는 한 개 이하의 물건만 들어가있다고 가정해보자.
각 상자에는 최대 1개의 물건이 있을 것이므로, 총 물건의 수는 많아야 N개이다.
그런데 N+1개의 물건이 있으므로, 이는 모순이다.
따라서 N+1개의 물건과 N개의 상자가 있을 때, 적어도 하나의 상자에는 두 개 이상의 물건이 들어간다.
귀류법을 이용해 쉽게 증명하였다.
귀류법이란 명제의 결론이 부정임을 가정했을 때 모순 발생함을 보여 명제가 참임을 증명하는 방법이다.
예시
- 한 반에 13명 이상의 학생이 있다면, 최소 2명 이상의 학생은 태어난 달이 같다.
- 5켤레(낱개로 10개)의 양말 중 6개를 고르면 적어도 하나 이상의 짝이 맞는 양말 쌍이 있다.
이 외에도 정말 다양한 곳에서 비둘기집 원리를 확인할 수 있다.
관련 문제
PS에서 비둘기집 원리는 주로 조합을 찾을 때 찾는 횟수를 제한해 시간 효율성을 높이는 용도로 사용된다.
어려운 문제일수록 비둘기집 원리를 적용할 수 있음을 찾아내고 증명하기가 어렵다.
따라서 아래 문제들을 비둘기집 원리를 적용해야 함을 알고 풀면 원래의 난이도보다 현저히 쉬워질 수 있음에 유의하자.
- [24228] 젓가락: 비둘기집 원리 그 자체인 문제
- [20529] 가장 가까운 세 사람의 심리적 거리: 2개 이상인 박스가 아니라 3개 이상인 박스가 있으려면..?
- [1323] 숫자 연결하기: 모듈로(나머지) 연산의 특성 활용 + 비둘기집 원리
- [21099] Four XOR: XOR 연산의 특성 활용 + 비둘기집 원리
코드는 여기에서 확인할 수 있다.
