[해피엔딩문제] 다각형을 품고 있는 점의 개수 구하기

(이 글은 "이토록 재미있는 수학이라니" 책의

 "다각형을 품고 있는 점의 개수 구하기" (해피엔딩문제) 편에 대한 것입니다.)

 

종이 한 장을 펴고 그 위에 5개의 점을 찍어봅시다.

이 중 어느 세 점도 한 직선 위에 있지 않습니다.

그리고 5개의 점이 어떻게 놓여 있는지 이 중에서 4개의 점을 잇습니다.

목표는 볼록 사각형 하나를 만드는 것입니다.

 

여러 조합으로 많은 사각형을 그릴 수 있습니다.

5개의 점 위치와 상관없이 언제든지 4개의 점으로 볼록 사각형을 만들 수 있다고 생각할 수 있습니다.

그러나 분명한 것은 4개의 점이 항상 볼록 사각형이 되는 것은 아닙니다.

5개의 점에서 4개를 이을 때 볼록 사각형이 만들어지지 않는 경우도 있다는 것을 알게 될 것입니다.

 

이 문제는 주어진 조건에서 볼록 다각형을 만들 수 있는지, 볼록 사각형을 만들려면 최소 5개의 점이 필요한지, 

볼록 사각형을 만들 수 없도록 5개의 점을 그릴 수 있는지에 대한 것입니다.

볼록 오각형을 만들려면 최소 점 몇개가 필요할까요?

볼록 육각형은 최소 몇 개의 점이 필요할까요?

일반적으로 평면 상 볼록 N각형을 만들수 있는 최소한의 점 개수를 묻는 문제를

해피엔딩문제라고 합니다.

 

위의 문제와 해피엔딩이 무슨 상관이 있을까요?

헝가리에 있었던 아름다운 이이기와 관련이 있습니다.

1933년 헝가리에서 수학을 사랑하는 젊은이들이 있었습니다.

이들은 자주 모여 수학문제를 논의했습니다.

그중에서도 활발한 활동을 했던 세 사람이 있었는데

23세 여성 클라인, 그녀보다 한 살 적은 남성 세케레시, 20세 에어디쉬였습니다.

 

어느 날 클라인은 두 친구에게 이 문제를 선보였습니다.

그들이 이 문제를 증명하기 원했었고, 몇 개의 예를 제시했습니다.

오래 지나지 않아 세케레시와 에어디쉬는 이 문제를 증명했습니다. 

뿐만 아니라 이들은 임의의 블록 다각형을 만들려면 필요한 점의 개수까지도 증명했습니다.

그중 볼록 N각형이 되도록 N개의 점을 찾기만 하면 된다는 것을 '에어디쉬-세케레시'정리라고 합니다.

세레케시와 클라인은 함께 이 문제를 연구하면서 서로 사랑에 빠졌습니다.

결국에 둘은 결혼하게 되었습니다.

이후 짓궂은 에어디쉬는 이 문제를 차라리 '해피엔딩문제'라고 부르자고 제안했습니다.

 

1937년 그 둘은 헝가리에서 결혼했고 2년 후에 2차 세계대전이 발발했습니다.

두 사람은 유대인이었기 때문에 도망갈 수밖에 없었고 그 둘은 상해에서 살기로 했습니다.

상해에서 사는 동안 첫째 다을이 태어났습니다.

이후 1948년에 그들은 오스트레일리아로 이주했고 거기서 남은 여생을 보냈습니다.

두 수학자 모두 장수했는데 90년 이상을 살았다고 합니다.

2005년 두 사람은 한 시간 차이로 잇달아 생을 마감했습니다.

그래서 그들의 인생은 절대적으로 해피엔딩이라고 불릴만합니다.

 

해피엔딩 정리는 간단한 사례 분석으로 증명할 수 있습니다.

4개 이상의 점이 볼록 꼽질의 꼭지점인 경우 이러한 점 4개를 선택합니다.

반면 볼록 껍질이 내부에 두 개의 점이 있는 삼각형 형태인 경우

두 개의 내부 점과 삼각형의 모서리 중 하나를 선택할 수 있습니다.

이 증명에 대한 설명은 Peterson(2000)의 증명을 보면 알 수 있습니다.

문제에 대한 보다 자세한 조사는 Morris & Soltan(2000)을 참조할 수 있습니다.

 

해피엔딩 문제는 '공심 해피엔딩문제'로 확장될 수 있습니다.

이것은 해피엔딩문제보다 더 많은 조건이 필요합니다.

볼록다각형을 만들 때 다른 점을 내부에 포함하지 않는 것입니다.

공심해피엔딩문제는 볼록 사각형인 경우, 여전히 5개의 점이 필요하고

오각형은 10개의 점이 필요하다고 알려져 있습니다.

우리는 공심해피엔딩문제에서 많은 점은 찍기만 하면 된다고 생각할 수 있습니다.

그러나 1983년 조제프 호턴은 점의 수가 충분히 많을 때 공심볼록칠각형을 찾을 수 없음을 증명했습니다.

 

하나의 추론에서 시작해서 꼬리에 꼬리를 무는 증명의 과정들을 통해 수학자의 위대함을 느낄 수 있습니다.

 

그림 출처 : wikipedia

해피엔딩 문제 :

일반적인 위치에 있는 다섯 개의 점의 모든 집합은 볼록 사변형의 꼭지점을 포함한다는 것입니다.