|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
pigeonhole principle비둘기집 원리는 간단하게 말해서 [math(n+1)]개의 물건을 [math(n)]개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이기 때문에, 비둘기 집의 원리라고 불린다.
2. 증명
귀류법을 이용해 증명이 가능하다.모든 비둘기가 비둘기집에 빠짐없이 들어가야 한다는 조건 하에서, [math(n+1)]마리의 비둘기와 [math(n)]개의 비둘기집이 있고 한 집당 한 마리씩만 존재한다고 가정하면[math((p\wedge{\sim}q))], 비둘기집 전체에는 최대 [math(n)]마리의 비둘기가 존재할 수 있게 되는데, 비둘기의 숫자는 [math(n+1)]마리이기에 어느 집에도 들어가지 못한 비둘기 한 마리가 남을 수밖에 없게 되므로 가정에 모순이 발생하게 된다. 따라서 모든 비둘기집에 한마리의 비둘기만 들어가야 한다는 제한은 성립할 수 없으며, 이에 따라 "[math(n+1)]마리의 비둘기를 [math(n)]개의 비둘기집에 넣는다면, 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 존재한다.[math((p\rightarrow q))]"가 참이 된다. 비둘기 집의 원리에 대한 문제를 구할 때에 아니면 표현할 때에는 올림 기호를 사용한다.
사람으로 치면, 다섯 명이 4개 집에 나눠 들어가면 2인 이상 가구가 최소 하나는 생긴다는 것. 사실 너무나 당연하고 직관적이어서 이게 증명씩이나 필요한지, '정리'라는 이름을 가지고 있어야 하는지 의문이 들 수도 있지만, 실제 생활에서 뿐만 아니라 많은 수학/과학, 그 중에서도 특히 조합 문제를 해결할 때 이 원리가 사용되며 이름이 없으면 불편하기 때문에 편의상 적당히 이름을 붙인 것으로 알려져 있다. '입력의 범위보다 출력의 범위가 작아 다른 입력값이어도 동일한 출력값이 나올 수 있는 상황'을 '비둘기 집의 원리'로 표현하면 간단하기 때문이다.
3. 확장
[math(n+2)] 마리의 비둘기와 [math(n)]개의 비둘기집이 있다고 가정하자. 비둘기집의 원리에 의해서 어느 하나의 비둘기집에는 2마리 이상 있는 것은 분명하다. 하지만, 2개 이상의 비둘기집에 비둘기가 2마리 이상 반드시 존재하는 것은 아니다. [math(n-1)]개의 비둘기집에는 모두 한마리씩 있고, 1개의 비둘기집에는 3마리가 들어갈 수도 있다. 또 같은 이유로, 3마리가 들어간 비둘기집이 반드시 존재하는 것도 아니다. [math(n-2)]개의 비둘기집에 1마리씩, 그리고 2마리씩 2군데 들어갈 수도 있다. 비둘기의 수가 증가한다고 해서, 그에 맞게 간단히 확장되는 것은 아니다.다만, 비둘기가 [math(2n+1)] 마리로 증가한다면, 이때는 3마리 이상 들어간 비둘기집이 최소 1군데 있다는 것이 보장된다. 일반화 하면 비둘기가 [math(kn+1)] 마리이고 비둘기집이 [math(n)]개이면, 최소한 하나의 비둘기집에는 [math(k+1)] 마리 이상의 비둘기가 들어간다. ([math(k\in\mathbb Z)])
4. 예시
가장 간단한 예를 들자면 공이 3개가 있는데, 공을 적당히 나누어 2개의 상자에 나누어 넣어야 한다. 그렇다면, 어떤 방법으로 나누어 넣더라도 공을 쪼개버리지 않는 이상은 반드시 둘 중 하나의 상자에는 공이 2개 이상 들어 있게 된다.어떤 집단에 367명(윤년의 2월 29일도 고려해야 하기 때문)이 있으면 생일이 같은 사람이 반드시 1쌍 이상 존재한다. 다만, 이는 100% 확률 조건이고, 구체적으로는 23명만 넘어가도 50%가 넘어가는 등, 훨씬 적은 수로도 가능하다. (이에 대한 자세한 사정은 생일 문제 참조.) 만약 전교생이 733명인 학교가 있다면 생일이 겹치는 사람은 3명 이상이다. (1년이 최대 366일이고 이것을 2배 해도 732일이기 때문이다.)
비슷하게 9901대의 승용차가 있다고 하면 번호가 같은 차량이 반드시 1쌍 이상 있게 된다.[1]
서울특별시에 살고 있는 인구는 955만명이므로 머리카락 개수가 무조건 겹치게 된다.[2] 또한 생일도 겹치게 되며 인간의 평균 수명은 69~74세이고 오래 살아도 최고 기록이 150살을 넘지 않으므로 나이도 겹친다.[3] 그리고 한국 전체로만 봐도 81,514개의 이름이 있으므로 당연히 서울특별시, 부산광역시같은 대도시나 인구 10만을 넘기는 한국의 여러 도시들에 (성은 제외하고) 이름이 같은 사람도 존재한다.
모여봐요 동물의 숲에서도 적용할 수 있는 요소가 많다. 우선 주민 숫자가 400마리가 넘기 때문에 생일이 겹치는 주민이 반드시 존재하며 전설의 낚시꾼 칭호를 얻으려면 물고기를 100마리 연속으로 잡아야 하는데 물고기 종류는 80종이므로 무조건 같은 물고기를 낚게 된다. 그리고 마일리지 섬을 30번 가게 되면 무조건 중복 섬이 걸리며[4] 여욱이 11번 오면 무조건 중복 미술품이 걸리게 된다.[5]
암호학적 해시 함수는 무조건 해시 충돌이 일어나게 되어 있다.
5. 실제로 비둘기에 적용한다면?
조류는 알을 하나의 둥지에만 낳기 때문에 자연적으로는 비둘기 두 마리가 한 둥지를 쓸 일은 없다. 물론 뻐꾸기는 예외적인 경우이므로 제외.여기서 말하는 '비둘기집'은 닭장처럼 큰 우리를 하나 혹은 여러 개 쌓아올려 만든 새장에 가깝다. 구글에 pigeon cage를 검색하면 나온다. 각 층마다 비둘기를 한 쌍 정도 키우는데 따라서 입구가 층마다 있어 입구의 개수가 여러 개다. 따라서 출입구의 개수는 비둘기의 수보다 적거나 같은 것. 층이 나누어지지 않은 큰 새장에서도 출입구를 여러 개 두는 경우도 있다. 큰 새장에서 비둘기들은 각 쌍별로 둥지를 따로 쓴다. 카타르 등 아랍 지역에서는 탑 형태의 비둘기집을 짓기도 한다. #
6. 관련 문서
[1]
0100~9999까지 가능하며 용도기호 32가지, 앞의 숫자 369가지 제외함.
[2]
인간의 머리카락 개수는 10~15만 가닥으로 아무리 잘해도 100만 가닥을 넘지 않기 때문이다.
[3]
이것은 당연히 전 세계인을 포함해도 겹친다.
[4]
마일리지 섬의 종류가 21가지(0~24번 섬까지의 섬 중에 3번과 5번 섬은 없고 1.2.0. 업데이트 이후 두 섬은 방문할 수 없기 때문이다.)
[5]
여욱은 미술품 4개를 들고 오기 때문에 11번 오면 44개를 가지고 오고 미술품은 43종류이므로 무조건 하나는 중복이 된다.