페미위키:포크 프로젝트/리브레 위키/비둘기집의 원리

Pigeonhole Principle.

개요

“비둘기집 $n$ 채에 비둘기 $n+1$ 마리를 나눠 넣으면, 비둘기가 두 마리 이상 들어 있는 집이 적어도 하나는 꼭 존재한다.”라는 원리이다. 서랍 원리라고도 한다.

좀 더 일반적으로는 아래와 같다.

비둘기 집 “$n$ 채에 비둘기 $m$마리를 나눠 넣으면, 비둘기가 $\left\lfloor {\tfrac {m-1}{n}}\right\rfloor +1$ 마리 이상 들어 있는 집이 적어도 하나는 꼭 존재한다.” 참고로, $m$이 $n$의 배수라면 ${\tfrac {m}{n}}$ 마리 이상이라는 뜻이다.

꼭 기억해야 할 점은, $\left\lfloor {\tfrac {m-1}{n}}\right\rfloor +1$ 마리가 정확히 들어 있는 집이 존재한다고 보장할 순 없고, 둘 이상 있는지도 보장할 수 없다는 것이다. 보장할 수 있는 것은 오직 $\left\lfloor {\tfrac {m-1}{n}}\right\rfloor +1$ 마리 이상 들어 있는 집이 적어도 하나 있다는 것뿐이다.

증명

귀류법을 이용한다.

모든 집에 비둘기가 $\left\lfloor {\tfrac {m-1}{n}}\right\rfloor$ 마리 이하로 들어 있다고 하면, 총 비둘기 수는 $n\cdot \left\lfloor {\tfrac {m-1}{n}}\right\rfloor <n\cdot {\tfrac {m-1}{n}}=m-1<m$이 되어 모순이다.

변형

굉장히 간단한 원리인 만큼 변형 또한 다양하다. 증명도 비슷하게 하면 된다. 쉬운 것부터 하나하나 보자.

• 비둘기집이 $n$채 있고 비둘기가 $n-1$마리 있을 때, 빈 집이 꼭 존재한다.빈집털이
• 비둘기집이 $n$채가 있는데 $i$번째 비둘기집마다 각각 자연수 $a_{i}$가 적혀 있다고 하자. 만약 비둘기가 $\sum a_{i}-n+1$마리 있으면 적혀 있는 수보다 비둘기 수가 더 많은 집이 있다.
  • 가장 간단한 형태는 $a_{1}=a_{2}=...=a_{n}=2$이다.
• 실수 $x_{1},x_{2},...,x_{n}$가 $n$개 있을 때, 평균 이상인 수 $x_{i}$가 존재한다.
  • 만약 $\sum _{i=1}^{n}x_{i}=n+1$이고 수들을 0을 포함한 자연수로 제한하면 간단한 형태가 된다.
• 확률변수 $X$가 있을 때, $X$가 $E(X)$이상일 확률이 0보다 크다. 비슷하게 $E(X)$이하일 확률도 0보다 크다.
  • 비둘기 $n+1$마리를 비둘기집 $n$채에 넣어두고 확률변수 $X$를 각 비둘기집에 들어 있는 비둘기 수라고 하면 간단한 형태가 된다.

예시

실생활에 적용할 수 있는 상황이 많다.

• 리브레 위키에는 위키러가 5,989명 있고, 이 중에서 생일이 같은 사람이 17명 이상 있다. 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \left \lfloor \tfrac{ 5,989-1 }{366} \right \rfloor + 1 = 17 }
• 대한민국 서울에 사는 사람들 중 머리카락 수가 같은 사람이 2명 이상 있다. 대머리 두 명 찾는 게 그렇게 어렵나
• 한 반에 있는 학생들의 시험 점수가 서로 같지 않으면 반 1등은 평균보다 잘 봤다. 애초에 평균은 안중에 없고 전교에서 노시는 분
• 6명이 있을 때, 서로 친구가 아니거나 서로 친구인 세 명이 있다. 램지의 정리라고 한다.
• 어떤 모임이든 친구 수가 같은 두명이 있다.
• 무손실 압축 알고리즘이 모든 파일에 대해서 잘 되는 것은 아니다.
• 소녀시대 멤버 중 생일 요일이 서로 같은 사람이 적어도 2명 존재한다.
• 8강에 5명의 테란이 올라갔을 때 적어도 하나 이상의 세상에서 재일 재밌는 테테전이 있다