[이산수학]비둘기 집 원리 (Pigeonhole principle)

비둘기 집 원리 (Pigeonhole principle)

 

m < n 일 때 n 마리의 비둘기를 m 개의 비둘기 집에 배당하면,

최소 하나 이상의 비둘기 집에 둘 이상의 비둘기가 배당된다.

 

: 집이 4개밖에 없는데 비둘기가 5마리라면,

  적어도 한 집에는 2마리 이상이 있어야 한다.

 

언뜻보면 당연해보이는 비둘기 집 원리(Pigeonhole principle)는 실제로

강력한 증명 기술로 사용될 수 있다.

 

Pigeonhole principle의 원리를 확장해보자.

n 마리의 비둘기가 m 개의 비둘기 집에 배당될 때,

하나 이상의 비둘기집은 최소 [(n-1)/m]+1 마리의 비둘기가 배당되어야 한다.

이 식을 가지고서 여러 가지를 증명할 수 있다.