d라이브러리

세트 게임 카드에는 모양과 색깔, 개수, 내부, 이렇게 4가지 속성이 있습니다. 속성에는 다시 세 가지 종류가 있고요. 예를 들어 모양에는 다이아몬드, 타원, 눈썹 모양, 색깔에는 빨강, 초록, 보라가 있지요. 즉 세트는 4가지 속성이 각각 3종류 중 하나인 34=81장의 서로 다른 카드로 하는 게임입니다.



게임을 즐기기 위해선 우선 카드 12장을 무작위로 골라 펼쳐 놓습니다. 그리고 세트가 되는 카드 3장을 묶어 ‘세트!’라고 외치고 그 카드 3장을 가져갑니다. 나머지 카드에서 3장을 바닥에 펼치고 다시 세트를 찾습니다. 바닥에 남아 있는 카드가 없을 때까지 게임을 반복한 다음 서로 가진 카드의 수를 세서 카드를 가장 많이 가진 사람이 우승하게 됩니다.

그렇다면 조건에 맞는 카드 3장, 세트란 무엇일까요? 속성이 모두 같거나 모두 다른 카드 3장을 말합니다. 예를 들어 카드 3장이 모두 빨간색 다이아몬드이고, 개수가 각각 1개, 2개, 3개, 여기에 속이 채워진 것이 1장, 속이 빈 것이 1장, 줄무늬인 것이 1장이라면 이 3장의 카드가 세트입니다. 만일 속성 4개 중 2개는 같고 1개가 다르다면 그건 세트가 되지 않습니다.

그런데 세트 게임을 하다 보면 간혹 12장 중에 세트가 전혀 없는 경우가 있습니다. 이때는 3장을 더 펼치라는 규칙이 있습니다. 운이 나쁠 때는 그래도 세트가 없습니다.



보드게임과 이산수학의 절묘한 만남!

그럼 카드가 최소 몇 장 있어야 세트가 항상 있을까요? 1970년 이탈리아의 수학자 주세페 펠레그리노는 카드가 21장 있으면 세트가 항상 있다는 것을 증명했습니다.

사실 펠레그리노가 세트 게임에 매료돼 이 문제를 푼 것은 아닙니다. 세트는 1974년에 나온 보드
게임이기 때문에 그는 세트가 뭔지도 몰랐습니다. 펠레그리노가 푼 문제는 이산수학 문제였습니다. 원래 논문에서는 다른 표현으로 적혀 있었지만, 세트 게임과 정확히 같은 상황이기 때문에 여기서는 세트 게임으로 설명하겠습니다.

한편 수학자들은 펠레그리노가 푼 문제에서 멈추지 않고 이 문제를 일반화했습니다. D(4)를 ‘세트가 없을 수 있는 최대 카드 장수’라고 합시다. 따라서 D(4)=20입니다. 이제 속성 수를 n개까지 늘립시다. 당연히 속성마다 3가지 가능성이 있지요. 따라서 가능한 서로 다른 카드의 수는 3ⁿ장입니다. 이 중에 세트가 없는 최대 카드 수를 D(n)이라고 합시다. 그렇다면 이 D(n)이라는 값은 n이 커질 때 과연 얼마나 빨리 커질까요?



한편 1993년 노가 아론과 모세 디비네르는 D(n)＜2.999n이라고 추측했습니다. n이 커지면 이 값은 지금까지 밝혀진 그 어떤 결과보다도 훨씬 작은값이 되지요. 그런데 얼마 전까지만 해도 미해결로 남아있던 이 문제를 놀랍게도 2016년 5월 미국과 네덜란드의 두 수학자가 거의 같은 시기에 해결했습니다. 대체 무슨 일이 있었던 것일까요?

새로운 신형 무기로 단 번에 문제 해결!

지난 5월 5일 수학, 과학 분야의 새로운 논문을 공유하는 웹 사이트인 ‘아카이브(arXiv)’에 세 명의 수학자 어니 크루트, 프세볼로드 레브, 피터 파흐가 D(n)과 관련된 논문을 올립니다. 이 문제는 D(n)과 관련이 있기는 하지만 조금 다른 문제였습니다. 이들은 지금까지 누구도 생각지 못한 방법을 써서 매우 짧고 간결하게 문제를 풀었습니다.

우연히 이 논문을 읽고 새로운 아이디어에 감탄한 조던 엘렌버그는 5월 12일 자기 블로그에서 이 논문의 증명 방법을 칭찬했습니다.

엘렌버그는 곧이어 이 논문의 증명 방법을 이용하면 세트에 관한 문제인 D(n)＜2.999n도 해결할 수 있다는 것을 알아챕니다. 급한 마음에 그 증명을 간략하게 써서 바로 다음날 블로그에 D(n)≤2.756n이라는 것을 올리지요. 이 글이 올라오자마자 필즈메달 수상자인 테렌스 타오와 티머시 가워스 등이 댓글로 축하 메시지를 보냈습니다.

그런데 이틀 뒤 네덜란드 수학자 디온 헤이스베이트가 사실 지난주에 자기도 비슷한 증명을 하고 있었다고 댓글을 답니다. 두 사람이 서로의 증명을 비교해 보니 너무 비슷해서 두 사람은 공동 논문을 쓰기로 결정하고 결과를 정리해서 5월 30일 아카이브에 올립니다. 이 모든 것이 2016년 5월 한 달 동안 있었던 일이지요.
 

신형 무기의 정체는 대학생도 아는 수학

대체 5월 5일 올라온 논문에는 어떤 방법이 담겨 있었기에 세트 문제가 단번에 풀린 걸까요? 크루트와 레브, 파흐는 이런 문제에 처음으로 다항식과 선형대수학★만 써서 문제를 풀었습니다. 다항식과 선형대수학을 이산수학 문제에 사용한 지는 오래됐지만, 세트 문제에는 사용한 적이 없었습니다. 이 분야 학자들은 D(n)에 관한 문제를 풀려면 반드시 푸리에 변환을 사용해야 한다고 생각했습니다. 푸리에 변환은 시간에 대한 함수를 그 진동수로 분해하는 작업으로 다항식이나 선형대수학보다 훨씬 더 복잡합니다.

이전까지 가장 좋은 증명을 내놓았던 베이트먼과 카츠는 푸리에 변환을 이용해서 복잡하게 증명했습니다. 그런데 크루트와 레브, 파흐는 푸리에 변환을 전혀 사용하지 않습니다. 대학생 정도면 이해할 수 있는 수학만 이용해 증명했지요. 논문에서 증명은 2쪽도 안 될 정도로 매우 짧았습니다.

이처럼 새로운 아이디어가 나오면 많은 수학자들이 관심을 갖습니다. 이번에도 많은 수학자들이 이 방법을 이용해 또 어떤 문제를 해결할 수 있는지 관심을 가지고 연구하고 있습니다. 게다가 이번에 나온 새로운 아이디어는 무척 간단해서 이 분야의 미해결 난제를 쉽게 해결할 수 있으리라고 많이 기대하고 있습니다. 필즈메달 수상자인 티머시 가워스는 블로그에 다음과 같이 썼습니다.