비둘기집의 원리

경시문제를 풀다보면 종종 비둘기집의 원리라는 방법에 의한 풀이를 종종보게됩니다.

 

우선 비둘기집의 원리란 n개의 비둘기집에 n+1마리의 비둘기가 들어간다면
비둘기집중에서 비둘기가 2마리이상 들어간 비둘기집이 반드시 존재한다.
라는 내용입니다. 원리는 간단하구요...

비둘기집의 원리를 사용한 문제는 다음과 같습니다.
가로 세로가 각각 4cm인 정사각형에 5개의 점을 찍으면

두점사이의 거리가 최소한 2√2보다 작은 두점이 존재한다는 내용입니다.

증명해보면 가로세로 2cm인 4개의 정사각형으로 나눕니다.

그러면 정사각형 하나가 비둘기집 하나가 되는 것이구요...

점하나가 비둘기 한마리가 되는 것이지요...

그러면 비둘기집의 원리에 의해서

하나의 정사각형에는 두점이상들어 가는 두점이 반드시 생기게 되구요...

그 두점사이의 거리는 대각선 최대값인 2√2보다 작게 되는 거죠...

원리 자체는 매우 간단한 것이구요.
응용할 때 어려운 것이라고 보시면 되겠습니다.