하나고 조계성 쌤의 재미난 수학세계 - 배열 원리 풀어주는 '비둘기집의 원리'
공원에서 비둘기 21마리가 한가롭게 놀고 있다. 밤이 되자 각자 잠을 청하기 위해 공원 한쪽에 마련된 집으로 돌아가려고 한다. 그런데 비둘기 집에는 방이 20개밖에 없다. 21마리의 비둘기 모두에게 방이 하나씩 돌아가지 않으므로 비둘기 중 적어도 2마리는 한 방에 같이 들어가 비좁게 잠을 잘 수밖에 없다.
이것은 독일의 수학자 디리클레가 수학 문제의 해결에 사용한 원리로 ‘비둘기 집의 원리’ 또는 ‘디리클레의 서랍 원리’ 등으로 불린다. 이 원리의 일반적 개념은 ‘n개의 비둘기 집에 (n+1)마리 이상의 비둘기가 들어간다면, 두 마리 이상의 비둘기가 들어간 비둘기 집이 적어도 하나 있다.’는 논리이다.
이 원리는 지극히 당연하고 사소하게 보인다. 하지만 이 원리를 이용하면 아주 복잡해 보이거나 도저히 풀 수 없어 보이는 문제도 간단하게 해결할 수 있는 경우가 있다.
이 원리는 이산수학에서 주요 관심사 중 하나인 배열이나 패턴의 존재성 문제를 해결하는 강력한 도구가 되기도 한다. 비둘기 집의 원리를 이용하여 다음 문제를 풀어보자.
문제 1 그림과 같이 한 변의 길이가 2인 정사각형 내부에 임의로 5개의 점을 찍을 때 두 점 사이의 거리가 √2 보다 크지 않은 점들이 반드시 존재함을 보여라.
해설 그림과 같이 정사각형을 4등분해 5개의 점을 찍을 때 적어도 2개의 점은 같은 방에 들어가게 된다. 작은 정사각형의 대각선 길이는 √2이므로 같은 방에 들어간 두 점 사이의 거리는 √2 보다 크지 않다. 이 문제를 통해 워밍업이 됐다면 비둘기 집을 좀 더 기술적으로 나눠서 해결하는 문제에 도전해보도록 하자.
문제 21에서 62까지의 자연수 중 임의로 6개를 고르면 이 중에는 m≤2n을 만족하는 자연수 m,n이 반드시 존재함을 보여라.
해설 다음과 같이 비둘기 집을 나타내는 각 집합의 원소는 최대수가 최소수의 2배가 되도록 하자.
수식1 5개의 집합에서 6개의 원소를 선택해야 하므로 적어도 2개의 원소는 같은 집합 안에서 선택된다. 즉, m≤2n을 만족하는 자연수 m,n 이 반드시 존재한다. 위에서 언급한 ‘n개의 비둘기 집에 (n+1)마리 이상의 비둘기가 들어간다면, 두 마리 이상의 비둘기가 들어간 비둘기 집이 적어도 하나 있다.’ 의 비둘기 집의 원리를 좀 더 일반화하면 다음과 같다.
m≥n 일때, m마리의 비둘기를 n개의 비둘기 집에 아무렇게나 넣으면 하나의 비둘기 집에는 적어도 k 마리 이상의 비둘기가 있게 된다. 여기서 k는
수식 2 단, ［x ］는 x를 넘지 않는 최대정수를 뜻한다.
조계성 선생님은 현재 하나고 에 근무하신다. 명덕외고, 대성학원에서도 수학을 가르쳤다. 전국연합모의고사 출제위원도 맡고 있다. 서울대에서 수학교육을 전공했으며 연세대에서 수학교육으로 석사학위를 받았다. 저서로는 ‘개념+유형 시리즈’ 등 다수가 있다.
