폴리매스

정의 (그래프) 그래프 G = (V,E)는 점 집합 V와 어떤 두 점을 잇는 선분들의 집합 E로 이루어진 조합적인 대상입니다.

정의 (완전그래프) 완전그래프 G = (V,E)는 임의의 두 점 사이를 잇는 선분이 하나씩 존재하는 그래프입니다. 점의 개수가 n일 때 이 그래프를 이라고 부릅니다.

정리 (램지 정리) 6개의 점으로 이루어진 완전그래프 (즉, )의 각 선분이 빨간색 또는 파란색으로 칠해져 있습니다. 이때 이 그래프에는 단색 삼각형이 존재합니다. 즉, 어떤 세 점을 골라서 이 세 점을 잇는 3개의 선분이 모두 빨간색이거나 또는 모두 파란색이도록 할 수 있습니다.

문제

평면 위에 6개의 점이 어떤 세 점도 한 직선 위에 있지 않도록 주어져 있습니다. 이때 이 점들을 꼭짓점으로 하는 삼각형들 중에서 한 변을 공유하는 두 삼각형이 존재하여 이 공유하는 변이 한 삼각형의 가장 긴 변인 동시에 다른 삼각형의 가장 짧은 변이 됨을 보이세요.

여담1

점 집합 V와 선분 집합 E는 각각 Vertex와 Edge의 첫 알파벳입니다.

여담2

R(3,3) = 6은 램지 정리와 관련된 숫자입니다. 일반적으로 R(a,b)는 다음을 만족하는 가장 작은 n을 일컫습니다: 완전그래프 의 각 선분을 빨간색 혹은 파란색으로 칠했을 때 빨간색의 가 존재하거나 파란색의 가 존재한다.

이 맥락에서 비추어볼 때, 램지 정리에서 "6"은 램지 정리의 조건을 만족하는 가장 작은 숫자임을 알 수 있습니다.

추가문제

의 각 선분을 빨간색 또는 파란색으로 잘 칠하여 단색 삼각형이 존재하지 않도록 해보세요.