이산수학) 비둘기집 원리

안녕하세요? 오랜만에 포스팅합니다. 

최대한 정확하고 유용한 그리고 간결한 정보만 전달하는게 이 블로그를 개설한 취지에 맞다고 판단하여 글을 쓰다 구성이 마음에 들지 않으면 지우고 부족한 부분을 다시 공부하고 이를 반복하다보니 포스팅 간격이 의도치 않게 길어졌습니다.

본론으로 들어가서, 오늘은 '비둘기 집의 원리'에 대해 포스팅해보고자 합니다.

비둘기집의 원리란, n+1 마리의 비둘기와 n 개의 상자가 있을 때, 적어도 상자 1 곳은 비둘기가 2마리가 들어있다는 원리입니다.

[비둘기가 집을 찾아가기 전]

[비둘기가 집을 찾아가고 난 후]

이 원리는 너무나 당연하면서도 굉장히 강력합니다.

대표적인 예를 통해서 추가 설명을 이어가겠습니다.

위키백과에 있는 용례를 살짝 바꿔봤습니다.

■ 서울에는 1000만 명 가량의 사람이 있고, 사람의 머리카락의 개수는 보통 10만개이다. 이 중 같은 머리카락 개수를 가진 사람이 존재함을 증명하시오.

이를 비둘기집 원리를 통해서 증명해보겠습니다.

서울에 사는 1000만 명의 '사람'을 '비둘기'로 치환하고, 사람의 '머리카락의 개수'를 '상자'로 치환시키겠습니다.

머리카락이 1개인 사람은 상자 1에 집어넣고, 머리카락이 2개인 사람은 상자 2에 집어 넣습니다. 이렇게 하다보면 머리카락이 10만개인 사람은 상자 10만에 들어가게 될 것이고, 이 후 10만+1번째인 사람이 들어가게 될 상자는 이미 누군가가 존재하고 있는 상자에 들어가게 됩니다.

같은 상자에 들어가있다는 것은 같은 머리카락의 개수를 가지고 있음을 의미함으로, 따라서 같은 머리카락의 개수를 가진 사람이 존재함을 증명할 수 있습니다.

이렇게 당연하지만 강력한 원리인 비둘기집 원리를 알아보았습니다. 

이상으로 포스팅을 마치겠습니다.

감사합니다.