비둘기집의 원리 램지의 정리 (Ramsey's theorem) 서로 아는 사람 모르는 사람

6명 중에는 서로 아는 사람이 3명 있거나 서로 모르는 사람이 3명 있음을 증명하라?
(KMO BIBLE 한국수학올림피아드 바이블 조합 p 127예제 3.6)

풀이: 6명의 사람을 6개의 점으로 나타내고, 각 쌍의 점을 그점에 해당하는 2명이 서로 알때는 파란색 선으로 서로 모를때는 빨간색 선으로 연결하자.
그러면 문제는 변의 색이 같은 삼각형이 존재함을 보이면 된다.

6개의 점중 임의의 한점을 택하여 P라 하면 , 비둘기집의 원리에 의하여 나머지 5개의 점중 3개는 P와 이어진 선의 색깔이 같다.
그  점을 X, Y, Z 라 하자. 일반성을 잃지않고, 이들선의 색깔이 모두 파란색이라고 하자.
 X, Y, Z 중 어느 두점이 파란색 선으로 이어져 있다면 , P와 그 두점은 변이 모두 파란색인 파란색삼각형이다.
X, Y, Z 중 어느 두점도 파란색 선으로 연결되어 있지 않다면 삼각형 XYZ 는 빨간색 삼각형이다.
QED


그래프 이론에서 완전 그래프(完全graph,  complete graph)는 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프이다.


K6 (6꼭짓점 15변)
 The complete graph with  graph vertices is denoted  and has 
6(6-1)/2=15변
6명을 서로 연결하면 15개의 선으로 연결 된다.

램지 이론에서, 램지의 정리( Ramsey’s theorem)는 충분히 큰 완전 그래프의 변을 색칠할 경우, 동색의 클릭을 찾을 수 있다는 정리이다.

R(3,3)=6의 증명

크기가 5인 완전 그래프의 경우, 크기 3의 클릭이 존재하지 않도록 2개 색으로 색칠할 수 있다. 즉, ${\displaystyle R(3,3)>5}$이다.

6개의 꼭짓점을 가지는 완전 그래프의 각 변을 빨강과 파랑으로 칠한다. 한 꼭짓점 v를 보면, 그 꼭짓점에는 5개의 변이 연결되어 있다. 비둘기집 원리에 의해, 적어도 그 중 3개는 같은 색이다. 그 색을 파랑이라고 가정 하고, 그 3개의 변에 연결된 꼭짓점을 각각 r, s, t라고 하자.

만약 변 (r, s), 변 (t, r), 변 (s, t) 중 어느 하나라도 파랑이면, v와 함께 파란색 삼각형(3개의 꼭짓점을 가지는 완전 그래프)이 생긴다. 만약 어느 하나도 파랑색이 아니면, (r, s), (t ,r), (s, t)는 모두 빨강색이므로 빨강색의 삼각형이 생긴다. 그러므로, 6개의 꼭짓점을 가지는 완전그래프 K₆의 변을 두 가지 색으로 칠하는 경우, 동일한 색의 K₃를 포함하게 된다. 즉, R(3,3) ≤ 6이다.

한편, K₅를 두가지 색으로 칠하는 방법 중에는 동일한 색의 삼각형을 만들지 않는 경우가 존재한다(오른쪽 그림). 그러므로, R(3,3) > 5 이다. 결론적으로 R(3,3)=6

방에 6명이 있다.두명이 서로알면 친구라하고 모르면 적이라하자.

 두명이 친구사이 라면 파란선으로 연결하자. 서로 모르는 사이라면 빨간색으로 연결하자.

세명을 연결하여 같은색으로 연결된 삼각형을 만들수 있나?

 can we find a blue triangle (three friends), or a red triangle (three strangers)?

In this case the answer is "yes".

 Charlie, Evelyn and Fred are all strangers to each other.  does a monochromatic triangle always appear?

위의 그림에서 Charlie, Evelyn,  Fred는 빨간색으로 연결된 삼각형으로 3명이 서로 모르는 사이다.
여러 그래프가 가능하다.

6점중의 한점을 A라하고 B,C,D,E,F 를 연결하자.
비둘기집 원리에 의해서 5점중 3점은 같은색으로 연결된다. 빨간색이든 파란색이든.

 First we choose any point, and note that five lines come out of it - one to each of the other five points:

With five lines, there must be at least three of one colour - at least three red lines or at least three blue lines. Let's suppose there are three red lines (if there were three blue lines instead, the argument would be exactly the same but with "red" and "blue" swapped). So we have four points like this:

A에서 B,C,D로 모두 빨간색으로 연결 되었다고 하고 B,C,D 사이에 즉 BC, BD, CD중 하나가 빨간색으로 연결 되었다면 빨간색 삼각형이 만들어 지고, 빨간색으로 연결된게 없다면 B,C,D 사이에 파란색으로 연결된 삼각형이 생긴다.

What colours are the three remaining lines? Well, if even one of them is red, then it makes a red triangle together with point A (left). And if not, the three together make a blue triangle (right):

Either way, we have our monochromatic triangle.

어떤경우든 단색삼각형 즉 빨간삼각형이나 파란삼각형이 만들어져, 서로 아는친구 3명이나 서로 모르는 3명이, 6명이 모인 자리에는 항상 존재하게된다.
R(3,3)=6

mutual friends/strangers

참고로 R(4,4)=18
          R(5.5)=43~49 이다.
6명이 모이면 어떤경우든 서로 아는사이 가 3명 ,아니면 모르는 사이가 서로 3명이 반드시 있다는 것으로, 램지의 정리 (Ramsey's theorem) 와 비둘기집의 원리로 설명이 되고 ,아는사이 가 3명이거나 ,모르는 사이가 서로 3명이 존재하려면 최소한 6명이 있어야 한다는 결론 R (3,3)=6 과 증명이 된다.

궁금한게 있으면 연락 주세요
010-3549-5206으로