맨위로가기

비둘기집 원리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

비둘기집 원리는 n개의 비둘기집에 n+1마리 이상의 비둘기를 넣으면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어간다는 원리이다. 이는 간단한 귀류법으로 증명되며, 여러 분야에서 활용된다. 소프트볼 팀 구성, 해시 테이블에서의 충돌, 비손실 데이터 압축, 생일 문제, 양말 짝 맞추기, 13명 중 같은 달에 태어난 사람, 정규 언어 펌핑 보조 정리, 미술관 문제 등 다양한 예시에 적용된다. 또한 일상생활, 컴퓨터 과학, 수학 등 여러 분야에서 응용되며, 일반화된 형태와 양자역학에서의 논의도 존재한다. 어원은 디리클레가 사용한 '서랍'이라는 단어에서 유래되었으며, 여러 언어에서 유사한 용어로 번역되어 사용된다.

더 읽어볼만한 페이지

  • 이산수학 정리 - 애로의 불가능성 정리
    애로의 불가능성 정리는 3개 이상의 선택지에서 약한 파레토, 무관한 대안으로부터의 독립성, 비독재성을 모두 만족하는 사회 후생 함수는 존재하지 않음을 증명한 정리이다.
  • 이산수학 정리 - 최소극대화
    최소극대화는 게임 이론에서 상대방의 최악의 수를 고려하여 자신의 최선의 수를 선택하는 의사 결정 방식이며, 게임 트리로 각 국면의 평가값을 계산하여 완전 정보 게임의 해법을 찾고, 알파-베타 가지치기와 같은 알고리즘으로 탐색 효율을 높이는 데 사용된다.
  • 램지 이론 - 램지의 정리
    램지의 정리는 주어진 조건을 만족하는 램지 수가 존재한다는 정리로, 그래프 이론으로 해석되며, 특정 크기의 동색 클릭이 존재함을 보장하고, 램지 이론의 시초로 여겨진다.
  • 램지 이론 - 세메레디의 정리
    세메레디의 정리는 양의 상부 밀도를 갖는 자연수 부분집합이 임의 길이의 등차수열을 포함한다는 내용으로, 세메레디 엔드레가 증명하고 힐렐 퓌르스텐베르크가 다른 증명을 제시했으며, 반 데르 바르덴 정리의 일반화이자 그린-타오 정리와 연관된다.
  • 이산수학 - 고속 푸리에 변환
    고속 푸리에 변환(FFT)은 이산 푸리에 변환(DFT)을 효율적으로 계산하는 알고리즘으로, 연산 횟수를 줄여 디지털 신호 처리, 이미지 처리, 음향 분석 등 다양한 분야에 활용되며 쿨리-튜키 알고리즘 등이 대표적이다.
  • 이산수학 - 조합론
    조합론은 이산적인 대상의 개수를 세거나 조건을 만족하는 대상을 구성, 분류하는 수학 분야로, 순열, 조합에서 시작해 그래프 이론, 설계 이론 등 다양한 조합적 구조와 관련된 문제를 연구하며 여러 학문 분야에 응용된다.
비둘기집 원리
개요
이름비둘기집 원리
다른 이름디리클레 상자 원리
디리클레 서랍 원리
독일어 이름Schubfachprinzip (슈브파흐프린치프)
영어 이름Pigeonhole principle (피전홀 프린시플)
Dirichlet's box principle (디리클레 박스 프린시플)
Dirichlet's drawer principle (디리클레 드로어 프린시플)
설명
내용만약 n개의 비둘기를 m개의 비둘기집에 넣을 때, n > m 이라면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어 있어야 한다.
수식n = km + 1 (n은 km + 1)
추가 설명m개의 상자에 n개의 물건을 넣을 때, 어떤 상자에는 적어도 k + 1개의 물건이 들어 있다.

2. 증명

간단한 귀류법으로 증명할 수 있다. 모든 비둘기가 집에 들어간다고 가정하고, ''n''개의 비둘기집과 ''n+1''마리의 비둘기가 있다고 가정한다. 만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 ''n''마리의 비둘기가 존재한다. 그런데 비둘기는 모두 ''n+1''마리이므로, 이것은 모순이다. 따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.

이 증명은 대표적인 존재 증명이다. 즉, 비둘기가 두 마리 이상 존재하는 집이 정확히 어떤 집인지는 이 증명으로 알아낼 수 없다.

3. 용례

비둘기집 원리는 다양한 실제 상황과 수학적 문제에 적용될 수 있다. 예를 들어, 세 개의 둥지가 있고 네 마리의 비둘기가 둥지로 돌아간다고 가정해 보자. 처음 세 마리의 비둘기는 각각 비둘기가 없는 둥지로 돌아갈 수 있지만, 네 번째 비둘기는 이미 비둘기가 있는 둥지만을 선택할 수밖에 없다. 따라서 어느 둥지에는 반드시 두 마리 이상의 비둘기가 있게 된다.[28]

이 원리는 다음과 같은 다양한 분야에 응용된다.


  • 일상생활 (자세한 내용은 하위 섹션 '일상생활' 참조)
  • 컴퓨터 과학 (자세한 내용은 하위 섹션 '컴퓨터 과학' 참조)
  • 수학 (자세한 내용은 하위 섹션 '수학' 참조)

3. 1. 일상생활


  • 5명의 사람이 소프트볼 경기를 하기 위해 4개의 팀으로 나누어질 때, 최소 2명은 같은 팀에 속해야 한다.
  • 보이지 않는 방에서 4쌍의 양말 중 5개 이상을 고르면, 반드시 같은 짝의 양말이 존재한다.
  • 13명의 사람들 중에는 생일의 월(月)이 같은 사람이 최소 2명 이상 있다.
  • 367명 이상의 사람이 모이면, 생일이 같은 사람이 최소 2명 이상 존재한다.[8]

3. 2. 컴퓨터 과학

해시 테이블에서 예상되는 키의 종류가 테이블의 배열 길이를 초과하는 경우, 테이블의 인덱스가 충돌하지 않는 값을 출력하는 해시 함수(완전 해시 함수)는 존재하지 않는다는 것을 비둘기집 원리로 증명할 수 있다.[29][30]

무손실 압축 알고리즘의 압축 처리 후 데이터 크기가 작아지는 입력 데이터가 존재하는 경우, 압축 처리 후 데이터 크기가 커지는 입력 데이터도 반드시 존재한다는 것을 비둘기집 원리를 사용하여 증명할 수 있으며, 구체적인 증명 과정은 다음과 같다.

# "압축 처리 후 데이터 크기가 작아지는 입력 데이터가 존재하고, 압축 처리 후 데이터 크기가 커지는 입력 데이터가 존재하지 않는다"고 가정한다.

# 압축 처리 후 데이터 크기가 작아지는 입력 데이터 중 가장 작은 입력 데이터를 F로 하고, 그 데이터 크기를 M 비트로 한다. F의 압축 처리 후의 데이터 크기를 N 비트로 한다(M < N).

# 압축 처리 후 데이터 크기가 커지는 입력 데이터가 존재하지 않으므로, N비트의 데이터는 압축 처리 후에도 N비트가 된다.

# N비트의 데이터는 2N종류가 있다. 압축 처리 후 N비트가 되는 데이터는 적어도 2N+1 종류 존재한다.

# N비트의 데이터가 2N 종류밖에 없으므로, '''비둘기집 원리'''에 의해 적어도 2종류의 데이터가 압축 후 같은 데이터가 되어 해제가 불가능하다.

# 따라서 첫 번째 가정은 오류이며, "압축 처리 후 데이터 크기가 작아지는 입력 데이터가 존재하지 않는다"(무손실 압축 알고리즘이 아님)거나 "압축 처리 후 데이터 크기가 커지는 입력 데이터가 존재한다"가 된다.

3. 3. 수학


  • 해시 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다. 따라서 어떤 해시 함수도 충돌을 피할 수는 없다. (해시 충돌 참고)[17]
  • 수학적 분석에서 고정된 무리수 에 대해 분수 부분의 집합 { [ n a ] : n ∈ Z } {\displaystyle \{[na]:n\in \mathbb {Z} \}} 이 [0, 1]에서 조밀함을 보일 수 있다. | n a − m | < e , {\displaystyle |na-m| 0 {\displaystyle e>0} 은 작은 양수이고 a {\displaystyle a} 는 임의의 무리수일 때, 정수 n , m {\displaystyle n,m} 을 명시적으로 찾는 것이 쉽지 않다는 것을 알 수 있다. 하지만 1 M < e , {\displaystyle {\tfrac {1}{M}}[18]

: n 1 a ∈ ( p + k M , p + k + 1 M ) , n 2 a ∈ ( q + k M , q + k + 1 M ) , {\displaystyle n_{1}a\in \left(p+{\frac {k}{M}},\ p+{\frac {k+1}{M}}\right),\quad n_{2}a\in \left(q+{\frac {k}{M}},\ q+{\frac {k+1}{M}}\right),}

어떤 p , q {\displaystyle p,q} 정수와 k ∈ { 0 , 1 , . . . , M − 1 } {\displaystyle k\in \{0,1,...,M-1\}} 에 대해. 그러면 다음을 쉽게 확인할 수 있다.

: ( n 2 − n 1 ) a ∈ ( q − p − 1 M , q − p + 1 M ) . {\displaystyle (n_{2}-n_{1})a\in \left(q-p-{\frac {1}{M}},\ q-p+{\frac {1}{M}}\right).}

이는 [ n a ] < 1 M < e , {\displaystyle [na]<{\tfrac {1}{M}}
: p ∈ ( j M , j + 1 M ] , {\displaystyle p\in \left({\frac {j}{M}},\ {\frac {j+1}{M}}\right],}

그리고

: k = sup { r ∈ N : r [ n a ] < j M } , {\displaystyle k=\sup \left\{r\in N:r[na]<{\frac {j}{M}}\right\},} 를 설정하여

: | [ ( k + 1 ) n a ] − p | < 1 M < e . {\displaystyle \Bigl |\bigl [(k+1)na\bigr ]-p\Bigr |<{\frac {1}{M}}
  • 정규 언어에 대한 펌핑 보조 정리 증명에서는 유한 집합과 무한 집합을 혼합한 버전이 사용된다. 즉, 무한히 많은 객체가 유한한 수의 상자에 배치되면 두 객체가 상자를 공유한다.[18] 미술관 문제에 대한 Fisk의 해결책에서는 일종의 역이 사용된다. 즉, n {\displaystyle n} 개의 객체가 k {\displaystyle k} 개의 상자에 배치되면, n k {\displaystyle {\tfrac {n}{k}}} 개 이하의 객체를 포함하는 상자가 있다.[19]

    • 4. 비둘기집 원리의 일반화

    n개의 물건을 m개의 상자에 넣으면, 적어도 하나의 상자에는 \(\left\lceil \frac n m \right\rceil\)개 이상의 물건이 들어간다. 여기서 \(\lceil x\rceil\)는 x보다 작지 않은 최소 정수이다.[21]

    확률론적으로 일반화된 비둘기집 원리에 따르면, \(\frac 1 m\)의 균일한 확률로 n개의 비둘기를 무작위로 m개의 비둘기집에 넣었을 때, 적어도 하나의 비둘기집에 두 마리 이상의 비둘기가 들어가게 된다. 이 확률은 다음과 같이 나타낼 수 있다.[22]

    :\(1 - \frac{m!}{(m-n)!\;m^n} = 1 - \frac{m(m-1)(m-2)\cdots (m-n+1)}{m^n} \!\)

    n = 0인 경우와 n = 1인 경우(단, m > 0)에 확률은 0인데, 이는 비둘기가 한 마리 밖에 없다면, 한 비둘기집에 두 마리 이상의 비둘기가 들어가는 '충돌'이 일어날 수 없음을 의미한다. n > m (비둘기가 비둘기집보다 많다)이라면 확률은 1이 되고, 이 경우에는 일반적인 비둘기집 원리와 같은 일이 일어난다. 그러나 비둘기의 수가 비둘기집의 수를 초과하지 않더라도 (\(n \le m\)), 비둘기 분배의 무작위적인 성질에 의해 종종 상당한 확률로 충돌이 일어난다.

    예를 들어, 2마리의 비둘기가 무작위로 4개의 비둘기집에 분배된다면, 25%의 확률로 적어도 하나의 비둘기집에 두 마리 이상의 비둘기가 들어가게 된다. 5마리의 비둘기를 10개의 비둘기집에 분배한다면 확률은 69.76%가 되고, 10마리의 비둘기를 20개의 비둘기집에 분배하면 그 확률은 약 93.45%가 된다.

    생일 문제는 n명의 무작위로 선택된 사람들의 집합에 대해, 그들 중 일부가 같은 생일을 가질 확률을 묻는 문제이다. 비둘기집 원리에 따르면, 367명의 사람들 중에는 100% 확률로 같은 생일을 공유하는 적어도 한 쌍의 사람이 존재하는데, 이는 가능한 생일이 366개밖에 없기 때문이다.

    \(q_1, q_2, ..., q_n\)이 양의 정수라고 할 때, 만약

    :\(q_1 + q_2 + \cdots + q_n - n + 1\)

    개의 객체를 n개의 상자에 분배한다면, 첫 번째 상자에 최소한 \(q_1\)개의 객체가 들어있거나, 두 번째 상자에 최소한 \(q_2\)개의 객체가 들어있거나, ..., 또는 n번째 상자에 최소한 \(q_n\)개의 객체가 들어있다.

    \(q_1 = q_2 = ... = q_n = 1\)로 하여 n + 1개의 객체를 얻을 수 있고, \(q_1 = q_2 = ... = q_n = r\)을 취하면, 만약 \(n(r - 1) + 1\)개의 객체를 n개의 상자에 분배한다면, 상자 중 적어도 하나는 r개 이상의 객체를 포함한다.

    이는 또한, 만약 k개의 이산 객체가 n개의 용기에 할당된다면, 적어도 하나의 용기는 \(\lceil k/n \rceil\)개 이상의 객체를 가져야 하며, 여기서 \(\lceil x\rceil\)는 천장 함수로, x보다 크거나 같은 가장 작은 정수를 나타낸다. 마찬가지로, 적어도 하나의 용기는 \(\lfloor k/n \rfloor\)개 이하의 객체를 가져야 하며, 여기서 \(\lfloor x \rfloor\)는 바닥 함수로, x보다 작거나 같은 가장 큰 정수를 나타낸다.

    비둘기집 원리의 확률적 일반화는 n 마리의 비둘기를 균등한 확률 \(1/m\)로 m 개의 비둘기집에 무작위로 넣으면, 적어도 하나의 비둘기집에 두 마리 이상의 비둘기가 들어갈 확률이

    :\(1 - \frac{(m)_n}{m^n},\)

    이 된다는 것이다. 여기서 \((m)_n\)은 내림 계승 \(m(m - 1)(m - 2)...(m - n + 1)\)이다.

    무한 집합에 대한 비둘기집 원리의 확장은 다음과 같다. 집합의 기수가 집합의 기수보다 크면, 에서 로의 단사 함수는 존재하지 않는다.

    5. 양자역학에서의 비둘기집 원리

    야키르 아하로노프 등은 양자역학이 비둘기집 원리를 위반할 수 있다는 주장을 제시했으며, 양자역학에서 비둘기집 원리를 테스트하기 위한 간섭 실험을 제안했다.[23] 이후 연구에서는 이러한 결론에 의문을 제기했다.[24][25]

    2015년 1월 arXiv 사전 출판물에서, 버밍엄 대학교의 연구원 알래스터 레이와 테드 포건은 파동 함수를 이용한 이론적 분석을 수행하여, 표준 비둘기집 원리를 적용하여 다양한 에너지의 전자가 간섭계를 통과하는 과정을 분석했다. 전자가 전혀 상호작용하지 않는다면, 각 전자는 하나의 완벽한 원형 피크를 생성할 것이다. 높은 상호작용 강도에서는 각 전자가 4개의 뚜렷한 피크를 생성하여 검출기에 총 12개의 피크가 나타난다. 이러한 피크는 각 전자가 경험할 수 있는 네 가지 가능한 상호작용(단독, 첫 번째 다른 입자와 함께, 두 번째 다른 입자와 함께, 또는 셋 모두 함께)의 결과이다. 상호작용 강도가 상당히 낮다면, 많은 실제 실험에서와 같이, 영(zero) 상호작용 패턴으로부터의 편차는 거의 구별할 수 없을 것이며, 이러한 패턴을 관찰하는 데 사용되는 검출기와 같은 고체 내 원자의 격자 간격보다 훨씬 작을 것이다. 이것은 약하지만 0이 아닌 상호작용 강도를 전혀 상호작용이 없는 것과 구별하기 매우 어렵거나 불가능하게 만들 것이며, 따라서 세 개의 전자가 두 개의 경로를 모두 통과했음에도 불구하고 상호작용하지 않은 듯한 착각을 줄 것이다.

    6. 어원

    디리클레는 독일어 Schubfachde 또는 프랑스어 tiroir프랑스어를 사용하여 프랑스어와 독일어로 논문을 출판했다. 이 용어들의 엄격한 원래 의미는 영어 ''drawer''(서랍)에 해당한다. 즉, "내부에 넣고 뺄 수 있는 뚜껑이 없는 상자"를 의미한다. (디리클레는 서랍에 진주를 분배하는 것에 대해 썼다.) 이 용어들은 "사무실, 캐비닛 또는 벽에 편지나 종이를 보관하기 위한 작은 열린 공간"이라는 의미에서 ''비둘기집''으로 바뀌었고, 비둘기를 수용하는 구조에서 은유적으로 파생되었다.[5]

    비둘기집이 있는 가구는 여러 범주로 물건을 보관하거나 분류하는 데 일반적으로 사용되기 때문에 (예: 우체국의 편지 또는 호텔의 객실 열쇠), "pigeonhole"이라는 번역이 디리클레의 원래 "서랍"을 더 잘 표현할 수 있다. 가구의 특징을 나타내는 ''pigeonhole''이라는 용어에 대한 이러한 이해는, 특히 영어를 모국어로 사용하지 않지만 과학계의 공용어로 영어를 사용하는 사람들 사이에서, 비둘기와 구멍이 실제로 관련된 더 그림 같은 해석을 선호하면서 사라지고 있다. "비둘기집"을 "비둘기집"으로 해석하는 암시적인 해석(오해의 소지가 없음)은 최근 "비둘기집 원리"의 독일어 역번역인 Taubenschlagprinzipde으로 다시 사용되었다.[5]

    독일어 원어 Schubfachprinzipde[6]와 프랑스어 Principe des tiroirs프랑스어[7] 외에도 다른 문자적 번역은 여러 언어에서 여전히 사용되고 있다.

    언어번역
    아랍어مبدأ برج الحمامar
    불가리아어принцип на чекмеджетатаbg
    중국어抽屉原理중국어
    덴마크어Skuffeprincippetda
    네덜란드어ladenprincipenl
    헝가리어skatulyaelvhu
    이탈리아어principio dei cassettiit
    일본어引き出し論法일본어
    페르시아어اصل لانه کبوتریfa
    폴란드어zasada szufladkowapl
    포르투갈어Princípio das Gavetaspt
    스웨덴어Lådprincipensv
    튀르키예어çekmece ilkesitr
    베트남어nguyên lý hộpvi


    참조

    [1] harvnb
    [2] 학술지 The pigeonhole principle, two centuries before Dirichlet https://biblio.ugent[...]
    [3] 웹사이트 Pigeonhole principle http://jeff560.tripo[...] 2006-11-11
    [4] harvnb
    [5] 서적 Diskrete Mathematik https://books.google[...] Books on Demand
    [6] 서적 The Induction Book https://books.google[...] Courier Dover Publications 2017-05-17
    [7] 서적 Mathematics Dictionary https://books.google[...] Springer 1992-07-31
    [8] 웹사이트 D3 Graph Theory - Interactive Graph Theory Tutorials https://d3gt.com/uni[...] 2021-01-12
    [9] 서적 The Psychology of Reasoning https://books.google[...] K. Paul, Trench, Trubner & Company, Limited
    [10] 문서
    [11] 웹사이트 London's Population / Greater London Authority (GLA) http://data.london.g[...]
    [12] 웹사이트 A Supplement to the Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries. ... To which is Prefix'd the History of the Athenian Society, ... By a Member of the Athenian Society https://books.google[...]
    [13] 웹사이트 The Athenian Oracle being an entire collection of all the valuable questions and answers https://books.google[...]
    [14] 웹사이트 The Athenian Oracle: Being an Entire Collection of All the Valuable Questions and Answers in the Old Athenian Mercuries. ... By a Member of the Athenian Society https://books.google[...]
    [15] citation Selecæe Propositiones in Tota Sparsim Mathematica Pulcherrimæ Gasparem Bernardum
    [16] harvnb
    [17] 잡지 Combinatorial problems, some old, some new and all newly attacked by computer 1976-10
    [18] 문서 Introduction to Formal Languages and Automata Jones and Bartlett Learning
    [19] 문서 Computational Geometry in C
    [20] harvnb
    [21] harvnb
    [22] 문서
    [23] 학술지 Quantum violation of the pigeonhole principle and the nature of quantum correlations
    [24] 웹사이트 Quantum pigeonholes are not paradoxical after all, say physicists https://physicsworld[...] 2015-01-08
    [25] arXiv On the implications of the Quantum-Pigeonhole Effect 2014-12-03
    [26] 웹사이트 Pigeonhole principle https://www.britanni[...] Britannica
    [27] 서적 ジーゲル: 人と数学 現代数学社
    [28] 웹사이트 当たり前のようで奥が深い 「鳩の巣原理」を知ろう https://www.asahi.co[...] 2021-11-12
    [29] 컨퍼런스 Surprising Computer Science https://books.google[...] Springer 2015-09-28
    [30] 서적 Lossless Compression Handbook (Communications, Networking and Multimedia) Academic Press 2002-12-18


    본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
    모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
    하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
    따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

    문의하기 : help@durumis.com