비둘기집 원리

목차

예제
비둘기집 원리의 일반화

본문내용

비둘기집 원리는 n마리의 비둘기가 m개의
비둘기집에 들어가 있고 n > m이면, 두 마
리 이상의 비둘기가 들어가는 비둘기집이
적어도 하나는 존재한다는 원리를 말한다.
다시 말하자면, m개의 비둘기집에 하나에
한마리씩 비둘기를 넣으면, 최대 m마리가
들어갈 수 있으므로 거기에 한 마리를 더
넣으려면 이미 넣은 곳에 하나 더 넣어야
한다는 말이다.


예제
① 서울에는 머리카락의 수가 같은 사람이 최소한 두 명 존재한다.. 왜냐하면 일반적 인 사람의 머리카락 수는 15만개이다. 그러므로 100만개 이상의 머리카락을 가진 사람은 없다고 가정해도 무리가 없다. 서울에는 1000만 명 가량의 사람이 있으므 로, 서로 다른 머리카락의 개수를 서로 다른 비둘기집으로 보고, 서울에 사는 사람 각각을 머리카락의 개수에 따라 서로 다른 비둘기집에 할당하면, 같은 머리카락 개 수를 가진 사람이 반드시 존재한다는 것을 알 수 있다.

② 소프트볼을 하고 싶어하는 5명의 사람 있다고 할때, 서로 같은 팀에서 경기를 하 고 싶어하지 않지만 팀은 4개 뿐인 경우를 생각해볼 수 있다. 만약 이 사람들이 서 로 다른 팀에 들어가고 싶어할 경우, 비둘기집의 원리에 의해 5명의 사람을 한 팀 에 한명씩 4개의 팀으로 나누는 것은 불가능하다는 것을 알 수 있다.

참고자료

· 없음