비둘기집 원리(pigeonhole principle) 기본개념 배우기

1. 비둘기집 원리(pigeonhole principle)

 

"n+1개의 물건을 n개의 상자에 넣을때, 최소한 한 상자에는 적어도 2개 이상의 물건이 반드시 들어있다"

 

n+1개의 물건과 n개의 상자가 있으며, 각 상자당 한개씩의 물건만 존재한다고 가정한다면, 최대 n개의 물건이 존재할 수 있는데,

 

물건의 숫자는 n+1개이므로 어느 상자에도 들어가지 못한 물건이 하나 남을 수밖에 없으므로 모순이다.

 

그러므로 각 상자당 한개씩의 물건만 들어가야한다는 가정은 성립할 수 없으며, 적어도 하나의 상자에는 2개 이상의 물건이 존재한다.

 

너무나도 당연한 이 사실에 "비둘기집 원리(pigeonhole principle)"이라는 거창한 이름이 붙은 이유는

 

생각보다 많은 수학적 원리를 증명하기 위해 비둘기집 원리가 사용되며 이름을 붙여 놓으면 "비둘기집 원리에 의해~"라며 증명이 편하기 때문이다 

 

 

2. 예시로 이해하는 비둘기집 원리

 

2-1) Dirichlet's Approximation Theorem

 

모든 무리수는 유리수를 통해 얼마든지 근사시킬 수 있다.

 

임의의 무리수 $\alpha$와 2이상의 자연수 Q에 대하여, 다음 부등식을 만족하는 두 정수 p,q가 반드시 존재한다(q < Q)

 

$$\left | q\alpha - p \right | \leq \frac{1}{Q}$$  

 

증명)

 

다음과 같은 Q+1개의 수를 생각한다.

 

0, 1, $\alpha - \left \lfloor \alpha \right \rfloor$, ... , $(Q-1)\alpha - \left \lfloor (Q-1)\alpha \right \rfloor$

 

위 수들은 모두 0이상 1이하의 값을 가진다.

 

왜냐하면 $\left \lfloor k\alpha \right \rfloor$이 무리수 $k\alpha$의 정수부분을 나타내기 때문이다.

 

또한 $\alpha$가 무리수이므로 이 수들은 모두 다른 수이다.

 

이제 구간 [0,1]을 Q등분하면 비둘기집 원리에 의해 어느 한 구간에는 반드시 위 Q+1개의 수중 어느 두 수가 들어가있게된다.

 

어떤 두 수가 되었든 두 수의 차는 반드시 $\left | q\alpha - p \right |$ (0 < q < Q)의 꼴로 쓸 수 있으며, 

 

[0,1]을 Q등분한 구간의 길이는 $\frac{1}{Q}$이고 이 구간 위에 존재하는 두 수이므로, $\left | q\alpha - p \right | \leq \frac{1}{Q}$이다.

 

 

2-2) 연속합

 

임의의 정수 $a_{1}, a_{2}, ... , a_{n}$이 주어져 있으면 적당한 연속합 $a_{k} + a_{k+1} + ... + a_{k+m}$은 n의 배수

 

증명)

 

$S_{k} = a_{1} + a_{2} + ... + a_{k}$라고 하자. k = 1,2,...,n이다.

 

$S_{k}$중 하나가 n의 배수라면 명제는 당연히 참이다.

 

$S_{k}$ 모두 n의 배수가 아니라면, $S_{k}$를 n으로 나눈 나머지는 1,2,...,n-1중 하나의 값을 가진다.

 

그런데 $S_{k}$로 가능한 값은 k = 1,2,...,n으로 총 n개이므로 비둘기집 원리에 의해 적어도 두개의 수는 n으로 나눈 나머지가 같다.

 

이러한 두 수를 $S_{i}, S_{j}$라고 하자. $S_{j} - S_{i} = a_{i+1} + ... + a_{j}$는 n으로 나누어 떨어진다.

 

https://pkjung.tistory.com/143

비둘기집 원리(Pigeonhole Principle)

 

 

 

3. 연습문제

 

24228번: 젓가락 (acmicpc.net)

24228번: 젓가락

 

4. 풀이

 

최악의 경우는 N개를 뽑을때, 모두 서로 다른 종류의 젓가락을 뽑아 0개의 짝이 만들어지는 것이다.

 

그리고 여기에 1개를 더 뽑아 N+1개를 뽑으면 비둘기집 원리에 의해 적어도 하나는 반드시 동일한 짝이 된다.

 

그렇게 만든 짝을 다른데로 치우면 N-1개가 남는데, 여기에 1개를 뽑았을때,

 

최악의 경우 나머지 N-1개와 다른 종류의 젓가락을 뽑으면 짝을 만들지 못한다.

 

거기에 1개를 더 뽑았을때, 비둘기집 원리에 의해 1개의 짝을 더 만들 수 있다.

 

즉, N-1개의 젓가락을 뽑고, 여기에 2개씩 뽑을때마다 1개의 짝을 얻을 수 있으므로... R개의 짝을 만들려면

 

최악의 경우 N-1 + 2R개를 뽑아야한다.

 

n,r = map(int,input().split())

print(n-1 + 2*r)