본문바로가기
함께 풀고 싶은 문제
나도 수학쌤 문장제 문제를 변형해 문제를 내는 곳입니다.
[문장제 문제&개념응용] 램지 정리
김다인(멘토) 2021.05.04 20:52 조회 1082

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

 

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

 

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

 

문제

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

 

여담1

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

 

여담2

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

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

 

추가문제

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

 

이 문제 어떠셨나요?

글쎄요

0

어려워요

1

  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911