집합론(Set theory)

비둘기집 원리(Pigeonhole principle)

n개의 칸에 n개보다 많은 물건을 넣으면 어떤 칸에는 반드시 두 개 이상이 들어간다. 당연한 말이 놀라운 결론을 만든다.

m > n \;\Rightarrow\; \text{어떤 칸에는 } \left\lceil \tfrac{m}{n} \right\rceil \text{개 이상}

먼저 보면 좋은 개념단사·전사·전단사

비둘기 $m =$ 마리가 비둘기집 $n =$ 칸에 들어갑니다. 어떻게 들어가든 가장 붐비는 칸에는 적어도 $\lceil m/n \rceil =$ 마리가 있습니다. 이번 배치에서는 마리입니다. 다시 넣기

빨간 칸은 두 마리 이상이 들어간 칸입니다.

함수⁠(function)⁠의 말로 하면, 큰 유한집합에서 작은 유한집합으로 가는 함수는 단사⁠(injective)⁠가 될 수 없습니다. 이 한 줄로 여러 사실이 나옵니다. 2월 29일까지 생일은 366가지이니, 367명이 있으면 생일이 같은 두 사람이 반드시 있습니다. "반드시"가 아니라 "그럴 가능성이 높다"로 물으면 훨씬 적은 수로 충분합니다. 365일에 고르게 태어난다고 가정하면 23명만 모여도 그럴 확률⁠(probability)⁠이 절반을 넘습니다(약 50.7%, 생일 문제⁠(birthday problem)⁠). 정수⁠(integer)⁠ $n+1$ 개를 고르면 $n$ 으로 나눈 나머지⁠(remainder)⁠가 같은 두 수가 반드시 있습니다(모듈러 연산⁠(modular arithmetic)⁠).

가장 멋진 응용은 디리클레의 근사 정리입니다. 무리수⁠(irrational number)⁠ $\alpha =$ 에 대해 $0, \alpha, 2\alpha, \dots, N\alpha$ 의 소수 부분(정수 부분을 버리고 남은 0과 1 사이의 값)을 둘레가 1인 원 위에 찍습니다( $N =$ ). 점 $N+1$ 개를 호 $N$ 개에 넣으니 두 점이 $1/N$ 보다 가까이 붙습니다.

가장 가까운 두 점을 빨갛게 이었습니다.

두 점 $j\alpha$ 와 $k\alpha$ 가 가깝다는 것은 $q = |k - j|$ 에 대해 $q\alpha$ 가 정수 $p$ 에 가깝다는 뜻입니다. 지금은 $q\alpha$ 와 $p$ 의 차가 $1/N$ 보다 작으니, 양변을 $q$ 로 나누면 $|\alpha - p/q| \lt 1/(qN) \le 1/q^2$ 입니다. $N$ 을 키우며 되풀이하면, 모든 무리수는 오차가 $1/q^2$ 보다 작은 분수 $p/q$ 를 무한히 많이 갖는다는 것이 나옵니다. 가장 좋은 근사 분수를 차례로 내놓는 방법이 연분수⁠(continued fraction)⁠입니다.

사람이 두 명 이상인 모임에는 모임 안에서 아는 사람 수가 같은 두 사람이 반드시 있습니다. 사람을 점, 아는 사이를 선으로 그린 그래프에서 한 점에 닿은 선의 개수(차수)가 곧 아는 사람 수입니다. $n$ 명이면 그 수는 0부터 $n-1$ 까지 $n$ 가지입니다. 그런데 아무도 모르는 사람(0)과 모두를 아는 사람( $n-1$ )은 함께 있을 수 없으니 실제로는 $n-1$ 가지뿐입니다. $n$ 명을 $n-1$ 칸에 넣으니 비둘기집 원리로 두 사람이 겹칩니다.

여섯 명이 모이면 서로 아는 세 사람이나 서로 모르는 세 사람이 반드시 있다는 것도 비둘기집 원리에서 시작하는데, 이 생각을 넓힌 것이 램지 이론⁠(Ramsey theory)⁠입니다. 자연수⁠(natural number)⁠를 유한 가지 색으로 칠하면 원하는 어떤 길이의 한 색 등차수열⁠(arithmetic progression)⁠이든 반드시 생긴다는 반 데르 바르던 정리⁠(van der Waerden's theorem)⁠도 비둘기집 원리를 겹겹이 쌓아 증명합니다.

색이 모자라면 이웃한 두 나라가 같은 색을 받을 수밖에 없습니다. 평면 지도는 네 가지 색이면 충분하다는 것이 4색 정리⁠(four color theorem)⁠입니다(나라마다 한 덩어리이고, 한 점에서만 만나는 나라끼리는 이웃으로 치지 않을 때). 1976년 미국 일리노이 대학의 케네스 아펠과 볼프강 하켄이 컴퓨터의 도움으로 증명해 '증명이란 무엇인가'라는 논쟁을 낳았습니다.

짝짓기에서 어떤 k명이 원하는 상대를 모두 합쳐도 k명보다 적으면 비둘기집 원리 때문에 모두에게 짝을 줄 수 없습니다. 사람 수가 유한할 때, 이 장애만 없으면 언제나 모두에게 짝을 줄 수 있다는 것이 홀의 정리⁠(Hall's theorem)⁠입니다.

컴퓨터에서도 자주 쓰입니다. 칸보다 키가 많으면 해시 테이블⁠(hash table)⁠의 충돌은 피할 수 없습니다. 비교를 k번 하는 정렬은 예/아니오 답의 줄이 많아야 $2^k$ 가지라서, $2^k \lt n!$ 이면 서로 다른 두 순서를 구별하지 못합니다(비교 정렬의 하한⁠, comparison sorting lower bound⁠).

상태가 유한한 기계(유한 오토마톤⁠, finite automaton⁠)도 이 원리에 걸립니다. 상태가 $k$ 개인 기계가 a를 $k$ 개 읽으면, 처음 상태까지 $k+1$ 개의 상태를 거치니 비둘기집 원리로 같은 상태를 두 번 지납니다. 예컨대 aⁱ를 읽은 뒤와 aʲ를 읽은 뒤( $i \ne j$ )의 상태가 같다면, 기계는 그 뒤에 bⁱ가 올 때 aⁱbⁱ와 aʲbⁱ를 구별하지 못합니다. 그래서 a와 b가 같은 개수만큼 이어지는 aⁿbⁿ 같은 언어, 곧 개수를 끝없이 세야 하는 언어는 유한 오토마톤과 같은 힘을 가진 정규 표현식⁠(regular expression)⁠으로 적을 수 없습니다. 같은 셈이 언어 모델⁠(language model)⁠에도 걸립니다. 상태의 크기가 고정된 상태 공간 모형⁠(state space model)⁠은 상태에 담을 수 있는 비트 수가 정해져 있으므로, 충분히 긴 무작위 토큰열을 그대로 베낄 수 없습니다.

관련된 시대와 장소부다페스트의 수학자들 20세기 초 케임브리지

이 개념이 나오는 큰 생각근사와 오차 무작위성 자기 참조와 대각선

이 개념이 나오는 긴 글

정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다. 집합론 무한에도 크기가 있다 자연수와 짝수는 어느 쪽이 많을까? 칸토어는 무한을 세는 법을 찾았고, 무한이 하나가 아님을 보였다. 그래프 이론 일곱 다리의 도시 쾨니히스베르크의 일곱 다리를 한 번씩만 건너 산책할 수 있을까? 오일러는 지도를 지우고 점과 선만 남겼다. 계산언어학 말을 세는 기계 문법은 규칙일까, 확률일까? 파니니의 문법에서 촘스키의 위계, 섀넌의 영어 엔트로피, 오늘날의 언어 모델까지. 조합론 세지 않고 세기 시의 운율을 세던 인도의 운율학자부터 오일러의 생성함수까지. 하나하나 늘어놓지 않고 경우의 수를 세는 법은 어떻게 자라났을까? 매칭과 흐름 짝을 찾는 알고리즘 의대 졸업생과 병원, 신장 기증자와 환자, 철도와 화물. 누구를 누구와 이을지 정하는 수학은 냉전의 철도 지도에서 노벨 경제학상까지 이어진다. 램지 이론 완전한 무질서는 없다 여섯 명이 모이면 서로 아는 세 사람이나 서로 모르는 세 사람이 반드시 있다. 충분히 크면 어디에나 질서가 숨어 있다는 이론과, 그것을 동전 던지기로 증명한 에르되시. 알고리즘과 복잡도 줄 세우기의 한계 카드 천 장을 가장 빨리 줄 세우는 방법은? 인구조사의 천공 카드에서 퀵정렬까지, 그리고 어떤 방법도 넘을 수 없는 n log n의 벽. 정보 이론과 압축 짧게 보내기 모스 부호는 왜 E를 점 하나로 보낼까? 섀넌의 엔트로피가 정한 압축의 한계와, 허프만 부호에서 JPEG까지 그 한계에 다가간 방법들. 수학의 오류 틀린 증명이 만든 수학 틀린 증명은 흔하다. 드물게, "정확히 어디가 틀렸는가"라는 물음이 새 분야를 낳는다. 코시의 합 정리와 균등 수렴, 라메의 증명과 아이디얼, 켐프의 사슬, 푸앵카레의 회수된 논문과 혼돈, 프레게의 법칙과 러셀의 편지, 보예보츠키와 증명 보조기까지. 오류는 대개 서로 다른 두 가지를 하나로 여긴 자리에 있었다. 불가능성 정리 불가능의 증명 각의 삼등분, 5차방정식의 근의 공식, 모든 파일을 줄이는 압축, 멈춤을 판정하는 프로그램, 공정한 투표 규칙. 없다는 것은 어떻게 증명할까? 서로 먼 분야의 불가능성 증명들은 거의 모두 불변량, 세기, 대각선이라는 세 가지 무기 가운데 하나를 쓴다. 압축과 과학 압축하는 것이 이해하는 것이다 튀코 브라헤가 20년 동안 적은 행성의 위치를 케플러는 법칙 세 줄로 줄였다. 짧게 적는 일과 이해하는 일은 정말 같은 일일까? 오컴의 면도날을 비트로 재는 법, 과적합을 압축의 실패로 읽는 법, 그리고 그 말이 정리인 곳과 철학인 곳.

이 개념 위에 세워진 것

램지 이론 반 데르 바르던 정리

이 개념을 언급하는 페이지

생일 문제
… 이렇게 2000번 실험하면 겹친 비율은 계산값과 맞습니다. 사람이 366명(윤년까지 치면 367명)이면비둘기집 원리로 확률이 정확히 1입니다. 하지만 그 훨씬 전, 칸 수의 제곱근 정도에서 겹침은 이미 흔합니다. N칸일 …
단사·전사·전단사
… 다른 유한집합 사이에는 전단사가 없습니다. A가 B보다 크면 어딘가 반드시 겹쳐 단사가 될 수 없고(비둘기집 원리), 작으면 B에 남는 원소가 생겨 전사가 될 수 없습니다. 곱셈도 전단사일 수 있습니다. 시계 위의 수 …
연분수
… 곧 어떤 무리수 x 에 대해서도 |x - p/q| \lt 1/q^2 인 분수 p/q 가 무한히 많다는 것은비둘기집 원리로도 보일 수 있습니다. 19세기에 디리클레가 이렇게 증명해 디리클레 근사 정리라 부릅니다. 0과 x, …
황금비
… 무리수인 리사주 곡선이 사각형을 빽빽이 메우는 것과 같은 이야기입니다. 그런데 점을 n+1 개 찍으면비둘기집 원리에 따라 어떤 두 점은 둘레의 1/n 보다 가깝게 붙습니다. 가장 가까운 두 점이 이보다 얼마나 더 …
원시근
… = 씩 곱해 봅시다. 자취는 입니다. 나머지는 n 가지뿐이니 거듭제곱은 언젠가 이미 들른 수로 돌아옵니다(비둘기집 원리). a 가 n 과 서로소이면(최대공약수가 1) 곱하기 a 는 되돌릴 수 있는 전단사라서, 돌아오는 …
중국인의 나머지 정리
… 이니 그럴 수 없습니다. mn 개의 수가 mn 개의 칸에 겹치지 않고 들어가니 칸마다 정확히 하나씩입니다(비둘기집 원리를 거꾸로 쓴 셈이고, 대응은 전단사입니다). 답을 직접 만들 수도 있습니다. n 의 배수 중 m 으로 …
그래프
… 안 이어짐)과 n−1인 점(모두와 이어짐)은 함께 있을 수 없습니다. 가능한 값이 n−1가지뿐이니비둘기집 원리에 따라 두 점이 같은 값을 가집니다. 지금은 . 변을 따라 오갈 수 있는 점끼리 같은 색으로 칠했습니다. …
4색 정리
… 다섯 나라가 서로 모두 맞닿는 지도는 평면에 그릴 수 없습니다. 그런 지도가 있다면 네 색으로 칠할 때비둘기집 원리에 따라 두 나라가 같은 색이 될 테니까요. (이 사실 자체는 4색 정리 없이, 아래에 나오는 오일러의 …
유한 오토마톤
… 두 경우, 예를 들어 a를 i개 읽은 경우와 j개 읽은 경우(i ≠ j)는 같은 상태에 있어야 합니다(비둘기집 원리). 그 뒤로 b를 i개 읽으면 a^i b^i 는 받아들이고 a^j b^i 는 거부해야 하는데, 같은 …
촘스키 위계
… aⁿbⁿ이 정규가 아니라는 증명에는 펌핑 보조정리를 씁니다. 상태가 k개인 기계가 k글자 이상을 읽으면비둘기집 원리에 따라 같은 상태를 두 번 지나고, 그 사이에 읽은 조각은 몇 번을 되풀이해도 기계의 판정이 바뀌지 …
문맥 자유 문법
… 표현식⟧과 유한 오토마톤을 넘어섭니다. 유한한 상태로는 몇 겹 열렸는지를 셀 수 없기 때문입니다(비둘기집 원리). 대신 스택 하나를 가진 푸시다운 오토마톤이 딱 맞습니다. 스택은 접시 더미처럼 맨 위에만 넣고 꺼낼 …
정규 표현식
… 기억이 유한하니 aⁿbⁿ이나 짝 맞는 괄호처럼 개수를 끝없이 맞춰야 하는 언어는 적을 수 없고(비둘기집 원리), 이런 언어에는 문맥 자유 문법이 필요합니다. 촘스키 위계의 가장 안쪽 층입니다. 다만 …
수학적 귀납법
… 0보다 큰 유리수 전체처럼 가장 작은 원소가 없는 부분집합이 있어서 위의 정렬성 논법이 통하지 않습니다.비둘기집 원리, 순열의 개수 n!, 카탈랑 수의 점화식이 모두 귀납법으로 증명됩니다. 1889년 이탈리아의 …
별과 막대
… 많으면 어떤 배치에서든 누군가는 둘 이상 받습니다. 모든 x_i \le 1 인 배치가 없다는 이 말이비둘기집 원리입니다.
램지 이론
… 둘레를 빨강, 안쪽 별 모양을 파랑으로 칠하면 한 색 삼각형이 없습니다. 여섯 명에서 피할 수 없는 까닭은비둘기집 원리입니다. 한 사람 A에게서 나가는 변은 5개인데 색은 둘뿐이므로, 같은 색 변이 적어도 3개 있습니다. …
확률적 방법
… 비트열, 곧 더 짧게 줄일 수 없는 비트열이 반드시 있습니다. 이것은 확률 대신 개수로 한 같은 논법, 곧비둘기집 원리입니다. 이어지는 곳. 존재 증명에 쓰던 무작위성을 계산에 쓰면 무작위 알고리즘이 됩니다. 위에서 …
반 데르 바르던 정리
… 서로 다른 색으로 칠해 나가면 한 색 끝없는 등차수열이 하나도 없는 칠하기가 만들어집니다. 증명의 뼈대는비둘기집 원리를 겹겹이 쓰는 것입니다. 예를 들어 연속한 다섯 수로 된 구간을 두 색으로 칠하는 방법은 2^5 = 32 …
비교 정렬의 하한
… 순서가 모든 비교에서 같은 답을 받으면 알고리즘은 둘을 구별하지 못하고 둘 중 하나는 틀리게 정렬합니다(비둘기집 원리). 그러니 2^k \ge n! , 곧 k \ge \log_2 n! 입니다. 알고리즘이 할 수 있는 비교를 …
해시 테이블
… 키의 가짓수는 칸 수보다 훨씬 많으니, 서로 다른 키가 같은 칸에 떨어지는 충돌은 피할 수 없습니다(비둘기집 원리). 게다가 충돌은 생각보다 훨씬 일찍 일어납니다. 해시 함수가 키를 칸들에 고르게 흩뿌린다고 하면 이것은 …
홀의 정리
… 합시다. 모두 일을 얻으려면 당연히 |N(S)| \ge |S| 여야 합니다. 세 사람이 두 일만 원한다면비둘기집 원리에 따라 둘이 같은 일을 맡아야 하니까요. 1935년 필립 홀은 이 당연한 조건이 모든 S에 대해 …
안정 매칭
… 모두 거절당했고, 그러면 n개 학교가 모두 다른 학생을 보류하고 있으니 학생이 n명보다 많아야 합니다(비둘기집 원리). 안정성도 곧바로 나옵니다. 학생 s가 자기 학교보다 c를 더 좋아한다면 s는 c에 먼저 지원했다가 …
원천 부호화 정리
… 모두 합쳐 1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1 개뿐입니다. 그러니비둘기집 원리에 따라 어떤 파일은 줄지 않습니다. 압축은 확률이 치우친 곳에서만 이득을 봅니다. 역사. 자주 쓰는 …
렘펠–지브 압축
… 부릅니다. 반면 '무작위 글'처럼 되풀이가 없는 글은 거의 줄지 않습니다. 이것은 방법의 결함이 아닙니다.비둘기집 원리에 따르면 어떤 압축도 모든 글을 줄일 수는 없고, 줄어드는 글이 있으면 줄지 않는 글도 있어야 합니다. …
콜모고로프 복잡도
… K(x) \lt n - c 인 것, 곧 c비트보다 많이 줄어드는 것은 2^{-c} 보다 적은 비율입니다(비둘기집 원리). 동전을 던져 얻은 문자열이 10비트 넘게 줄어들 확률은 1,000분의 1도 되지 않습니다. 장난감 …
라틴 방진
… 기호가 변 rc의 색). 모든 짝이 한 번씩이라는 조건은 전단사로, 칸과 짝의 개수를 맞추는 셈은비둘기집 원리로 이어집니다.
상태 공간 모형과 선형 순환
… \gt Nb 가 되면 가능한 입력( V^n 가지)이 가능한 상태( 2^{Nb} 가지)보다 많습니다. 그러면비둘기집 원리에 따라 서로 다른 두 입력이 같은 상태에 이르므로, 모든 입력을 옳게 베낄 수는 없습니다(평균적으로 …

이 페이지가 가리키는 개념

생일 문제 모듈러 연산 페터 구스타프 르죈 디리클레 무리수 연분수 그래프 램지 이론 반 데르 바르던 정리 4색 정리 홀의 정리 해시 테이블 비교 정렬의 하한 유한 오토마톤 정규 표현식 상태 공간 모형과 선형 순환