Pigeon Hole Principle   비둘기집 원리

1. 비둘기집 원리

  ㅇ n,k (n > k) 일 때, n 마리의 비둘기를 k 개의 비둘기집에 넣을때, 
     - 적어도 한 집에는 2 마리 이상 들어간 집이 있게 됨

  ㅇ 또는, n(A) > n(B) 이면, 
     - 유한 집합 A에서 B로 가는 단사 함수가 될 수 없음
        . 단사 함수 : B의 각 원소에 대응하는 A의 원소가 기껏해야 하나 만 갖을 때 (1:1 함수)

  ㅇ 비둘기집 원리는, 배열의 존재성 문제를 증명할 때 필요함


2. 비둘기집 원리의 의의

  ㅇ 단순하지만 강력한 논리 도구
     - 쉽게 이해할 수 있지만, 수학적 엄밀한 증명에 자주 활용됨
  ㅇ 존재 증명의 도구
     - 특정한 구조, 패턴, 중복이 반드시 존재함을 보장하는 존재성 증명(existence proof)에 자주 쓰임 
  ㅇ 최소/최대 보장 원리
     - 어떤 상황에서 최소 몇 개는 반드시 겹친다는 보장을 제공하여,
     - 하한(lower bound) 추정에 핵심적으로 사용됨