01. The Pigeonhole Principle

1. The Pigeonhole Principle(비둘기집의 원리)

If there are more pigeons than pigeonholes and every pigeon goes into a pigeonhole, then some pigeonhole must have more than one pigeon in it.

 

 쉽게 말하면 '비둘기의 수가 비둘기집의 수보다 많고, 모든 비둘기가 비둘기집에 들어가야 할 때, 어떠한 비둘기집에는 한 마리 이상의 비둘기가 들어있을 것이다'라는 말이다. 아주 직관적이고 당연하게 들리는 이 문장은, 복잡한 문제를 해결하는 강력한 논리적 도구가 된다.

 

2. Extended Pigeonhole Principle(확장된 비둘기집의 원리)

Theorem 1.3 (곱셈의 관점): For any finite sets X and Y and any positive integer k such that |X| > k · |Y|, if f: X → Y, then there are at least k + 1 distinct members x_1, ..., x_(k+1) such that f(x_1) = ... = f(x_(k+1))

Theorem 1.4 (나눗셈과 올림의 관점): Extended Pigeonhole Principle, Alternate Version. Let X and Y be any finite sets and let f: X → Y. Then there is some y ∈ Y such that f(x) = y for at least
(the ceiling of the quotient of the absolute values of X and Y)
values of x.

 

 기존의 원리를 더 보편적으로 사용할 수 있도록 일반화(Generalization)한 정리이다. Theorem 1.3과 1.4는 같은 원리를 표현 방식만 다르게 정의한 것이며, Theorem 1.4가 더 일반적인 형태이다.

 

3. Fundamental theorem of arithmetic (FTA, 산술의 기본 정리)

Theorem 1.5. The Fundamental Theorem of Arithmetic. There is one and only one way to express a positive integer as a product of distinct prime numbers in increasing order and with positive integer exponents.

n = p_1^e_1 * p_2^e_2 * ... * p_k^e_k

 

 우리가 흔히 아는 소인수분해를 떠올리면 쉽다. 이 정리는 어떤 수의 소인수분해 결과가 세상에 오직 하나뿐이라는 것을 수학적으로 보장한다.

 

4. 소수와 곱셈의 성질

Theorem 1.7. If m, n, and p are integers grater than 1, p is prime, and p | m * n, then either p | m or p | n.

 

 p = 3, m = 4, n = 15라고 가정하자. m과 n의 곱인 60은 소수인 3으로 나누어진다. 이때 원래의 수 중 하나인 n=15 역시 소수 3으로 나누어 떨어지는 걸 볼 수 있다. 즉, 결과물에 특정 소수가 존재한다면, 원래의 수 중 어딘가에는 반드시 그 소수가 있어야 한다는 의미이다.

 

5. Application of Pigeonhole Principle to Number Theory

Choose m distinct numbers between 2 and 40 inclusive, where m ≥ 13. Then at least two of the numbers have some common divisor greater than 1.

 

 비둘기집: 2부터 40 사이의 소수, 즉 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 총 12개

 비둘기: 무작위로 고른 13개의 숫자들(m≥13)

 결론: 비둘기(13개 이상)가 비둘기집(12개) 보다 많으므로, 적어도 한 방(소수)에는 두 개 이상의 숫자가 들어가게 된다. 이는 곧, 같은 소수를 약수로 공유하는 숫자가 적어도 두 개 이상이라는 뜻이므로, 1보다 큰 공약수를 가진다는 결론이 도출된다.