비둘기 집의 원리
전형적인 예로 다음을 알아봅시다.
n은 자연수이고, 만약 (n+1) 마리의 비둘기와 n 개
의 비둘기집이 있다면, 반드시 어떤 비둘기집에는 두
마리 이상의 비둘기가 있다.
|
위의 원리를 함수의 형식으로 표현하자면 다음과 같다.
X, Y 는 공집합이 아닌 두 집합이고, 원소의 개수가 각각 X는
(n+1) 개, Y 는 n 개 이다. 그러면 함수
는 단사함수 ( injective function )가 아니다.
비둘기집 원리는 그 내용은 단순하지만 많은 다양한 문제에
적용될 수 있는 중요한 원리이다.
예제1. 한 변의 길이가 2 인 정사각형에 5 개의 점이
있으면, 두 점 사이의 거리가 √2 보다 작은 두 점이
반드시 존재한다.
|
풀이.
네 개의 작은 정사각형으로 자르면, 비둘기집 원리에 의하여 5개의 점
중에서 반드시 어떤 2 점은 같은 작은 정사각형 안에 있게 된다. 따라서,
그러한 두 점은 두 점 사이의 거리가 √2 보다 작게 된다. ?
예제 2. 한 변의 길이가 1 센티미터인 정육각형 안에
임의로 일곱 개의점을 찍으면 이들 가운데 두 점 사이
의 거리가 1 이하인 것이 적어도 한 쌍 있다.
|
풀이. 이것을 증명해 보면 다음과 같다. 먼저 다음 그림과 같이
정육각형은 한 변의 길이가 1 센티미터인 여섯 개의 정삼각형으로 나눈다.
그러면 적어도 하나의 정삼각형에는 두 개 이상이 들어가게 된다. 따라서
같은 삼각형안에 있는 두 점 사이의 거리는 1 이하가 된다. ?
예제 3. 임의의 양의 정수 열한 개 중에는 두 수의 차가
10의 배수가 되는 짝이 적어도 한 쌍이 있다.
|
풀이. 임의의 양의 정수의 1의 자리 수는 0부터 9까지 열까지 ( 비둘기 집
의 수 ) 뿐이므로 열 한 개 (비둘기 수)의 양의 정수 중에는 1의 자리의 수가
같은것이 적어도 한 쌍 있다. 이 때 이 두 수의 차는 10의 배수이다. ?
풀이. 8 명의 학생이 있고, 요일은 모두 7 개이므로, 비둘기집 원리에
의하여 생일의 요일이 같은 학생들이 반드시 있다. ?
문제 1. 유리수는 반드시 순환마디의 길이가 유한인 무한
소수로 표시할 수 있음을 보여라. 예를 들어, 9 / 7 는
순환마디의 길이가 7 (0 포함)을 넘지 않는 무한소수임을
보이시오.
|
 ?
문제 2. 한 변의 길이가 1 인 정사각형에 9 개의 점이
있으면, 최대넓이가 1/8 인 삼각형을 이루는 세
점이 반드시 존재함을 보이시오.
|
문제 3. 한 변의 길이가 2 인 정삼각형의 모양의 판에
5개의 핀을 꽂으면,두 핀 사이의 거리가 1 보다 작은
두 핀이 반드시 존재함을 보이시오.
|
풀이. 먼저 m 개의 수를 a1, a2, ... am 이라 하고 새로운 m 개의 수
a1, a1+ a2, a1+ a2 + a3, a1+ a2 + ... +am 을 만든다. 이를 m개 수
중에서 m의 배수인 것이 있으면 그것이 구하는 수의 합이다.
만일 m의 배수인 것이없으면, m으로 나눈 나머지는 1, 2, ..., (m - 1)
뿐이고, 위에 만든 수는 모두m개 이므로, 위의 수 중에는 나머지가 같은
것이 반드시 있다. 만일 두 수 a1+ a2 + ... +ai 와 a1+ a2 + ... +aj 의
나머지가 같다고 하면, 두 수의 차
(a1+ a2 + ... +ai) - ( a1+ a2 + ... +aj )
= ai+1+ ai+2 + ... + aj 가 구하는 m의 배수이다. ?
예를 들어 m = 5 일 때를 생각해 보자.
임의의 다섯 개의 수를 3 , 4 , 7 , 8 , 9 라 하면 ,
3, 3 + 4 = 7, 3 + 4 + 7 = 14, 3 + 4 + 7 + 8 = 22,
3 + 4 + 7 + 8 + 9 =31
과 같은 다섯 개의 수를 5로 나누면 나머지는 각각 3, 2, 4, 2,1 이다.
이 때 두 수의 차
( 3 + 4 + 7 + 8 ) - ( 3 + 4 ) = 15
는 5 의 배수이다. 또, 순서를 바꿔서 구하면
3 + 4 + 8 , 3 + 8 + 9 , 4 + 7 + 9
등도 5의 배수임을 알 수 있다.
연구문제. 126 보다 크지 않은 7 개의 서로 다른
자연수를 택하면 그 중에서 두 수 x, y 는 반드시
조건
1 〈 y/x ≤ 2
를 만족함을 보이시오.
|
풀이. 먼저 비둘기집 원리를 적용하기 위하여 126 보다 크지 않은
자연수를 6 개의 묶음으로 나눌 수 있는 방법을 알아보아야 한다.
주어진 문제에서는두 수 x, y 의 몫의 조건
1〈 y/x ≤2
으로주어졌으므로,
1 부터 시작하여몫의 조건을 만족하려면 { 1, 2 },
3 부터 시작하여 몫의 조건을 만족하려면 { 3, 4, 5, 6 },
7 부터 시작하여 몫의 조건을 만족하려면
{ 7, 8, 9, 10, 11, 12, 13, 14 }
이와 같이 126 까지 계속하면 6 개의 분할
{ 1, 2 }, { 3, 4, 5, 6 }, { 7, 8, 9, 10, 11, 12, 13, 14 }
{15, 16, 17, ..., 30 }, { 31, 32, ...62 },
{ 63, 64, ..., 126 }
따라서 7 개의 서로 다른 자연수를 택하려면 비둘기집 원리에 의하여
위 6 개의 분할 중에서 어떤 한 분할에서는 반드시 두 개 이상의 숫자를 고를
수 밖에 없다. 따라서 그 두 숫자를 각각 x, y 라 하면, 주어진 조건
1〈 y/x ≤2
를 만족한다. ?
문제 4. 위 문제를 이용하여, 7 개의 서로 다른 자연수를
택하여 그 중에서 두 수 x, y 는 반드시 조건1〈 y/x ≤3
를 만족하려면 얼마보다 작은 수를 골라야 하는가
알아보시오.
|
|
