비둘기집의 원리 (1편) - 간단하지만 강력하다!

1. 비둘기집의 원리란 무엇인가?

그림을 보면, 5마리의 비둘기와 4개의 집이 있다. 4개의 집에 5마리의 비둘기를 알맞게 넣어주려면, 그 어떤 방법을 써도 적어도 하나의 집에는 2마리 이상의 비둘기를 넣어야 함을 알 수 있다. 이 것이 바로 비둘기집의 원리인데, 조금 더 수학적으로 써보면 다음과 같다.

비둘기집의 원리. 개의 물품을 개의 상자에 집어넣을 때, 만약 이라면 적어도 하나의 상자에는 이상의 물품이 들어가야 한다.

증명 은 사실 할 필요가 없을 정도로 간단하다. 일단 초등학교 때 배운 정수의 나눗셈 알고리즘을 떠올려보자. 을 으로 나눌 경우

을 만족하는 나머지 이 존재한다. 만약 모든 상자가 최대 개의 물품 만을 담고 있다면,

가 되어 모순이 일어나므로, 적어도 하나의 상자는 이상의 물품이 들어가야만 한다.

2. 비둘기집의 원리는 어디에 사용되는가?

2-1. 유리수와 순환소수

초등학교와 중학교 때 배운 유리수와 소수 (decimal) 간의 관계를 배웠다. 모든 유리수는 기약분수 꼴로 나타내었을 경우, 유한소수이거나 순환소수로 표현됨을 배웠다. 이제 비둘기집의 원리를 이용하여 (자명하다고 믿었던?!) 사실을 증명해보자.

유리수와 소수(decimal) 정리. 모든 유리수는 항상 유한소수이거나 순환소수이다. 또한 유리수가 순환소수가 아닌 유한소수로 표현되는 경우는 기약분수로 나타내었을 때, 분모의 소인수가 또는 만 존재하는 경우이다.

음의 유리수는 -부호만 붙이면 되므로 양의 유리수로 한정해서 생각해보자. 먼저 임의의 양의 유리수는 항상 서로소인 두 자연수 에 대해

꼴로 나타낼 수 있다.

Step 1. 정수의 나눗셈 알고리즘에 의해

를 만족하는 몫 와 를 만족하는 나머지가 존재한다. 이 때 만약 이라면,

이는 소수 (decimal) 부분이 없는 정수이다. (즉 유한소수)

Step 2. 만약 이라면,

을 만족하는 정수 과 나머지 가 존재한다. 이 때, 은 무엇을 뜻할 까?

을 만족한다. 즉 이는 곧

의 꼴로 나타낼 수 있다는 것이고, 이므로 은 의 소수 첫째 자리 자릿수를 나타냄을 알 수 있다.

Step 3. 규칙을 찾았으므로 귀납적으로 몫과 나머지를 정의해보자. 수열 을 다음과 같이 정의한다.

주목해야 할 것은, 나머지의 성질에 의해 모든 은 를 만족한다는 것이다.

Step 4. 가 유한소수가 되는 경우에 대해 생각해보자. 그러면 을 만족하는 어떤 음이 아닌 정수 이 존재해야 한다. (왜일까요...?) 그러한 일 경우, Step 1에서의 경우이므로 더 이상의 논의는 무의미하다. 만약 일 경우,

이 성립한다. 의 정의를 살펴보면,

를 만족하므로, 은 의 값들만을 가질 수 있다. (Step 3의 관찰과 일치!!!). 따라서

이라면, 는 모두 소수 (prime) 이므로 무조건 가 성립해야한다. 그런데 이러한 성질을 만족하는 최소의 은 으로 보다 작다는 사실과 모순이다. 따라서 는 또는 중 적어도 하나를 소인수로 가져야 한다! 더욱이, 가 와 외의 소인수 을 가진다면,

이므로 은 절대로 이 될 수 없다. 따라서

가 유한소수일 조건은 가 오직 또는 만을 소인수로 가질 조건과 동치이다.

Step 5. 가 무한소수가 되는 경우에 대해 생각해보자. 그렇다면 어떠한 경우에도 을 만족한다. 여기서! 비둘기집의 원리를 사용해보자. 은 무한수열이고, 가질 수 있는 값은 로 한정된다. 따라서, 비둘기집의 원리에 의해 를 만족하는 서로 다른 두 자연수 쌍 가 존재한다. 집합

를 정의하면, 비둘기집의 원리가 임을 보장하므로 자연수의 정렬원리 (Well Ordering Principle of Natural numbers) 에 의해 최소원소 가 존재한다. 다시

로 정의하면, 자연수의 정렬원리에 의해 이 집합의 최소원소 가 존재한다. 은 온전히 에만 의존하고, 도 온전히 에만 의존하므로, 은 영원히 반복, 즉 순환 할 것이다. 따라서 우리가 원하던 순환소수 표현은

이다!.

2-2. 못믿겠으니 예시를 들어주세요.

예를 들어서 인 경우를 생각해보자. Step 3에서 정의한 수열 을 구하는 Python 코드는 다음과 같다.

def dec_period(p, q, n):
    for i in range(n+1):
        m = p // q
        r = p % q
        print ("%3d %3d %3d" % (i, m , r))
        p = 10 * r    
    return
#----------------------------------------------#
dec_period(19, 62, 20)

이제 출력값을 살펴보면

0	0	19
1	3	4
2	0	40
3	6	28
4	4	32
5	5	10
6	1	38
7	6	8
8	1	18
9	2	56
10	9	2
11	0	20
12	3	14
13	2	16
14	2	36
15	5	50
16	8	4
17	0	40
18	6	28
19	4	32
20	5	10

다음과 같다. Step 5에서 내린 정의들에 대입하여 보면, 이 됨을 알 수 있고 따라서 의 순환소수 표현은

이다. 깔끔!

2-3. 조밀집합과 비둘기집의 원리

굉장히 뜬금없지만, 무한을 다루는 해석학의 영역에서도 비둘기집의 원리는 사용된다. 임의의 무리수 에 대해 다음 정리를 증명하여 보자.

Theorem. 임의의 무리수 에 대해, 집합

는 의 조밀 부분집합이다. (단, )

Proof.
먼저 이므로 이어야만 한다. 따라서 주어진 자연수 에 대해,

은 모두 다른 값을 가지고 0이 아니다. 이제 폐구간 을 개의 구간으로 균등하게 자른다.

이제, 각 들을 개의 구간에 집어 넣는 경우를 생각해본다면! 비둘기집의 원리 에 의해 적어도 어느 한 구간 내에는 서로 다른 두 개의 값이 들어가 있음을 알 수 있다. 다시 쓰면, 이면서 을 만족하는 가 존재한다.

를 만족하는 적당한 정수 를 잡으면,

가 성립한다. 을 굉장히 크게 잡으면, 은 양수이면서 동시에 한없이 작아지므로, 이를 통해 은 의 극한점 (limit point) 임을 알 수 있다.

임의의 점 을 잡는다.

1. 만약 이라면, 0이 극한점이므로 자동적으로 도 의 극한점이 된다.

1. 만약 () 이라면,

을 정의한다. 은 의 정수배 가 보다 작아지는 값 중 최대를 의미하므로,

가 성립하며 부등식 에 의해 이러한 또한 의 극한점 (limit point) 이 됨을 알 수 있다. 따라서 이므로 는 의 조밀 부분집합이다. Q.E.D

눈여겨볼 성질은 집합 는 가산집합 (countable) 이면서 0을 제외한 그 어떤 유리수도 포함하지 않는다는 것이다. 가 의 조밀부분집합임을 자명한 (???) 사실로 받아들인다면, 집합

은 아마도 가장 간단하게 만들 수 있는 비자명한 의 조밀부분집합일 것이다.

3. 결론

비둘기집의 원리는 간단해 보이지만 근본적인 것들을 증명하는데 꼭 필요한 아이디어이다. 이산수학이나 조합론 에서 뿐만 아니라 해석학과 대수학에서도 종종 등장하는 아이디어이므로 알아두면 언젠가는 써먹는다. 다음 포스팅에서는 비둘기집의 원리를 사용한 예시들을 더 다루어보겠다.