N+1개의 물건을 N개의 상자에 넣으면, 적어도 하나의 상자에는 두 개 이상의 물건이 들어간다. 오늘은 당연하면서도 다양한 곳에 적용할 수 있는 비둘기집 원리에 대해 알아보겠다. 증명 N+1개의 물건과 N개의 상자가 있을 때, 각 상자에는 한 개 이하의 물건만 들어가있다고 가정해보자. 각 상자에는 최대 1개의 물건이 있을 것이므로, 총 물건의 수는 많아야 N개이다. 그런데 N+1개의 물건이 있으므로, 이는 모순이다. 따라서 N+1개의 물건과 N개의 상자가 있을 때, 적어도 하나의 상자에는 두 개 이상의 물건이 들어간다. 귀류법을 이용해 쉽게 증명하였다. 귀류법이란 명제의 결론이 부정임을 가정했을 때 모순 발생함을 보여 명제가 참임을 증명하는 방법이다. 예시 한 반에 13명 이상의 학생이 있다면, 최소 2..
