이산수학 비둘기집의 원리 알아봅시다

간단하지만 첨예한 비둘기집 원리

🐦 비둘기집 원리란?

비둘기집 원리는 아주 간단한 아이디어에서 출발합니다.

n+1 마리의 비둘기를 n개의 집에 넣으면, 적어도 한 집에는 두 마리 이상의 비둘기가 들어간다.

 

너무 당연해 보이죠? 하지만 단순하기만 이 원리는 수학, 컴퓨터 과학, 정보 이론, 심지어 일상생활에서도 놀라운 응용력을 발휘합니다.

📦 수학적 정의

비둘기집 원리는 다음과 같이 정의됩니다:

어떤 항목의 개수가 그 항목을 담을 수 있는 그룹의 개수보다 많다면, 최소한 하나 이상의 그룹에는 두 개 이상의 항목이 들어간다.

 

이 원리는 귀류법으로 증명이 됩니다. 증명은 나무위키에서 확인하시기 바랍니다.
비둘기집 나무위키

비둘기 집의 원리

 

🧠 일상 속 예시

1. 생일이 같은 사람이 있다?

한국에는 약 5천만 명이 삽니다. 태어날 수 있는 날은 365일이죠(윤년 제외). 5천만 명이 365일이라는 ‘비둘기집’에 들어간다고 생각하면, 반드시 생일이 같은 사람들이 존재한다는 걸 알 수 있습니다.

2. 양말을 뽑는 문제

어두운 방에서 검정색, 흰색, 회색 양말이 각각 여러 켤레 있습니다. 몇 개를 뽑아야 최소한 같은 색 양말 2개를 확실히 뽑을 수 있을까요?

 

답: 4개

이유: 3개의 색(비둘기집)에 4개의 양말(비둘기)을 넣으면, 어떤 색깔은 반드시 2개 이상 존재합니다.

 

 

🧮 수학 문제 적용 예시

문제:

0 이상 99 이하의 정수가 11개 주어졌을 때, 이들 중 두 수의 차가 10의 배수인 쌍이 존재함을 증명하라.

해결:

• 0~99의 정수를 10으로 나눈 나머지는 0~9 (총 10개, 비둘기집).
• 숫자 11개(비둘기)가 10개의 나머지 분류(비둘기집)에 들어간다.
• 따라서 최소한 두 수는 같은 나머지를 가지며, 두 수의 차는 10의 배수!

 

💡 프로그래밍에도 쓰인다?

컴퓨터 과학에서도 비둘기집 원리는 유용합니다.

• 해시 충돌: 해시 함수로 만든 값은 유한하지만 입력은 무한. 비둘기집 원리에 따라 해시 충돌은 피할 수 없음.
• 데이터 압축: 모든 데이터를 압축하는 건 불가능. 이유? 압축 가능한 경우보다 원본 데이터가 훨씬 많기 때문!

 

✨ 마치며

비둘기집 원리는 굉장히 단순하지만 응용력이 어마어마합니다. 어찌보면 너무 당연해서 지나칠 내용을 끄집어내서 하나의 원리로 처음 사용한 사람은 누구인지 정말 똑똑한 사람인 듯합니다. 비둘기집 원리로 단지 "더 많다"는 이유 하나만으로도 우리는 무언가 반드시 일어난다는 확실한 결론을 얻을 수 있죠. 뭔가 불가능해 보이는 상황에서 이 원리를 한번 떠올려 보세요. 해결의 실마리를 줄지도 모릅니다.

 

함께보면 좋은글

이산수학의 6가지 논리 연산자 (부정, 논리곱, 논리합, XOR, 함축, 쌍조건)

이산수학 자주 사용하는 기호모음(뜻 포함)

[파이썬 자료구조] HashTable 충돌 시 적용 알고리즘

[파이썬 자료구조] 해쉬테이블 구현해보기