더블릿 5계단에도 있긴 있지만..... 조금 보충해봅니다.
비둘기 집 원리는 이해 하기는 간단합니다.
마리의 비둘기가 있고
개의 집이 있다면 적어도 두 마리의 비둘기가 들어가 있는 집이 존재한다는 원리입니다.
예제:
100보다 작거나 같은 11개의 양의 정수로 이루어져 있는 집합
가 있다.
일때
를 만족하는 쌍
가 존재한다는걸 증명하시오.
증명:
함수를 정의 합니다.
그렇다면 이 함수의 치역은 1-10 까지의 정수가 됩니다.
그런데 집합
에는 총 11개의 양의 정수가 있으니 비둘기집 원리에 따라
가 성립하는 서로 다른
가 존재합니다.
이므로
가 성립합니다.
또한
이므로
가 성립합니다.
즉
가 증명되었습니다.
그런데 이 원리를 다음과 같이 확장 할수도 있습니다.
Generalized Pigeonhole Principle
마리의 비둘기가 있고
개의 집이 있다면 적어도
마리의 비둘기가 들어가 있는 집이 존재한다.
증명:
귀류법으로 증명 가능합니다.
각 집에 최대
마리의 비둘기가 들어가 있다고 가정 합니다.
그렇다면 모든 비둘기 수는 최대
마리가 됩니다.
하지만
이므로, 다음과 같은 식이 성립합니다.
모순이므로, 적어도
마리의 비둘기가 들어가있는 집이 존재 한다는게 증명 되었습니다.
P.S. 제가 만들었던 줄 다리기 문제도 다이나믹 프로그래밍으로도 해결 가능하지만 비둘기집 원리를 이용한 brute-force 방법으로도 풀수 있습니다.
