문서 보기문서 편집수정 내역 비둘기 집의 원리 (덤프버전으로 되돌리기) [include(틀:이산수학)] [목차] == 개요 == {{{+1 pigeonhole principle}}} [[비둘기]]집 원리는 간단하게 말해서 [math(n+1)]개의 물건을 [math(n)]개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이기 때문에, 비둘기 집의 원리라고 불린다. == 증명 == [[귀류법]]을 이용해 증명이 가능하다. 모든 비둘기가 비둘기집에 빠짐없이 들어가야 한다는 조건 하에서, [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인가구가 생긴다는 것. 사실 너무나 당연하고 직관적이어서 이게 증명씩이나 필요한지, '정리'라는 이름을 가지고 있어야 하는지 의문이 들 수도 있지만, 실제 생활에서 뿐만 아니라 많은 수학/과학, 그 중에서도 특히 조합 문제를 해결할 때 이 원리가 사용되며 이름이 없으면 불편하기 때문에 편의상 적당히 이름을 붙인 것으로 알려져 있다. == 확장 == [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)]) == 예시 == 가장 간단한 예를 들자면 공이 3개가 있는데, 공을 적당히 나누어 2개의 상자에 나누어 넣어야 한다. 그렇다면, 어떤 방법으로 나누어 넣더라도 공을 쪼개버리지 않는 이상은 반드시 둘 중 하나의 상자에는 공이 2개 이상 들어 있게 된다. 어떤 집단에 367명(윤년의 2월 29일도 고려해야 하기 때문)이 있으면 생일이 같은 사람이 반드시 1쌍 이상 존재한다. 다만, 이는 100% 확률 조건이고, 구체적으로는 23명만 넘어가도 50%가 넘어가는 등, 훨씬 적은 수로도 가능하다. 이에 대한 자세한 사정은 [[생일 문제]] 참조. 비슷하게 9901대의 승용차가 있다고 하면 번호가 같은 차량이 반드시 1쌍 이상 있게 된다.[* 0100~9999까지 가능하며 용도기호 32가지, 앞의 숫자 369가지 제외함] 서울특별시에 살고 있는 인구는 955만명이므로 머리카락 개수가 무조건 겹치게 된다.[* 인간의 머리카락 개수는 10~15만 가닥으로 아무리 잘해도 100만 가닥을 넘지 않기 때문이다.] 또한 생일도 겹치게 되며 인간의 평균 수명은 69~74세이고 오래 살아도 최고 기록이 150살을 넘지 않으므로 나이도 겹치게 된다. [[모여봐요 동물의 숲]]에서도 적용할 수 있는 요소가 많다. 우선 주민 숫자가 400마리가 넘기 때문에 생일이 겹치는 주민이 반드시 존재하며 전설의 낚시꾼 칭호를 얻으려면 물고기를 100마리 연속으로 잡아야 하는데 물고기 종류는 80종이므로 무조건 같은 물고기를 낚게 된다. 그리고 마일리지 섬을 30번 가게 되면 무조건 중복 섬이 걸리며[* 마일리지 섬의 종류가 21가지(0~24번 섬까지의 섬 중에 3번과 5번 섬은 없고 1.2.0. 업데이트 이후 두 섬은 방문할 수 없기 때문이다.)] 여욱이 11번 오면 무조건 중복 미술품이 걸리게 된다.[* 여욱은 미술품 4개를 들고 오기 때문에 11번 오면 44개를 가지고 오고 미술품은 43종류이므로 무조건 하나는 중복이 된다.] == 실제로 비둘기에 적용한다면? == 조류는 알을 하나의 둥지에만 낳기 때문에 자연적으로는 비둘기 두 마리가 한 둥지를 쓸 일은 없다. 물론 [[뻐꾸기]]는 예외적인 경우이므로 제외. 여기서 말하는 '비둘기집'은 닭장처럼 큰 우리를 하나 혹은 여러개 쌓아올려 만든 새장에 가깝다. 구글에 [[https://www.google.com/search?q=pigeon+cage&source=lnms&tbm=isch&sa=X&ved=2ahUKEwiD0Pif87TmAhXCMd4KHRx_D80Q_AUoAXoECBAQAw&biw=1600&bih=757#imgrc=-rApR5J7Uw0TgM:|pigeon cage]]를 검색하면 나온다. 각 층마다 비둘기를 한 쌍 정도 키우는데 따라서 입구가 층마다 있어 입구의 개수가 여러개다. 따라서 출입구의 개수는 비둘기의 수보다 적거나 같은 것. 층이 나누어지지 않은 큰 새장에서도 출입구를 여러 개 두는 경우도 있다. 큰 새장에서 비둘기들은 각 쌍별로 둥지를 따로 쓴다. 카타르 등 아랍 지역에서는 탑 형태의 비둘기집을 짓기도 한다. [[https://www.alamy.com/the-pigeon-towers-in-katara-cultural-village-doha-qatar-image337665080.html|#]] == 관련 문서 == * [[수학 관련 정보]] [[분류:이산수학]]캡챠되돌리기