6.0 제6장의 목차

제6장의 목차는 다음과 같다.

     6.1 비둘기집 원리

6.1 비둘기집 원리

6.1 비둘기집 원리

 

     6.2 램지정리(Ramzey's Theorm)

6.2 램지정리(Ramzey's Theorem)

6.2 램지정리(Ramzey's Theorem)

 

     6.3 램지수(Ramsey number)

6.3. 램지 수(Ramsey number)

6.3. 램지 수(Ramsey number)

 

'비둘기집 원리'는 단순해 보이지만 수학의 여러 정리를 증명하는데 강력한 도구로 쓰여왔다.

 

예를 들어, 다음의 '디리글레의 근사정리(Dirichlet's Approximation Theorem)'가 간단히 증명할 수 있다. 이 정리는 모든 무리수는 유리수를 통해 얼마든지 가깝게 근사할 수 있다는 내용을 담고 있다.

임의의 무리수 $\alpha$와 2이상의 자연수 $Q$에 대해 다음 부등식을 만족하는 두 정수 $p, q(0<q<Q)$가 존재한다.
   $|q \cdot \alpha - p| \leq \frac{1}{Q}$

 

증명을 위해 다음고 같이 $Q+1$개의 수를 생각한다. 여기서 $\displaystyle [x]$는 $x$보다 넘지 않는 최대정수이다.

   $0, 1,\alpha-[\alpha], 2\alpha-[2\alpha], \cdots, (Q-1)\alpha -[(Q-1)\alpha]$

 

이 수들은 모두 0이상 1이하의 값을 가진다.(왜일까?) $\displaystyle [x]$의 정의 때문인데, 이것에 대한 설명은 생략한다. 또한, $\alpha$는 무리수이므로 이 수들은 모두 다른 수이다. 이게 구간 $[0,1]$을 $Q$등분하면 비둘기집 원리에 의해 어느 한 구간에는 위의 두 수 중 어느 두 수가 들어있게 된다. 어떤 두 수가 되든지간에 두 수의 차는

   $|q \cdot \alpha - p| \ (0<q<Q)$

의 꼴로 쓸 수 있고, 그 값은 $\displaystyle \frac{1}{Q}$이하이므로 증명은 완성된다.