비둘기집 원리$(\text{Pigeonhole Principle})$

우리가 여섯 켤레의 양말을 아무렇게나 서랍에 넣는다고 해 봅시다. 그런데 서랍이 다섯 칸밖에 없다면 어떤 일이 벌어질까요? 어느 서랍에는 반드시 두 켤레 이상의 양말이 들어가게 됩니다. 이 단순한 사실이 오늘 이야기할 비둘기 집 원리$(\text{Pigeonhole Principle})$입니다.비둘기 집 원리는 다음과 같이 수학적으로 표현할 수 있습니다. $n+1$개의 물체를 $n$개의 상자에 넣으면, 적어도 하나의 상자에는 두 개 이상의 물체가 들어간다. 이 원리는 너무 당연해 보이지만, 다양한 수학 문제에서 중요한 역할을 합니다. 몇 가지 예시를 들어보겠습니다.Example 1. 400명이 모여 있을 때, 이들 중 두 사람 이상은 생일이 같음을 보여라. 사람의 생일은 윤년을 고려해도 총 366가지뿐인..

2025.04.13