(이상구교수의 조합론 성균관대 강의록)


2장 The pigeonhole Principle

1. The pigeonhole principle

2. Dirichlet drawer principle

3. Shoebox principle


2.1 Pigeonhole principle의 simple form

   

    

If object(비둘기)를 개의 box(비둘기집)에 넣으면,

적어도 한 box(비둘기집)에는 둘 이상의 object(비둘기)가 있게 된다

 

BWOC

[증명] 만일 box가 모두 기껏해야 1마리만의 비둘기를 가진다면 담을 수 있는 전체 비둘기의 수는 기껏해야 마리이다. 이는 비둘기가 마리라는 가정에 모순이다


[예제2] 쌍의 부부가 있다. 명의 사람 중 몇 명을 뽑아야 그 중에 적어도 한 쌍의 부부가 포함되어 있음을 보장할 수 있다.

♣ Recall : ,

         


[예제3] 개의 integers 에 대하여 ,

  with such that


[풀이] 수열 에는 그의 합이 에 의하여 나누어지는 consecutive 's가 존재한다.  ( 예     )

Consider    

이것 중 하나가 에 의하여 나누어 떨어지면 O.K


[증명] 위의 개를 각각 으로 나누면 (P.29)

개의 서로 다른 나머지 밖에 없으므로 적어도 둘은 같은 remainder를 갖는다. (Pigeonhole principle) 그것을 이라 하자.  그러면 그 둘의 차이는 바로 위의 이 된다. 그리고 이 값은 에 의하여 나누어진다.


[예제6] (Chinese remainder thm)

Let

Then for some integers and

이것을 증명하는 것도 Pigeonhole principle이다.


2.2 general (strong) 비둘기집 문제


(ⅰ) 만일   개의 물체를 개의 box에 넣으려면

either  첫 번째 박스가 적어도 개  or

        두 번째 박스가 적어도 개 or

                 

       번째 박스가 적어도 개를 포함해야만 한다

[증명] 왜냐하면 Suppose not. only

개만의 물체만이 box 들에 들어  간다. (모순) 

이의 Special case 인 인 경우가

인 경우 ⇒ simple (비둘기집) case 이다.


(ⅱ) 만일 물체가 개의 box에 들어간다면,

적어도 하나의 상자는 개 또는 그 이상의 개수의 물체를 포함해야 한다.

.

[증명] BWOC

Suppose not 즉, 모든 상자가  개미만의 물체를 담고 있다면

  역시 적어도 나머지 하나가 있을 곳이 없다, 모순.


(ⅲ) 만일 정수들 보다 큰 평균 을 갖는다면, 정수들 의 적어도 하나는 과 같거나 커야한다.

[증명] BWOC

Suppose not

      

      

       이는 라는 가정에 모순.

      

2.3 Ramsey(1903년에 태어나 1930년에 사망) 의 정리


[예] 한 반에서 6명을 (또는 그이상의) 모아 놓으면 그 안에는 서로 친한 3명이 있거나 또는 서로 친하지 않은 3명이 있다.


(참고)          

                    

              

              

위의 증명은

를 그리고 각 edge를 red or blue로 마음대로 칠해도

안에서 either red or blue 라는 sub graph를 찾을 수 있다.

을 이용하여 설명되어 질 수 있다.


의 의미는 의 모든 edge 들에 red or blue 로 그리면 그 안에서  red    or blue 라는  sub graph를 찾을 수 있다는 의미이다.


If 이 되고

If .


Definition)

The Ramsey number 되는 가장 적은 정수 이다.


위에서 임을 보이는 것은 직접 해 본 셈이다.

이제 가 false 임을 보이면 을 보인 셈이 된다.

일반적으로 이고

       

        

        

          

        

        


위의 개념을 일반화하여 이면,

되는 최소의 정수 는 존재

  



이런 최소정수 를 Ramsey number 로 정의한다.


♣ Note :  로 이것이 pigeonhole principle 이다.


일반적인 Ramsey number 로 결정하는 것은 어려운 문제이다.

그러나 임을 보이는 것은 별로 어렵지 않다.

여기서 를 배열하는 순서는 Ramsey number에 영향이 없다.


Definition)

-element subset of a set 는 정확히 개의 元을 갖는 의 subset이다.


인 양의 정수들이라면

아래 성질을 만족하는 에만 depend되는 양의 정수가 존재한다.

그러니까 그런 가장 작은 양의정수, Ramsey number, 가 존재한다.

with the following 성질.


If 이고,-원소의 부분집합이 개의 box로 분배될 때

then either

objects  such that 이러한 objects의 모든 -elements의 부분집합이

첫 번째 box에 포함되는

or ∃ objects  such that 이러한 objects의 모든 -elements의 부분집합이

두 번째 box에 포함되는

    

or ∃ objects such that 이러한 objects의 모든 -elements의 부분집합이

번째 box에 포함되는.

그러니까 이것은 비둘기집 문제의 직접적인 ꡒ일반화ꡓ일 뿐이다.

이 증명은 Ryser의 ꡒCombinatorial Math, MAA, 1963년책ꡓ에 있다.

일 경우가 이다.

♣ Note: Ramsey's 정리의 이용은 아직 많이 안 알려져 있다.

인 경우조차도 upper bound 외에는 거의 알려진 것이 없다, {see P41.}


2.4 Exercise

➜ #4. 집합 에서 개의 元을 고르면 언제나 두수의 차가 1인 두수가 존재한다.


[증명] 개의 元을 고르면 그 중에 적어도 2개는 연이어져 있다.

모든 consequitive 수는 차가 1이고 서로소이다.


◎ Partition the integers into the pair.


➜ #9. 한 살은 넘고 60살은 안 되는 10명이 한방에 있다. Prove 언제나 나이의 합이 같게 하는 두 group을 찾을 수 있다. 10대신 더 적은 수에서는 어떨까?


☞ The number of sums that can be formed with 10 numbers is . 어떤 합도   600을 넘지 않는다.


➜ #14. 100개의 사과, 100개의 바나나, 100개의 오렌지, 100개의 배를 담은 가방이 있다. 만일 1분마다 가방에서 하나씩의 과일을 꺼낸다면, (어떤 한 가지) 같은 종류의 과일을 적어도 12개 골랐다고 확신할 때까지는 몇 분이나 걸릴까?

☞ 45분


➜ #24. Let and be positive integers with .

Ramsey number 는 무엇인가?


《 2장 연습문제 과제 》

  (아래를 포함하여 각 6문제를 풀어 다음 시간 전에 제출)


4. the set 에서 개의 정수를 뽑으면 반드시 이웃하는 숫자가 생기는 것을 증명하라. 


[증명]




9. 한 방에, 1살 이상 60살 이하의 자연수의 나이를 갖는 10명의 사람들이 있다. 나이의 합이 같은 두 그룹을 항상 발견할 수 있음을 증명하여라. 그리고, 10명의 사람보다 더 적은 사람들이 있을 경우에도 가능한가?


[풀이]









14. A bag contains apples, bananas, oranges, and pears. If I pack piece of fruit out of the bag every minute, how long will it be before I am assured of having picked at least a dozen pieces of fruit of the same kind?