어두운 곳에 보관된 양말을 꺼내려 하는데, 양말장에는 검은색과 흰색 두 종류의 양말이 뒤섞여 있다. 색을 보지 않고 양말장에서 꺼내서 밝은 곳에 이르러서야 양말을 확인할 수 있다. 무심결에 가져왔다가는 짝이 맞지 않아 다시 가지러 가는 낭패를 볼 수 있다. 그렇다고 양말장의 양말을 통채로 가져올 수도 없는 법. 양말을 최소한 몇 짝 가져와야 짝이 맞는 양말을 항상 찾을 수 있을까?
누구나 간단하게 3짝이라고 말할 것이다. 일단 두 개를 꺼낼 때 같은 색이 나오면 다행이고 흑, 백이 한 짝씩 나오면 이후에 세 번째 것은 어떤 색이 나오든 짝이 맞게 된다. 색이라는 포지션은 2개이고 양말이라는 대상은 3개이므로 셋 중 둘은 같은 위치에 들어가야 한다.
이것은 비둘기 집의 원리[Pigeonhole principle]라 알려진 정리인데, 디리클렛의 상자원리[Dirichlet's Box Principle]등등의 다른 이름으로도 알려져 있지만 본질은 같다. 정리에 이러한 이름이 붙은 이유는 설명할 때 항상 비둘기 집에 들어가는 비둘기로 비유를 하기 때문인데, 간단하게 설명하자면 n+1 마리의 비둘기가 n 개의 집에 들어가려면 적어도 한 집에는 두 마리 이상이 들어가야 한다는 것이다. 참, 뭐 이런 당연한 소리를...ㅋㅋㅋ
이 원리는 어떻게 응용할 수 있을까? 이 원리에 대한 흥미를 주입하기 위해 자주 언급되는 예가 서울시민 중에는 머리카락의 개수가 정확히 같은 사람이 존재한다는 것에 대한 증명이다. 사람의 머리카락의 개수는 평균적으로 약 15만개이고 20만개 이상인 사람은 드물다고 한다. (이 지식에 대해 한참 검색해봤지만 출처 없음. 대충 추측컨대 그정도 될 듯.) 아무튼 따라서 비둘기 집이 넉넉잡아 30만개 있고, 비둘기가 서울시민만큼 있다면 그중 적어도 두 사람은 같은 머리카락 개수를 가져야 하는 것이다. 물론 대머리는 0 이므로 서울에 대머리가 두 명 있으면 증명 끝이긴 하지만, 서울시내에 대머리를 모두 빼더라도 아마 여전히 성립할 것이다. 20만과 1000만은 차이가 꽤 크니까. ㅋㅋ
다양하게 기괴한 응용이 가능한데 일전에 포스트한 R(3,4)의 증명도 넓은 의미로 비둘기 집의 원리라고 볼 수 있다. 비둘기 집의 원리로 다음과 같은 사실을 증명할 수 있다. 뒤로 갈 수록 난이도가 올라간다고 생각한다.
검색하다가 비둘기집의 원리와 관련된 재미있는 문제를 몇 개 더 찾았다.
누구나 간단하게 3짝이라고 말할 것이다. 일단 두 개를 꺼낼 때 같은 색이 나오면 다행이고 흑, 백이 한 짝씩 나오면 이후에 세 번째 것은 어떤 색이 나오든 짝이 맞게 된다. 색이라는 포지션은 2개이고 양말이라는 대상은 3개이므로 셋 중 둘은 같은 위치에 들어가야 한다.
이것은 비둘기 집의 원리[Pigeonhole principle]라 알려진 정리인데, 디리클렛의 상자원리[Dirichlet's Box Principle]등등의 다른 이름으로도 알려져 있지만 본질은 같다. 정리에 이러한 이름이 붙은 이유는 설명할 때 항상 비둘기 집에 들어가는 비둘기로 비유를 하기 때문인데, 간단하게 설명하자면 n+1 마리의 비둘기가 n 개의 집에 들어가려면 적어도 한 집에는 두 마리 이상이 들어가야 한다는 것이다. 참, 뭐 이런 당연한 소리를...ㅋㅋㅋ
이 원리는 어떻게 응용할 수 있을까? 이 원리에 대한 흥미를 주입하기 위해 자주 언급되는 예가 서울시민 중에는 머리카락의 개수가 정확히 같은 사람이 존재한다는 것에 대한 증명이다. 사람의 머리카락의 개수는 평균적으로 약 15만개이고 20만개 이상인 사람은 드물다고 한다. (이 지식에 대해 한참 검색해봤지만 출처 없음. 대충 추측컨대 그정도 될 듯.) 아무튼 따라서 비둘기 집이 넉넉잡아 30만개 있고, 비둘기가 서울시민만큼 있다면 그중 적어도 두 사람은 같은 머리카락 개수를 가져야 하는 것이다. 물론 대머리는 0 이므로 서울에 대머리가 두 명 있으면 증명 끝이긴 하지만, 서울시내에 대머리를 모두 빼더라도 아마 여전히 성립할 것이다. 20만과 1000만은 차이가 꽤 크니까. ㅋㅋ
다양하게 기괴한 응용이 가능한데 일전에 포스트한 R(3,4)의 증명도 넓은 의미로 비둘기 집의 원리라고 볼 수 있다. 비둘기 집의 원리로 다음과 같은 사실을 증명할 수 있다. 뒤로 갈 수록 난이도가 올라간다고 생각한다.
- 반지름이 10인 원형 다트에 다트를 7번 던지면, 꽂힌 위치 중 적어도 거리가 10 이하인 두 점이 존재한다.
증명
원을 부채꼴로 6등분하면 다트는 일곱개인데 원은 6개 조각으로 나누었으므로 두 개의 다트는 적어도 한 군데에 같이 들어가야 한다. 따라서 한 개의 부채꼴 안에 있는 두 다트는 거리가 10 이하일 수 밖에 ㅋ
- 좌표평면에서 두 좌표값이 모두 정수인 점을 격자점이라 한다. 격자점 다섯 개를 선택하면 그 중 중점이 다시 격자점이 되는 쌍을 항상 찾을 수 있다.
증명
홀수끼리 혹은 짝수끼리의 평균은 항상 정수이다. 좌표평면의 두 좌표값이 모두 정수라면 (홀, 홀), (홀, 짝), (짝, 홀), (짝, 짝) 이 네 경우 뿐이다. 다섯 개의 점을 선택하면 비둘기집의 원리에 의해 적어도 두 점은 홀짝이 동일하다. 그 두 점은 평균을 내도 여전히 정수이므로 중점은 격자점이 된다.
- 결혼식장에 참석했더니 몇 명의 사람이 모여 있었다. 그 중에는 아는 사람도 있고 모르는 사람도 있다. 각 개인마다 아는 사람의 숫자가 다를 것이다. 그러나 아는 사람의 수가 같은 두 사람이 반드시 존재한다. 어떻게 증명할까? (여기서 안다는 의미는 쌍방에 안면이 있다는 뜻이다. 나는 장동건을 알지만 장동건은 나를 모르므로 이런 경우를 배제한다.)
증명
모인 사람의 수가 n명 이라고 하자. 아는 사람의 숫자는 최소 0명에서 자신을 제외해야 하므로 최대 n-1명이다. 그런데 아는 사람이 n-1명인 경우와 0명인 경우는 동시에 발생하지 않는다. 따라서 아는 사람의 경우는 0에서 n-2까지 또는 1에서 n-1까지 총 n-1가지 경우이고 사람의 수는 n명이므로 비둘기 집의 원리에 의해 적어도 두 사람은 아는 사람의 수가 같다.
- 3의 거듭제곱 중에서 십진법으로 표시하여 끝자리가 001로 끝나는 수가 존재한다.
증명
31, 32, .... , 31001
위와 같은 수 1001개를 생각하자. 1000으로 나누었을 때 나오는 나머지는 1000개 뿐이므로, 비둘기 집의 원리에 의해 적어도 두 수의 나머지가 같다. 그 두 수를 3n, 3m ( n > m )이라 하면,
3n- 3m = 3m(3n - m - 1) 이고 3m과 1000은 서로 소이므로, 3n - m - 1이 1000의 배수이다.
따라서 3n - m은 십진법으로 끝자리가 001로 끝난다.
- 100 이하의 자연수 중 임의로 55개를 선택하면 그 중에는 차가 딱 9인 쌍, 10인 쌍, 12인 쌍, 13인 쌍이 반드시 존재하지만 신기하게도 11인 쌍은 존재하지 않을 수 있다. 왜 그럴까?
증명
개수가 적은 경우에 대해 생각해보자. 6 이하의 자연수가 있다면 (1, 4), (2, 5), (3, 6) 과 같이 짝을 지을 수 있다. 이 중 4개의 수를 선택한다면 비둘기집의 원리에 의해 한 쌍의 자연수가 반드시 선택되므로, 6 이하의 자연수 중 4개를 선택하면 반드시 차가 3인 쌍이 존재하는 것이다.
같은 방법으로 18의 배수를 단위로 잘라서 다음과 같이 총 46쌍을 만들어 준다.
(1, 10), (2, 11), ..... , (9, 18),
(19, 28), (20, 29), ..... , (27, 36),
....
(73, 82), (74, 83), .... , (81, 90), (91, 100)
이렇게 만들면 92부터 99까지 총 여덟 개의 수가 남는데, 이 여덟 개의 수를 먼저 고른다고 해도, 47개의 수를 더 골라야 한다. 그러면 비둘기 집의 원리에 의해 적어도 두 수는 한 쌍에서 동시에 고르게 되고, 그 두 수의 차는 9가 된다.
마찬가지로 (1, 11), (2, 12), .... (10, 20), (21, 31), (22, 32), .... , (90, 100) 이렇게 50쌍을 만들면 적어도 다섯 쌍의 수는 차가 10이 되는 수가 된다. 12와 13도 비슷하게 하면 48쌍과 네 개의 수가 남아서 적어도 세 쌍의 차가 12 또는 13이 된다.
그러나 11의 경우는 짝이 맞지 않는 수가 많아서 55개의 수를 선택해도 차가 11이 되지 않게 회피할 수 있다. 즉,
2~12, 24~34, 46~56, 68~78, 90~100 이와 같이 선택하면 어떤 두 수의 차도 11이 되지 않는다.
검색하다가 비둘기집의 원리와 관련된 재미있는 문제를 몇 개 더 찾았다.
- 50일간 매일 한 바퀴 이상 운동장을 돌았다. 총 82바퀴를 돌았을 때, 돈 회수가 총 17이 되는 연속한 날이 존재함을 증명하라.
증명
1일 부터 50일까지 누적해서 돈 바퀴 수를 ai라 하면, a1, a2, ...... , a50, a1 + 17, a2 + 17, ..... , a50 + 17 은 모두 100개의 수이고 모두 82 + 17 = 99 이하의 자연수이다. 따라서 적어도 두 수는 같다. ai와 ai + 17 은 항상 증가하는 수열이므로 (매일 한 바퀴 이상 돌았으니까) 각 ai와 ai + 17은 모두 다르다. 따라서 ar = as + 17 를 만족하는 r, s가 존재한다. 즉, s + 1 일부터 r 일까지 운동장을 돈 회수는 17바퀴이다.
- 서로 다른 일곱 개의 실수를 임의로 선택했을 때, 그 중
를 만족하는 두 실수 x, y가 항상 존재함을 증명하라.
증명
임의의 실수 x에 대해 x = tan Θ 을 만족하는 Θ를 -π/2 < Θ < π/2 범위에서 항상 찾을 수 있다. 선택된 일곱 개의 수 각각을 x1 .... x7이라 하면 각각 Θ1 .... Θ7이 존재해서 xi = tan Θi가 성립하게 만들 수 있다. 따라서 길이가 π인 그 구간을 6등분하면 비둘기 집의 원리에 의해 Θ1 .... Θ7 중 적어도 두 수는 같은 구간에 들어간다. 그 두 수를 Θi, Θj라 하면, (편의상 Θi > Θj라 두자) 삼각함수의 합의 공식에 의해이 성립한다.
- <x>는 x에서 x를 넘지 않는 최대의 정수를 뺀 값 즉, <x> = x - [x] 라고하자. 예를 들어 <4.4509> = 0.4509, <-4.4509> = 0.5491, <15/7> = 1/7, <√2> = √2 - 1이다. 양의 무리수 a에 대해 집합 Xa = { <na> | n은 자연수 }가 구간 [0,1) = { x | 0 ≤ x < 1 } 안에서 조밀(dense)함을 증명하라.
증명
이건 사실 예전 DC 수학갤러리에서 어느 분이 증명한 것을 보고 내 나름대로 좀 편집한 것이지만.... 기억을 더듬어 적어봄. ㅋ
다음의 사실에 주목한다.
사실 1. 정수 m에 대해 m<na> = <mna> (단, m<na> < 1)
사실 2. <<na> - <ma>> = < (n - m)a>
집합 Xa의 원소로 0으로 수렴하는 수열을 만들 수가 있다고 가정해보자. 즉, Xa의 원소 중에 0에 얼마든지 가까이 있는 것을 찾을 수 있다고 가정해보자.
[0,1)의 임의의 원소 b가 주어지면 적당히 0에 가까운 Xa의 원소를 골라서 정수배 해주면 사실 1에 의해 b에 얼마든지 가까운 Xa의 원소를 찾을 수 있다. 따라서 위 문제는 Xa의 원소 중에 0에 얼마든지 가까운 수를 찾을 수 있음을 증명하면 된다.
다음 n + 1 개의 수 <a>, <2a>, ..... , <(n + 1)a> 는 구간 [0,1) 을 n 등분했을 때 비둘기 집의 원리에 의해 차가 1/n을 넘지 않는 두 수가 존재한다. a가 무리수 이므로 어느 두 수도 같지 않다. 사실 2에 의해 그 차도 Xa의 원소이므로 얼마든지 0에 가까운 Xa의 원소를 찾을 수 있다.
쿼리의 결합 : UNION 으로 쿼리 결합하기
암호화 알고리즘 종류와 관련 용어
