비둘기구멍 원리

수학에서 비둘기홀 원리는 n개의 항목을 m개의 컨테이너에 넣고 n> m으로 할 경우 적어도1개의 컨테이너에 여러 ^[1]개의 아이템을 포함해야 합니다.예를 들어 장갑이 3개(양손잡이/후진형 장갑이 없고)인 경우 오른손 장갑이 2개 이상 또는 왼손 장갑이 2개 이상 있어야 한다. 왜냐하면 3개의 물체가 있지만 장갑을 끼울 수 있는 범주는 2개이기 때문이다.명백해 보이는 이 진술은 세는 논쟁의 한 종류로, 예상치 못한 결과를 보여주는 데 사용될 수 있다.예를 들어, 런던의 인구가 인간의 머리에 존재할 수 있는 머리카락의 최대 수보다 많다는 것을 고려하면, 비둘기구멍 원칙은 머리에 같은 수의 털을 가진 적어도 두 명의 사람이 런던에 있어야 한다고 요구한다.

비둘기홀 원리는 1624년 장 류르천의 ^[2]책에 등장하지만, 1834년 피터 구스타프 르준 디리클레가 슈바흐프린집(그림의 원리 또는 선반 원리)^[3]이라는 이름으로 이 원리를 취급한 후 흔히 디리클레 상자 원리 또는 디리클레의 서랍 원리라고 불린다.

그 원리는 몇 가지 일반화를 가지고 있으며 다양한 방법으로 언급될 수 있다.보다 정량화된 버전: 자연수 k와 m의 경우, n = km + 1 개체가 m 집합 사이에 분포되어 있는 경우, 비둘기 구멍 원리는 집합 중 적어도 하나가 k + 1 ^[4]개체를 포함할 것이라고 주장한다.임의의 n과 m의 경우, 이는${\displaystyle \mathrm{k}}$ + 1 ${\displaystyle =n}$( n${\displaystyle }$-${\displaystyle }$1 ) / m${\displaystyle 1}$ + ${\displaystyle 1}$ $=$ n / ${\displaystyle m}$、 \ $lfloor$ ( n - 1 ) /$m$ \$lfloor$ + 1 = \ $lceil n$ / m \ rceil }로 일반화되어 있습니다$.$여기서 $"\$ $style$\ $lfoor"$는 \ ${\displaystyle \mathrm{cdots}}$입니다.

가장 간단한 적용은 유한 집합(비둘기나 상자 등)에 대한 것이지만 일대일 대응에 넣을 수 없는 무한 집합에도 사용됩니다.그러기 위해서는 비둘기홀 원리의 공식 스테이트먼트가 필요합니다.즉, "영역보다 작은 코드메인을 가진 주입 함수는 존재하지 않습니다."시겔의 보조개념과 같은 고도의 수학적 증명은 이 보다 일반적인 개념을 기반으로 한다.

어원학

디리클레는 독일 슈바흐나 프랑스 티루아르를 사용하여 프랑스어와 독일어로 그의 작품을 출판했다.이 용어의 엄밀한 본래 의미는 영어 서랍, 즉 서랍이 들어 있는 캐비닛에 넣고 꺼낼 수 있는 뚜껑이 열린 상자에 해당합니다.(디리클레는 서랍에 진주를 뿌리는 것에 대해 썼다.)이 용어들은 책상, 캐비닛, 또는 비둘기를 수용하는 구조물에 은유적으로 뿌리를 둔 편지나 종이를 보관하기 위한 벽의 작은 열린 공간이라는 의미에서 비둘기 구멍이라는 단어에 변형되었다.

비둘기구멍이 있는 가구는 많은 카테고리(우체국의 편지나 호텔의 방 열쇠 등)로 물건을 보관하거나 분류하는 데 일반적으로 사용되기 때문에 번역 비둘기구멍은 Dirichlet의 원래 서랍의 은유를 더 잘 표현한 것일 수 있습니다.비둘기 구멍이라는 용어에 대한 이해는 (특히 영어가 모국어가 아닌 과학계의 언어로서) 말 그대로 비둘기와 구멍과 관련된 좀 더 그림적인 해석에 유리하게 사라지고 있다."pigeonhole"을 "dovecote"로 암시적으로 해석하는 것은 최근에 "pigeonhole 원리"를 "Taubenschlagprinzip"^[5]으로 역번역한 독일어로 다시 돌아왔다.

원래 조건 German[6]에 French,[7] 다른 문자 그대로의 번역에"프린시페 섬:아프리카 서해안 앞바다 destiroirs""Schubfachprinzip"게다가 아직도 아랍어("مبدأ برج الحمام"), 불가리아("принцип на чекмеджетата"), 중국("抽屉原理"), 덴마크("Skuffeprincippet"), 네덜란드("ladenprincipe"), 헝가리("skatulyaelv"), 이탈리아("principio 데이 cassetti"), J.에서 보편화된apanese ("引き出し論法"), Persian ("اصل لانه کبوتری"), Polish ("zasada szufladkowa"), Portuguese ("Princípio das Gavetas"), Swedish ("Lådprincipen"), Turkish ("çekmece ilkesi") and Vietnamese ("nguyên lý hộp").

예

양말 따기

서랍에 검정색 양말과 파란색 양말이 섞여 있고, 각 양말은 양쪽 발에 신을 수 있으며, 서랍에서 여러 개의 양말을 보지 않고 꺼낸다고 가정해 보십시오.같은 색상의 양말을 보증하기 위해 필요한 최소 풀 삭스 수는 몇 개입니까?비둘기 구멍 원리를 사용하여 색상당 하나의 비둘기 구멍을 사용하여 같은 색상(m = 2개 구멍, 색상당 1개)을 최소 한 쌍으로 만들려면 서랍에서 양말 3개만 당기면 됩니다(n = 3개 항목).한 가지 색상 중 세 가지가 있거나 한 가지 색상 중 두 가지와 다른 색상이 있습니다.

악수

서로 악수할 수 있는 사람이 n명(n > 1)인 경우, 비둘기홀의 원칙은 같은 수의 사람과 악수하는 사람이 항상 한 쌍임을 나타냅니다.이 원칙의 적용에서, 한 사람이 배정되는 '구멍'은 그 사람이 악수하는 손의 수입니다.0부터 n - 1까지 몇 명씩 악수를 하기 때문에 n개의 홀이 있을 수 있습니다.한편, '0'홀 또는 'n - 1'홀 또는 둘 다 비어 있어야 합니다. 어떤 사람은 다른 사람과 악수하는 것이 불가능하기 때문입니다(n > 1인 경우).따라서 n명의 사람이 비어있지 않은 최대 n-1개의 구멍에 배치되므로 원칙이 적용됩니다.

이 핸드쉐이킹 예는 두 개 이상의 정점이 있는 그래프에서 동일한 ^[8]정도를 공유하는 정점 쌍이 적어도 하나 있다는 문장과 동일합니다.이것은 각 사람을 꼭지점에 연관시키고 각 모서리를 악수로 연관시킴으로써 볼 수 있다.

머리 세기

런던에는 적어도 두 사람이 있어야 하며,^[9][10] 머리에는 다음과 같이 같은 털이 나 있다.일반적인 인간의 머리는 평균 약 150,000개의 털을 가지고 있기 때문에, 머리에 1,000,000개 이상의 털을 가지고 있는 사람은 없다고 가정하는 것이 타당하다(m = 100만 개의 구멍).런던에는 100만 명이 넘는 사람들이 있다.머리털의 개수에 따라 비둘기구멍을 할당하고 머리털의 개수에 따라 사람을 비둘기구멍에 할당하는 경우, 1001번째 할당(머리에 같은 수의 털이 있기 때문에)에 의해 적어도 2명이 같은 비둘기구멍에 할당되어야 한다(또는 n>m).런던의 ^[11]인구가 900만2천명이라고 가정하면, 적어도 10명의 런던인은 머리카락 수가 같다고 말할 수 있는데, 이는 100만개의 비둘기 구멍에 각각 9명의 런던인이 있다는 것이 900만 명에 불과하기 때문이다.

제한이 있는 평균 사례(m = 150,000)의 경우, 중복이 가장 적으면 모든 비둘기 홀에 최대 1명, 다른 사람과 동일한 비둘기 홀에 150,0001번째 사람이 배정된다.이 제약이 없는 경우 150,0001번째 사용자보다 먼저 "충돌"이 발생하기 때문에 빈 비둘기구멍이 있을 수 있습니다.이 원리는 중복의 존재를 증명할 뿐이며 중복의 수에 대해서는 언급하지 않습니다(확률 분포의 대상이 됩니다).

A History of the Atheny Society의 이 원칙의 영어 버전에는 "A Supplement to the Athernet Oracle:고대 아테네 머큐리에 남아 있는 질문과 답변 모음집" (런던 앤드류 벨, 1710년 ^[12]인쇄).이 세상에 머리에 털이 같은 사람이 두 명이나 있을까?1704년 ^[13][14]이전에 아테네 머큐리에서 길러졌다.

아마도 비둘기홀 원리에 대한 첫 번째 언급은 1622년 프랑스 예수회 신학자 장 루레촌이 ^[2]쓴 라틴어 작품 셀렉테 프로포지션의 짧은 문장에서 나타나는데, 그는 "두 남자가 서로 ^[15]같은 수의 머리카락, 에쿠스, 또는 다른 것들을 가지고 있어야 한다."고 썼다.2년 후, 류촌이 쓴 것으로 알려진 또 다른 책에서 완전한 원리는 추가 사례와 함께 설명되었다. 그러나 그의 ^[2]제자 중 한 명이 쓴 것일 수도 있다.

생일 문제

생일 문제는 무작위로 선택된 n명의 사람들에게, 그들 중 몇 쌍이 같은 생일을 가질 확률이 얼마나 되는지 묻습니다.문제 자체는 주로 직관에 반하는 확률과 관련되어 있습니다.그러나 우리는 비둘기구멍의 원칙에 의해서도 알 수 있습니다.만약 방에 367명이 있다면, 적어도 한 쌍의 사람들이 100% 확률로 같은 생일을 공유합니다.이는 366명의 가능한 생일 중에서 선택할 수 있기 때문입니다(2월 29일, 만약 미리 선택된다면 포함).nt)

단체전

팀 토너먼트(n = 7개 항목)에 참가하고 싶은 7명의 선수를 상상해 보십시오. 단 4개 팀(m = 4홀)의 제한이 있습니다.비둘기 홀 원칙은 그들이 모두 다른 팀에서 경기할 수 없다는 것을 말해준다. 7명 중 적어도 2명 이상의 선수로 구성된 팀이 있어야 한다.

$\displaystyle \left \lfloor \frac {n-1} {m} \right \lfloor +1=\left \lfloor +1=1+1=2}$

부분집합

집합 S = {1,2,3,9}의 크기 6의 하위 집합에는 합계가 10인 두 개의 원소가 포함되어야 합니다.비둘기 구멍에는 두 가지 요소 하위 집합 {1,9}, {2,8}, {3,7} 및 싱글톤 {5, 총 5개의 비둘기 구멍으로 레이블이 지정됩니다.6개의 "비둘기" (크기 6개의 서브셋의 요소)가 라벨에 포함된 비둘기 구멍으로 들어가는 각각의 비둘기 구멍에 배치될 때, 2개의 서브셋으로 표시된 비둘기 구멍 중 적어도 1개는 ^[16]비둘기 구멍에 2개의 비둘기를 갖게 됩니다.

용도 및 응용 프로그램

이 원리는 어떤 무손실 압축 알고리즘이 (압축이라는 이름에서 알 수 있듯이) 일부 입력을 더 작게 만든다면 다른 입력도 더 크게 만든다는 것을 증명하기 위해 사용될 수 있습니다.그렇지 않으면 (압축이 무손실이기 때문에) 특정 길이 L까지의 모든 입력 시퀀스 세트를 충돌 없이 (대부분) 더 작은 길이의 모든 시퀀스 세트에 매핑할 수 있습니다.이것은 비둘기 홀 원리에 의해 제외됩니다.

수학 해석에서 주목할 만한 문제는 고정 비합리수 a에 대해 부분 부분 집합 {[na]: n이 정수}이 [0, 1]에서 조밀하다는 것을 보여주는 것이다.na - m < e (e > 0은 작은 양의 수, a는 임의의 비합리수)인 정수 n, m을 명시적으로 찾는 것은 쉽지 않다는 것을 알 수 있다.그러나 1/M < e가 되도록 M을 취할 경우, 비둘기홀 원리에 따라 na와₂ na가 크기 1/M의 동일한 정수 하위 분할에 있도록₁ n₂, n 1 {1, 2, ..., M + 1}이₁ 있어야 한다(연속되는 정수 간에는 M의 하위 분할만 있음).특히 na가 (p + k/M, p + (k + 1)/M), na가₂ (q + k/M, q + (k + 1)/M에 있는 n₁, n을₂ 찾을₁ 수 있다.그러면 (n₂ - n₁)a가 (q - p - 1/M, q - p + 1/M)에 있는지 쉽게 확인할 수 있다.이는 [na] < 1/M < e, 여기서 n = n₂ - n₁ 또는 n = n₁ - n을₂ 의미한다.이는 0이 {[na]}의 제한점임을 나타냅니다.그런 다음 이 사실을 사용하여 p in (0, 1)의 대소문자를 증명할 수 있습니다. [na] < 1/M < e가 되도록 n을 찾습니다.그러면 p ( (0, 1/M)가 되면 증명은 완료됩니다.그렇지 않으면 p δ(j/M, (j + 1)/M) 및 k = sup{r δ N : r[na] < j/M 을 설정하면 [(k + 1)na] - p < 1/M < e 를 얻을 수 있다.

변형은 많은 증거에서 발생합니다.정규 언어의 펌핑 보조어 증명에서는 유한 집합과 무한 집합을 혼합한 버전이 사용됩니다.무한히 많은 오브젝트가 여러 박스에 배치되어 있는 경우,^[17] 상자를 공유하는 오브젝트가 2개 존재합니다.미술관의 문제에 대한 Fisk의 해결책에서는 다음과 같은 역설이 사용됩니다.n개의 객체가 k개의 상자에 배치되어 있는 경우, 최대 n/k개의 ^[18]객체가 들어 있는 상자가 있습니다.

대체 제제

다음은 비둘기 구멍 원리의 대체 공식이다.

1. n개의 객체가 m개의 장소에 분산되어 있고 n> m 의 경우, 어떤 장소에서는 적어도2개의 ^[1]객체를 수신합니다.
2. (1의 등가 공식) n개의 오브젝트가 n개의 장소에 분산되어 있는 경우, 어떤 장소도 여러 오브젝트를 수신하지 않는 경우, 각 플레이스는 정확히1개의 ^[1]오브젝트를 수신합니다.
3. n개의 객체가 m개의 장소에 분산되어 있고 n < m 의 경우, 어떤 장소에서는 객체가 수신되지 않습니다.
4. (3의 등가 공식) n개의 오브젝트가 n개의 장소에 분산되어 있어 어떤 장소도 오브젝트를 수신하지 않는 경우, 각 플레이스는 정확히1개의 오브젝트를 ^[19]수신합니다.

튼튼한 형태

q₂, q, ..., q를_n 양의 정수라고 합니다₁.한다면

${\displaystyle q_{1}+q_{2}+\cdots +q_{n}-n+1}$

오브젝트는 n개의 상자로 분산되며 첫 번째 상자에는 적어도q개의₁ 오브젝트가 포함되어 있거나 두 번째 상자에는 적어도q개의₂ 오브젝트, ...가 포함되어 있거나 n번째 상자에는 적어도q개의_n ^[20]오브젝트가 포함되어 있습니다.

여기서 q₂ = q = ...를₁ 취하면 간단한 형식을 얻을 수 있습니다. = q_n = 2로, n + 1개의 객체를 제공합니다.q₁₂ = q =... = q_n = r은 보다 정량화된 버전의 원칙을 제공한다. 즉, 다음과 같다.

n과 r을 양의 정수라고 합니다.n(r - 1) + 1개의 오브젝트가 n개의 박스에 분산되어 있는 경우, 적어도1개의 박스에는 r개 이상의 ^[21]오브젝트가 포함됩니다.

이는 k개의 개별 객체가 n개의 컨테이너에 할당되는 경우 적어도1개의 컨테이너에 ${\displaystyle \mathrm{적어도}}$"${\displaystyle k}$/n$"$ (\$displaystyle\lceil k/n$\rceil$)$ 객체가 있어야 합니다.여기서${\displaystyle }$"$"$ (\$displaystyle\lceil$ x$\rceil)$는 x보다 크거나 같은 최소 정수를 나타냅니다.1개의 컨테이너에는${\displaystyle }$"${\displaystyle k}$/$n"$개체(${\displaystyle \mathrm{여기}}$서 "x$"$개체는 "x"개체(\displaystyle$\lfloor$ x$\displayloor")$개체)를$$ 초과할 수 없습니다.여기서${\displaystyle }$"x"개체는 x보다 작거나 같은 최대 정수를 나타냅니다.

비둘기홀 원리의 일반화

비둘기홀 원리의 확률론적 일반화에 따르면 n마리의 비둘기가 균일한 확률 1/m의 m개의 비둘기홀에 무작위로 투입될 경우, 적어도 1개의 비둘기홀은 확률로 둘 이상의 비둘기를 수용할 것이다.

${{displaystyle 1-{\frac {(m)_{n}}}{m^{n}}}}$

여기서 (m)_n은 하강 요인 m(m - 1)(m - 2)...(m - n + 1)입니다.n = 0 및 n = 1(및 m > 0)의 경우, 그 확률은 0이다. 즉, 비둘기가 1마리만 존재하면 충돌이 발생할 수 없다.n > m(비둘기 구멍보다 비둘기 수가 많다)의 경우, 이는 1이며, 이 경우 일반적인 비둘기 구멍 원리와 일치한다.그러나 비둘기 수가 비둘기 구멍의 수(n µ m)를 초과하지 않더라도 비둘기 구멍에 비둘기를 할당하는 무작위 특성 때문에 충돌이 발생할 가능성이 크다.예를 들어, 비둘기 2마리가 4개의 비둘기 구멍에 무작위로 할당되면, 적어도 1개의 비둘기 구멍에 2마리 이상의 비둘기가 있을 확률은 25%입니다. 비둘기 5개와 10개의 구멍에 대해서는 69.76%이고, 비둘기 10개와 20개의 구멍에 대해서는 약 93.45%입니다.구멍 수가 고정되어 있으면 비둘기를 추가할 때 쌍이 생길 확률이 항상 높아집니다.이 문제는 생일 역설에서 훨씬 더 길게 다뤄진다.

또 다른 확률론적 일반화는 실수치 랜덤 변수 X가 유한 평균 E(X)를 가질 때 X가 E(X)보다 크거나 같을 확률은 0이 아니며 마찬가지로 X가 E(X)보다 작거나 같을 확률은 0이 아니라는 것이다.이것이 표준 비둘기 구멍 원리를 의미하는지 확인하려면 n개의 비둘기를 m개의 구멍에 고정 배치하고 X를 무작위로 균일하게 선택한 구멍의 비둘기 수로 한다.X의 평균은 n/m이므로 비둘기가 구멍보다 많으면 평균이 1보다 큽니다.따라서 X는 최소 2가 될 수 있습니다.

무한 집합

비둘기홀 원리는 기수로 표현함으로써 무한 집합까지 확장할 수 있습니다.세트 A의 카디널리티가 세트B의 카디널리티보다 클 경우 A에서B로의 주입은 없습니다.단, 이 형식에서는 세트A의 카디널리티가 세트B의 카디널리티보다 크다는 스테이트먼트의 의미는 A에서B로의 주입 맵이 존재하지 않는다는 것을 의미하기 때문에 원칙은 반복적입니다.다만, 적어도 1개의 요소를 유한 세트에 추가하는 것으로써, 카디널리티가 증대하는 것을 보증하는데 충분하다.

유한 집합의 비둘기 구멍 원리를 표현하는 또 다른 방법은 유한 집합이 데데킨드 유한이라는 원리와 유사합니다.A와 B를 유한 집합으로 하자.A에서 B로 사출하지 않는 사출이 있는 경우, A에서 B로 사출하지 않습니다.사실 A에서 B까지 어떤 종류의 기능도 주입되지 않습니다.무한 집합에는 해당되지 않습니다.1과 2를 1, 3과 4를 2, 5와 6을 3으로 보내는 자연수의 함수를 생각해 보겠습니다.

무한 집합에도 비슷한 원리가 있다: 셀 수 없을 정도로 많은 비둘기들이 셀 수 없을 정도로 많은 비둘기 구멍에 채워진다면, 셀 수 없이 많은 비둘기들이 채워진 비둘기 구멍은 적어도 하나 이상 존재할 것이다.

그러나 이 원리는 유한 집합의 비둘기 구멍 원리를 일반화하지 않는다.유한 집합의 경우 일반적으로 잘못된 것입니다.기술적 용어로 A와 B가 유한 집합이기 때문에 A에서 B로 가는 어떤 사출함수도 사출함수가 아닌 경우, B의 원소 B가 존재하여 B의 원소와 A의 원소 사이에 사출이 존재한다고 한다.이것은 상당히 다른 진술이며, 큰 유한 기수에는 불합리합니다.

양자역학

야키르 아로노프 외양자역학에서 비둘기홀 원리를 위반할 수 있다는 주장을 제시했고 ^[22]양자역학에서 비둘기홀 원리를 테스트하기 위해 간섭계 실험을 제안했다.하지만, 이후의 연구는 이 결론에 ^[23][24]의문을 제기했습니다.2015년 1월 arXiv 프리프린트에서 버밍엄 대학의 Alastair Rae와 Ted Forgan 연구원은 간섭계를 통한 다양한 에너지에서 전자의 비행에 대해 표준 비둘기 구멍 원리를 사용하여 이론적인 파동 함수 분석을 수행했다.만약 전자가 상호작용 강도가 전혀 없다면, 각각의 전자는 하나의 완벽한 원형의 피크를 만들어 낼 것이다.높은 상호작용 강도에서 각 전자는 검출기에서 총 12개의 피크를 위해 4개의 뚜렷한 피크를 생성한다. 이러한 피크는 각 전자가 경험할 수 있는 4개의 가능한 상호작용의 결과이다(첫 번째 다른 입자만, 두 번째 다른 입자만 또는 세 개 모두 함께).많은 실제 실험에서와 같이 상호작용 강도가 상당히 낮다면 제로 상호작용 패턴으로부터의 편차는 거의 식별 불가능할 것이며, 이러한 패턴을 관측하는 데 사용되는 검출기와 같은 고체 내 원자의 격자 간격보다 훨씬 작을 것이다.이것은 약하지만 0이 아닌 상호작용 강도와 어떤 상호작용도 구별하는 것을 매우 어렵게 만들며, 따라서 세 개의 모든 경로가 두 개의 경로를 통과함에도 불구하고 상호작용하지 않는 세 개의 전자의 착각을 일으킨다.

「 」를 참조해 주세요.

• 선택 공리
• 블리히펠트의 정리
• 조합 원리
• 조합 증명
• 데데킨트 무한집합
• 힐베르트의 그랜드 호텔의 역설
• 다항 정리
• 램지의 정리
• 포치해머 기호

메모들

레퍼런스

• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pentice Hall, ISBN 978-0-13-602040-0
• Fletcher, Peter; Patty, C.Wayne (1987), Foundations of Higher Mathematics, PWS-Kent, ISBN 978-0-87150-164-6
• Grimaldi, Ralph P. (1994), Discrete and Combinatorial Mathematics: An Applied Introduction (3rd ed.), Addison-Wesley, ISBN 978-0-201-54983-6
• Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016

외부 링크

• "Dirichlet box principle", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• "비둘기 구멍 원리의 이상한 경우"; 에즈거 다이크스트라는 원리의 해석과 재구성을 조사한다.
• '비둘기 구멍 원리' 래리 쿠식(Larry Cusick)이 사용하고 있는 원리의 기본적인 예.
• 알렉산더 보고몰니의 기본적인 비둘기 홀 원리 분석과 예시인 "대화형 수학 잡셀러리와 퍼즐의 피죤 홀 원리"
• "피죤홀 원리의 16가지 재미있는 응용"; 원리에 의해 도출된 흥미로운 사실들.
• "How Many Humans Have the Same Number of Body Hairs?". PBS Infinite Series. December 1, 2016. Archived from the original on 2021-12-11 – via YouTube.