비둘기집 원리에 대해 알아 봅니다.

문제를 풀다 보면 비둘기집의 원리에 의해서 이렇게 된다고 정의를 하는 문제 유형들이 많이 나오는데.

오늘은 비둘기집의 원리가 무엇인지 확인을 해 보겠습니다.

 

비둘기집의 원리는 정말 단순합니다.

비둘기집은 2개이고 비둘기는 3마리입니다.

비둘기가 저녁에 잠을 자기 위해 비둘기 집에 들어가야 되는데...

그렇다면 반드시 한개의 비둘기집에는 비둘기가 2마리 이상이 존재하게 된다는 원리입니다.

 

가령 1번집에 비둘기 3마리 2번집에 0마리, 혹은 1번집에 2마리 2번집에 1마리, 1번집에 1마리 2번집에 2마리,1번집에 0마리 2번집에 3마리 이렇게 4가지 경우의 수 밖에 없는데 이 4가지 경우의 수에서 반드시 한개의 집에는 2마리 이상이 존재 하게 된다는 것인데...

 

이러한 정의를 위키백과에서는 다음과 같이 귀류법으로 정의 하고 있습니다.

n개의 비둘기집과  n+1마리의 비둘기가 있다고 가정한다.  만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야  n마리의 비둘기가 존재한다. 그런데 비둘기는 모두  n+1마리이므로, 이것은 모순이다. 따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.

이것을 일반화된  원리로 정의를 하면 다음과 같이 정의를 합니다.

n개의 별개의 사물을 m개의 용기에 나누어 담으면 적어도 한 개의 용기는 n/m이상의 사물을 담고 있어야 한다.

 

확률론적으로 일반화된 원리로 정의를 하면 다음과 같이 정의를 합니다.

1/m의 균일한 확률로 n개의 비둘기를 무작위로 m개의 비둘기집에 넣었다면 확률적으로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 된다.

 

이러한 비둘기집의 원리를 이용해 문제를 풀어 가는 유형을 살펴 보면 다음과 같습니다.

 

어느 지역은행은 고객들에게 ATM 카드를 사용할 때 필요한 4자리 코드를 신청하도록 하였다. 코드의 첫 두 자리는 알파벳 문자이어야 하고, 세 번째와 네 번째 두 자리는 숫자로 구성되어야 한다. 이 은행에는 75,000명의 고객이 있다. 적어도 두 명의 고객은 같은 코드를 선택하게 됨을 증명하여라.

이러한 유형의 문제를 풀어 나가기 위해서는 어떤 집합이 동일한 성질을 갖는 원소를 적어도 두 개 갖는다는 것을 증명하기 위해서 먼저 이 집합의 원소들이 갖는 서로 다른 성질의 가짓수를 세고, 다음으로 원소들의 개수를 센다. 
비둘기 집의 원리는 만약 원소의 개수가 성질의 가짓수보다 많으면 적어도 두 개 이상의 원소는 동일한 성질을 갖는다는 것을 의미하기 때문에 다음과 같은 문제를 해결 할 수가 있습니다.

 

먼저 코드를 만드는 경우가 몇가지인지 먼저 원소의 갯수를 세어 보면

앞의 두자리가 알파벳이므로 26 * 26, 뒤의 두자리가 숫자이므로 10*10 이므로 모든 경우는 26 * 26 * 10 * 10 인것을 확인 할 수 있습니다.

 

이것을 계산하면 67600 가지수가 나오는데 고객의 수는 75000명입니다.

따라서 비둘기집의 원리에 의해서 적어도 두명 이상은 같은 코드를 사용할 수 밖에 없게 됩니다.

 

또다른 유형의 문제는 다음과 같은 유형이 있습니다.

159개의 팀이 있다.  만약 하나의 리그에 많아야 8팀이 포함될 수 있다면, 최소한 얼마나 많은 리그를 만들어야 하는가?  만약 10팀, 또는 12팀이 포함될 수 있다면 최소한 얼마나 많은 리그를 만들어야 하는가?

이러한 유형의 문제는 

n개의 별개의 사물을 m개의 용기에 나누어 담으면 적어도 한 개의 용기는 n/m이상의 사물을 담고 있어야 한다.

는 원리를 이용하면

159/8  이상이므로 20개의 리그

159/10 이상이므로 16개의 리그

156/12 이상이므로 14개의 리그 

라는 것을 확인 할 수가 있습니다.

 

 

이렇게 비둘기집의 원리를 응용해서 많은 문제들이 출제 되고 있는데요.

그 중에도 비둘기 집의 원리는 어떤 문제가 풀릴 수 없다는 것을 증명하기 위해 사용됩니다.

전형적인 예는 자동차 번호판 위에 표시할 문자와 숫자의 형식을 결정하는 것이다. 번호판을 설계할 때 반드시 고려해야 할 사항은 등록된 모든 차량들이 서로 다른 문자-숫자 형식을 가질 수 있도록 하기 위해서는 얼마나 오랜 기간 동안 사용할 것인가와 번호판 위에 문자와 숫자를 어떤 형식으로 나타내야 하는가 하는 문제입니다.

자동차 번호판의 수를 세는 문제는 각 자리를 정해진 종류의 기호로 나타내므로 곱의 법칙을 적용하는 간단하고 좋은 예제입니다.

 

 

오늘은 비둘기집의 원리와 응용하는 문제에 대해 알아 보았는데요.

비둘기집의 원리는 컴퓨팅 과학에서 이것이 가능한지 불가능한지 판단을 하기 위한 중요한 요소 중의 하나입니다.

가령 첫번째 문제와 같이 은행의 고객들에게 ATM 카드를 발급해야 되는데...

서로 다른 고객이 같은 카드 번호를 소지하고 있다고 하면 중대한 오류가 발생할 것입니다.^^

 

프로그램을 설계할 때 많은 부분을 고려해야 하지만 특히나 이런 부분은 중요한 부분 중 하나입니다.

 

비둘기집의 원리 어렵지는 않지만 컴퓨팅 과학에서는 중요하다는 사실...

놓치지 않고 잘 챙기시길 바랍니다.^^

 

인천 서구 컴퓨터학원 - 원당컴퓨터학원