세 명의 젊은 수학자는 3,4,5각형일 때의 경우를 풀었다. 5개의 점이 4각형을 만들고, 9개의 점이 5각형을 만들 수 있다. 그들은 2^(n–2) + 1개의 점이 볼록 다각형 n각형을 만들 수 있다고 생각했다. 그리고 이것을 증명하는데에 $500를 걸었다.
몇십년이 흐르는 동안, 17개의 점이 볼록다각형 6각형을 보장한다는 것 외에 진전이 없었다. 그리고 이 문제가 나타난지 80여년이 지나서야 드디어 2^(n–2) + 1개의 점이 볼록 다각형 n각형을 만들 수 있다는 것이 증명되었다.
Split Shapes
이 문제는 볼록다각형을 만드는 변들을 찾는 것으로 볼 수 있다. 1935년의 논문에서 그들은 u shape모양을 Cup라고 하였고, n shape 모양을 Cap이라고 하였다. 그래서 볼록다각형을 만들 때는 cup 위에 cap을 붙이면 된다. 이를 이용하면, 볼록다각형을 확장할 때 어떤 것을 붙일지를 통해 쉽게 생각할 수 있다.그들은 이 논문에서 컵-캡 정리를 증명했다. 컵-캡 정리는 점이 적어도 몇 개 필요한지 컵 또는 캡의 사이즈를 정하기 전에 알려준다. 게다가 Happy Ending Problem의 상한을 정할 수 있다. 그들은 이 정리를 통해 4^n개의 점이 n sided convex polygon을 만든다는 것을 알았다. 하지만 이 상한은 여전히 크다.
Sorting Spikes
Andrew Suk은 Ramsey Theory에 집중했다. 문제에 Ramsey Theory를 적용하면, 잘 정리된 볼록다각형의 point set을 얻을 수 있다.
Suk의 작업은 Erdős and Szekeres’ conjecture 가 거의 맞다는 것을 보여줬다. 기존의 상한은 4^n이었던데 반해, Suk은 상한을 2^(n+6n^(⅔)log n) 까지 제한하는데 성공했다.
To Divide the Rent, Start With a Triangle
작년에 나는 두명의 친구와 함께 맨해튼에 있는 방 3개 짜리 아파트로 이사했다. 월세도 합리적이었고, 위치가 특히 편했다. 집을 구하는 것도 힘들었지만 우리는 또 다른 문제에 직면했다. 바로 누가 어떤 방을 쓸 것인가에 관한 것이었다.
각 방은 각각 다른 크기를 가지고 있었다. 두 방은 거리를 향한 북향이고 가장 작은 방은 뒷골목을 향했다. 가장 큰 방은 두 개의 창문이 있고, 두번째로 큰 방은 화재대피로와 연결된다.
사람들은 주거비를 아끼기 위해 전혀 알지도 못하는 사람들과 살기도 한다. 월세를 똑같이 나눌지, 방 크기에 따라 나눌지 아니면 수입에 따라 나눌지도 정해야 한다.
그래서 학계에서는 공평하게 나누는 법을 연구했다. 연구자들은 어떤 방법에도 만족하지 못했다.
문제는 개개인이 각 방을 다르게 평가한다는 것이다. 나는 자연광을 굉장히 고려하지만 다른 사람들은 그렇지 않았다. 옷장을 갖는 것보다 가치가 있는 일인지? 어떤 이는 방 모양을, 다른 이는 화장실 유무를 더 크게 고려했다.
방의 크기나 각 개인의 선호도를 전부 고려하지 못하다 보니 뾰족한 수가 없는 협상은 갈등과 서운함만을 불러올 뿐이었다.
나는 우리의 월세를 나누는 더 좋은 방법을 찾기 위해 고민했다. 그렇게 Harvey Mudd 대학의 수학 교수인 Francis Su의 논문까지 보게 되었다. 수학적으로 어떻게 분할할 것인가를 고민한 Sperner’s lemma에 관한 논문이었다.
Su 박사는 1999년 논문 "Rental Harmony : Sperner’s Lemma in Fair Division."(조화로운 월세 내기 : Sperner’s lemma를 적용한 공평한 나누기)에서 Sperner’s lemma와 월세 나누기의 연관성을 처음으로 제시했다. 그는 하버드에서 박사학위를 마칠 때 쯤 이 문제를 연구하기 시작했다. 그의 친구가 나와 똑같은 곤경에 처해 있었고, 그에게 조언을 구했기 때문이다.
Su 박사는 어쩌면 이 문제가 자신이 들어본 다른 문제와 연관이 있을 수도 있을 것이라는 생각을 하게 된다.
No comments:
Post a Comment