잔글 (→예시) |
잔글 (오류 수정 (빈칸)) |
||
| (사용자 4명의 중간 판 6개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
''' | '''Pigeonhole Principle'''. | ||
== 개요 == | == 개요 == | ||
“비둘기집 <math>n</math> 채에 비둘기 <math>n+1</math> 마리를 나눠 넣으면, 비둘기가 두 마리 이상 들어 있는 집이 적어도 하나는 꼭 존재한다.”라는 원리이다. 서랍 원리라고도 한다. | |||
좀 더 일반적으로는 아래와 같다. | 좀 더 일반적으로는 아래와 같다. | ||
비둘기 집 “<math>n</math> 채에 비둘기 <math>m</math>마리를 나눠 넣으면, 비둘기가 <math>\left\lfloor \tfrac{m-1}{n} \right\rfloor + 1</math> 마리 이상 | 비둘기 집 “<math>n</math> 채에 비둘기 <math>m</math>마리를 나눠 넣으면, 비둘기가 <math>\left\lfloor \tfrac{m-1}{n} \right\rfloor + 1</math> 마리 이상 들어 있는 집이 적어도 하나는 꼭 존재한다.” 참고로, <math>m</math>이 <math>n</math>의 배수라면 <math>\tfrac{m}{n}</math> 마리 이상이라는 뜻이다. | ||
꼭 기억해야 할 점은, <math>\left\lfloor \tfrac{m-1}{n} \right\rfloor + 1</math> 마리가 정확히 들어 있는 집이 존재한다고 보장할 순 없고, 둘 이상 있는지도 보장할 수 없다는 것이다. 보장할 수 있는 것은 오직 <math>\left\lfloor \tfrac{m-1}{n} \right\rfloor + 1</math> 마리 '''이상''' 들어 있는 집이 '''적어도 하나''' 있다는 것뿐이다. | 꼭 기억해야 할 점은, <math>\left\lfloor \tfrac{m-1}{n} \right\rfloor + 1</math> 마리가 정확히 들어 있는 집이 존재한다고 보장할 순 없고, 둘 이상 있는지도 보장할 수 없다는 것이다. 보장할 수 있는 것은 오직 <math>\left\lfloor \tfrac{m-1}{n} \right\rfloor + 1</math> 마리 '''이상''' 들어 있는 집이 '''적어도 하나''' 있다는 것뿐이다. | ||
| 20번째 줄: | 20번째 줄: | ||
굉장히 간단한 원리인 만큼 변형 또한 다양하다. 증명도 비슷하게 하면 된다. 쉬운 것부터 하나하나 보자. | 굉장히 간단한 원리인 만큼 변형 또한 다양하다. 증명도 비슷하게 하면 된다. 쉬운 것부터 하나하나 보자. | ||
* 비둘기집이 <math>n</math>채 있고 비둘기가 <math>n-1</math>마리 있을 때, 빈 집이 꼭 존재한다.{{ㅊ|[[빈집털이]]}} | * 비둘기집이 <math>n</math>채 있고 비둘기가 <math>n-1</math>마리 있을 때, 빈 집이 꼭 존재한다.{{ㅊ|[[빈집털이]]}} | ||
* 비둘기집이 <math>n</math>채가 있는데 <math>i</math>번째 비둘기집마다 각각 자연수 <math>a_i</math>가 적혀 있다고 하자. 만약 비둘기가 <math>\sum a_i -n+1</math>마리 있으면 적혀 있는 수보다 비둘기 수가 더 많은 집이 있다. | * 비둘기집이 <math>n</math>채가 있는데 <math>i</math>번째 비둘기집마다 각각 자연수 <math>a_i</math>가 적혀 있다고 하자. 만약 비둘기가 <math>\sum a_i -n+1</math>마리 있으면 적혀 있는 수보다 비둘기 수가 더 많은 집이 있다. | ||
| 27번째 줄: | 26번째 줄: | ||
** 만약 <math>\sum_{i=1}^{n} x_i = n+1</math>이고 수들을 0을 포함한 자연수로 제한하면 간단한 형태가 된다. | ** 만약 <math>\sum_{i=1}^{n} x_i = n+1</math>이고 수들을 0을 포함한 자연수로 제한하면 간단한 형태가 된다. | ||
* 확률변수 <math>X</math>가 있을 때, <math>X</math>가 <math>E(X)</math>이상일 확률이 0보다 크다. 비슷하게 <math>E(X)</math>이하일 확률도 0보다 크다. | * 확률변수 <math>X</math>가 있을 때, <math>X</math>가 <math>E(X)</math>이상일 확률이 0보다 크다. 비슷하게 <math>E(X)</math>이하일 확률도 0보다 크다. | ||
** 비둘기 <math>n+1</math>마리를 비둘기집 <math>n</math>채에 넣어두고 확률변수 <math>X</math>를 각 비둘기집에 | ** 비둘기 <math>n+1</math>마리를 비둘기집 <math>n</math>채에 넣어두고 확률변수 <math>X</math>를 각 비둘기집에 들어 있는 비둘기 수라고 하면 간단한 형태가 된다. | ||
== 예시 == | == 예시 == | ||
실생활에 적용할 수 있는 상황이 많다. | 실생활에 적용할 수 있는 상황이 많다. | ||
* 리브레 위키에는 [[위키러]]가 {{NUMBEROFUSERS}}명 있고, 이 중에서 생일이 같은 사람이 {{#expr: floor (({{formatnum:{{NUMBEROFUSERS}}|R}}-1)/366+1)}}명 이상 있다. {{#tag:math|\left \lfloor \tfrac{ {{NUMBEROFUSERS}}-1 }{366} \right \rfloor + 1 = {{#expr: floor (({{formatnum:{{NUMBEROFUSERS}}|R}}-1)/366+1)}} }} <ref>[[2월 29일]] 포함 366일</ref> | |||
* 리브레 위키에는 [[위키러]]가 | * [[대한민국]] [[서울]]에 사는 사람들 중 머리카락 수가 같은 사람이 2명 이상 있다. {{ㅊ|[[대머리]] 두 명 찾는 게 그렇게 어렵나}} | ||
* [[대한민국]] [[서울]]에 사는 사람들 중 머리카락 수가 같은 사람이 2명 이상 있다. {{ㅊ|[[대머리]] 두 명 | |||
* 한 반에 있는 학생들의 시험 점수가 서로 같지 않으면 반 1등은 평균보다 잘 봤다. {{ㅊ| 애초에 평균은 안중에 없고 전교에서 노시는 분}} | * 한 반에 있는 학생들의 시험 점수가 서로 같지 않으면 반 1등은 평균보다 잘 봤다. {{ㅊ| 애초에 평균은 안중에 없고 전교에서 노시는 분}} | ||
* 6명이 있을 때, 서로 친구가 아니거나 서로 친구인 세 명이 있다. [[램지의 정리]]라고 한다. | * 6명이 있을 때, 서로 친구가 아니거나 서로 친구인 세 명이 있다. [[램지의 정리]]라고 한다. | ||
| 45번째 줄: | 43번째 줄: | ||
{{주석}} | {{주석}} | ||
[[분류:수학]] | [[분류:조합론]] | ||
[[분류:수학 정리]] | |||
2021년 6월 19일 (토) 23:59 기준 최신판
Pigeonhole Principle.
개요[편집 | 원본 편집]
“비둘기집 [math]\displaystyle{ n }[/math] 채에 비둘기 [math]\displaystyle{ n+1 }[/math] 마리를 나눠 넣으면, 비둘기가 두 마리 이상 들어 있는 집이 적어도 하나는 꼭 존재한다.”라는 원리이다. 서랍 원리라고도 한다.
좀 더 일반적으로는 아래와 같다.
비둘기 집 “[math]\displaystyle{ n }[/math] 채에 비둘기 [math]\displaystyle{ m }[/math]마리를 나눠 넣으면, 비둘기가 [math]\displaystyle{ \left\lfloor \tfrac{m-1}{n} \right\rfloor + 1 }[/math] 마리 이상 들어 있는 집이 적어도 하나는 꼭 존재한다.” 참고로, [math]\displaystyle{ m }[/math]이 [math]\displaystyle{ n }[/math]의 배수라면 [math]\displaystyle{ \tfrac{m}{n} }[/math] 마리 이상이라는 뜻이다.
꼭 기억해야 할 점은, [math]\displaystyle{ \left\lfloor \tfrac{m-1}{n} \right\rfloor + 1 }[/math] 마리가 정확히 들어 있는 집이 존재한다고 보장할 순 없고, 둘 이상 있는지도 보장할 수 없다는 것이다. 보장할 수 있는 것은 오직 [math]\displaystyle{ \left\lfloor \tfrac{m-1}{n} \right\rfloor + 1 }[/math] 마리 이상 들어 있는 집이 적어도 하나 있다는 것뿐이다.
증명[편집 | 원본 편집]
귀류법을 이용한다.
모든 집에 비둘기가 [math]\displaystyle{ \left\lfloor \tfrac{m-1}{n} \right\rfloor }[/math] 마리 이하로 들어 있다고 하면, 총 비둘기 수는 [math]\displaystyle{ n \cdot \left\lfloor \tfrac{m-1}{n} \right\rfloor \lt n \cdot \tfrac{m-1}{n} = m-1 \lt m }[/math]이 되어 모순이다.
변형[편집 | 원본 편집]
굉장히 간단한 원리인 만큼 변형 또한 다양하다. 증명도 비슷하게 하면 된다. 쉬운 것부터 하나하나 보자.
- 비둘기집이 [math]\displaystyle{ n }[/math]채 있고 비둘기가 [math]\displaystyle{ n-1 }[/math]마리 있을 때, 빈 집이 꼭 존재한다.
빈집털이 - 비둘기집이 [math]\displaystyle{ n }[/math]채가 있는데 [math]\displaystyle{ i }[/math]번째 비둘기집마다 각각 자연수 [math]\displaystyle{ a_i }[/math]가 적혀 있다고 하자. 만약 비둘기가 [math]\displaystyle{ \sum a_i -n+1 }[/math]마리 있으면 적혀 있는 수보다 비둘기 수가 더 많은 집이 있다.
- 가장 간단한 형태는 [math]\displaystyle{ a_1 = a_2 = ... = a_n = 2 }[/math]이다.
- 실수 [math]\displaystyle{ x_1 , x_2 , ... , x_n }[/math]가 [math]\displaystyle{ n }[/math]개 있을 때, 평균 이상인 수 [math]\displaystyle{ x_i }[/math]가 존재한다.
- 만약 [math]\displaystyle{ \sum_{i=1}^{n} x_i = n+1 }[/math]이고 수들을 0을 포함한 자연수로 제한하면 간단한 형태가 된다.
- 확률변수 [math]\displaystyle{ X }[/math]가 있을 때, [math]\displaystyle{ X }[/math]가 [math]\displaystyle{ E(X) }[/math]이상일 확률이 0보다 크다. 비슷하게 [math]\displaystyle{ E(X) }[/math]이하일 확률도 0보다 크다.
- 비둘기 [math]\displaystyle{ n+1 }[/math]마리를 비둘기집 [math]\displaystyle{ n }[/math]채에 넣어두고 확률변수 [math]\displaystyle{ X }[/math]를 각 비둘기집에 들어 있는 비둘기 수라고 하면 간단한 형태가 된다.
예시[편집 | 원본 편집]
실생활에 적용할 수 있는 상황이 많다.
- 리브레 위키에는 위키러가 8,600명 있고, 이 중에서 생일이 같은 사람이 24명 이상 있다. [math]\displaystyle{ \left \lfloor \tfrac{ 8,600-1 }{366} \right \rfloor + 1 = 24 }[/math] [1]
- 대한민국 서울에 사는 사람들 중 머리카락 수가 같은 사람이 2명 이상 있다.
대머리 두 명 찾는 게 그렇게 어렵나 - 한 반에 있는 학생들의 시험 점수가 서로 같지 않으면 반 1등은 평균보다 잘 봤다.
애초에 평균은 안중에 없고 전교에서 노시는 분 - 6명이 있을 때, 서로 친구가 아니거나 서로 친구인 세 명이 있다. 램지의 정리라고 한다.
- 어떤 모임이든 친구 수가 같은 두명이 있다.[2]
- 무손실 압축 알고리즘이 모든 파일에 대해서 잘 되는 것은 아니다.
- 소녀시대 멤버 중 생일 요일이 서로 같은 사람이 적어도 2명 존재한다.
- 8강에 5명의 테란이 올라갔을 때 적어도 하나 이상의
세상에서 재일 재밌는테테전이 있다