AI가 풀지 못한 마지막 IMO 문제

[Submit subtitle corrections at criblate.com] 2025년, 전 세계 각지에서 온 600명이 넘는 청소년들이 호주 선샤인 코스트에 모여 국제수학올림피아드(International Math Olympiad)에 참가했습니다. 이 대회는 매우 어려운 6개의 문제로 구성되어 있으며, 그중 6번 문제가 단연코 가장 어려웠습니다. 각 참가자들 중 자신의 국가에서 최고의 문제 해결사들이 분명히 있었음에도 불구하고, 학생들의 1% 미만이 만점을 받았습니다. 또한 이것이 풀릴 마지막 IMO 문제일 가능성이 높아 보입니다.

AI가 풀 수 없는 문제는 없습니다. 그리고 이 문장은 겨우 5년 전만 해도 대회 수학에 익숙한 대부분의 사람들에게는 터무니없게 들렸을 것입니다. 그렇게 말하는 것이 공정하다고 생각합니다. 만약 당신이 이 분야 밖에 있다면, 이해해야 할 것은 이러한 문제들이 상상력과 창의성의 요소를 요구하도록 설계되었다는 것입니다. 단순히 암기나 계산만 하는 것이 아닙니다. 이 문제들 중 하나를 풀었다는 것은 단순히 올바른 수치적 답을 내놓거나 그런 것을 의미하지 않습니다.

그것은 완전하고 엄밀한 증명(rigorous proof)을 작성하는 것을 의미하며, 대회의 정신은 증명을 찾는 행위 자체가 특정 설정에 대한 미묘하고 깊은 이해를 요구해야 한다는 것입니다. 그래서 시간을 되돌려 2021년이라고 가정해 봅시다. 그때쯤에는 게임에서의 AI가 인상적인 결과를 많이 보여주었고, 자연어에 대한 스케일링 법칙(scaling laws)도 명확해졌음에도 불구하고, 많은 사람들은 IMO를 완전히 다른 차원의 문제로 여겼을 것입니다. 그것은 엄밀함과 창의성의 혼합을 요구하며, 증명을 작성할 때 할 수 있는 논리적 움직임들의 탐색 공간(search space)은 사실상 무한합니다.

사실 2023년 Dwarkesh Patel의 팟캐스트에 출연했을 때, 이것이 그가 던진 질문 중 하나였습니다. 만약 어떤 AI 모델이 국제수학올림피아드(IMO)에서 금메달을 딸 수 있게 된다면, 그것은 단순히 범용 인공지능(AGI)일까요? 하지만 바로 다음 해인 2024년, Google DeepMind의 AlphaProof 팀은 그해 시험 문제 6개 중 4개에 답한 모델을 선보였습니다. 여기에는 약간의 주석이 붙습니다. 왜냐하면 해당 시스템은 인간이 문제를 영어에서 Lean으로 수동 번역해야 했기 때문인데, Lean은 수학적 증명이 프로그램인 일종의 프로그래밍 언어입니다.

하지만 AlphaProof 시스템은 비록 다른 언어로 되어 있더라도 증명을 찾는 실질적인 부분까지 처리하고 있었고, 이것만으로도 많은 사람들에게 놀라움을 주었습니다. 그리고 2025년에는 여러 조직들이 자신들의 모델로 이 테스트에 도전했고, 이번에는 Lean 접근 방식을 취하는 팀들과 순수하게 자연어(natural language)만으로 엔드투엔드(end to end) 처리하는 팀들이 혼합되어 있었습니다. 그리고 이제 모델들은 이 문제 번호 6을 제외하고는 모든 문제에 답했습니다. 그러다가 2026년에는... 공개적으로 사용 가능한 추론 모델(reasoning models)에 단순히 프롬프트를 제공하는 것만으로도 6개 문제 모두에 정답을 얻을 수 있게 될 것입니다.

이것은 지난 몇 년 동안 이 모델들이 수학 분야에서 얼마나 발전했는지를 정말로 과소평가한 것입니다. IMO는 마치 고대 역사처럼 느껴지는데, 모든 것이 지난 한 해 동안 연구 수학(research math)의 영역으로 속속 진입해 왔기 때문입니다. 이에 대해서는 나중에 더 이야기할 것이며, 시간이 되면 저를 믿으세요. AI와 수학에 대해 할 말이 정말 많습니다. 수학은 중요합니다. 하지만 지금 당장은 이 영상이 주로 AI에 관한 것은 아닙니다. 무엇보다도, 아주 아름다운 문제에 대한 깊은 탐구일 뿐입니다.

하지만 우리가 이 문제를 해결해 나가는 과정과 그에 필요한 통찰력을 살펴보면서, 아무런 기계도 풀지 못했을 때 몇몇 뛰어난 학생들이 어떻게 답을 찾아낼 수 있었는지에 대해 생각해 보는 것이 흥미롭다고 생각합니다. 그래서 저는 올해 시험에서 추론 모델(reasoning model) 공격을 감행했던 Google DeepMind 팀의 연구 책임자 중 한 명인 Thang Luong에게 이 질문을 실제로 했고, 그는 정말 흥미로운 답변을 해주었습니다. 그는 우리가 모델에게 '인내심'을 가르칠 방법이 없었다고 말했습니다.

모델은 문제를 이해하는 데 시간을 들이거나, 문제를 파악하거나, 심지어는 문제를 풀려고 시도하지 않는 것에도 시간이 걸립니다. 오늘 함께 살펴보면서 여러분도 인내심이 확실히 필요한 요소라는 것에 동의하실 것이며, 해결하려고 하기 전에 이해해야 한다는 그의 의미도 알게 되실 겁니다. 하지만 저는 최소한 한 가지 추가적인 재료를 제시하고 싶습니다. 모델들은 적어도 제가 상호작용한 바로는, 어떤 문제나 전략이 아름다운지 감각을 가지고 있지 않은 것 같습니다. 그리고 여기서 해답을 찾는 것은 '아름다움'에 대한 이해로부터 절대적으로 이점을 얻습니다.

자, 그럼 본론으로 들어가겠습니다. 이 문제는 무엇이며, 학생의 입장에서 이것을 어떻게 해결할지 알아가는 기분은 어떨까요? 문제를 꺼내보겠습니다. 2025x2025 크기의 단위 정사각형 격자를 고려해 봅시다. 좋습니다. 화면에 애니메이션으로 보여주기에는 명백히 다루기 어렵습니다. 그래서 처음에는 10x10과 같이 더 작은 것부터 시작합시다. Matilda는 이 격자에 다양한 크기의 직사각형 타일을 배치하고 싶어 하는데, 모든 타일의 변은 격자 선 위에 놓여야 하며, 모든 단위 정사각형은 최대 하나의 타일에 의해 덮여야 합니다.

합리적으로 생각하면, 타일들은 서로 겹치지 않습니다. 이제 문제 설명은 특정 핵심 규칙을 따르는 최소한의 타일 개수를 찾도록 요구합니다. 그 규칙이란 각 행이 어떤 타일로도 덮이지 않은 단위 정사각형을 정확히 하나 가져야 한다는 것입니다. 저는 이러한 간격 각각에 X 표시를 하고, 마찬가지로 각 열 역시 어떤 타일로도 덮이지 않은 단위 정사각형을 정확히 하나 갖도록 합니다. 따라서 열마다 하나의 X가 있습니다. 이는 우리의 작은 10x10 경우에서 타일링에 10개의 다른 간격이 있다는 것을 의미합니다. 하지만 실제 문제 설명의 전체 격자에서는 타일링에 총 2025개의 간격이 있을 것입니다.

어떤 종류의 타일링인지 직관적으로 이해하는 것부터 시작하는 것이 좋겠습니다. 예를 들어, 우리의 10x10 경우로 돌아가서, 총 21개의 타일을 사용하는 예시를 보여드리는데, 이 예시가 핵심 규칙을 따르는 것을 알 수 있습니다. 즉, 두 개의 X가 같은 행이나 열에 놓이지 않습니다. 하지만 만약 우리가 가장 적은 수의 타일을 원한다면, 이것은 확실히 최선이 아닙니다. 다른 세트를 선택하여 간격을 다른 곳에 남김으로써, 이 예시는 우리에게 17개의 타일을 제공합니다. 심지어 이것도 개선할 여지가 있습니다. 여기는 단지 16개의 타일만으로 해내는 또 다른 시도입니다.

이것이 국제 수학 올림피아드(International Math Olympiad)인 만큼, 여러분의 과제는 단순히 이 최소한의 타일 개수에 대한 수치적 답을 내놓는 것뿐만 아니라, 그 최소 타일링을 달성하는 구성(construction)을 보여주는 것을 넘어섭니다. 그 구성은 일부가 될 것이지만, 여기서 진정한 도전은 여러분이 찾은 어떤 최소값이 정말로 최선인지 엄격하게 증명하는 것입니다. 이것에 대해 머릿속으로 가지고 놀면서 생각하면 왜 이 문제가 어려운지 감을 잡을 수 있습니다. 타일들이 어디에 놓여야 하는지에 대한 일반화 가능한 설명(generalizable descriptions)을 생각하기가 어렵기 때문입니다.

가장 쉬운 경우는 X들을 이렇게 대각선으로 모두 놓은 다음, 나머지 영역을 가로 타일로 덮는 것입니다. 만약 한 변의 길이가 n인 격자를 추가하면, 오른쪽 측면의 타일 개수가 n-1개이고 마찬가지로 왼쪽 측면도 n-1개이므로 총 2(n-1)개의 타일을 얻게 됩니다. 하지만 이 구성은 너무나 당연해서 IMO가 요구하는 바는 아닐 가능성이 높습니다. 따라서 여러분이 원하는 것은 X를 배치할 수 있는 다른 일반적인 방법과, 그 주변에 타일을 놓을 수 있는 일반적인 방법으로, n의 함수로서 현재보다 더 작은 개수를 주는 것입니다.

그렇다면 이런 문제에 어떻게 접근해야 할까요? 어디서부터 시작해야 할까요? 이제 한 발 물러나서 생각해보면, 문제 해결에 대한 매우 중요한 일반적인 교훈은 천재적으로 보이는 것도 보통 경험의 잔여물이라는 것입니다. 통찰력은 갑자기 생겨나는 것이 아니며, 이 경우 어려운 문제 6번으로 곧장 뛰어들기 전에 여러분이 인내심을 가지길 바랍니다. 저는 큐브를 자르는 것과 관련된 겉보기에 완전히 다른 두뇌 퍼즐에 대해 이야기해 드리고 싶습니다. 이것은 IMO 문제보다 간단하고 매우 재미있으며, 타일링 퍼즐과는 아무 관련이 없어 보일지라도, 제가 말씀드리고 싶은 요점은 이것을 우리가 가지고 있는 주요 문제에 진전을 이루기 위한 첫 단계를 알려줄 수 있는 종류의 과거 경험으로 강조하는 것입니다.

자, 여기 두뇌 퍼즐입니다. 3x3x3 큐브를 상상해 보세요. 그리고 그것을 27개의 서로 다른 1x1x1 큐브로 자르고 싶습니다. 가능한 한 적은 절단으로 어떻게 할 수 있을까요? 규칙은 칼로 만드는 모든 슬라이스는 단일 평면을 따라 잘려야 하며, 지그재그나 구불거림 같은 것은 없습니다. 그리고 바로 눈에 띄는 방법이 있습니다. 각 좌표 방향으로 각각 두 개의 평행한 절단을 하여 모서리를 세 등분하고, 각 면을 아홉 등분하며, 전체 큐브를 이 27개의 1x1x1 조각으로 나누는 것입니다.

하지만 문제를 흥미롭게 만드는 주요 변형이 있습니다. 각 절단 후에 가지고 있는 조각들을 재배열할 수 있다고 가정해 봅시다. 예를 들어, 기존의 조각들을 쌓아서 다음 절단이 더 많은 전체 물질을 통과할 수 있도록 하는 것입니다. 다시 질문은 이것입니다. 가능한 한 적은 절단을 사용하여 이 27개의 각각 다른 1x1x1 큐브로 어떻게 자를 수 있을까요? 잠시 큐브라는 것에서 일반화하여, 만약 어떤 모양이든 자르고 있다면, 각 새로운 절단은 현재 가지고 있는 조각의 수를 최대 두 배로 늘릴 것입니다.

이는 모든 조각들을 다음 절단의 평면에 떨어지도록 재배열할 수 있다고 가정할 때 발생합니다. 이것이 의미하는 바는 네 번의 절단으로는 최대 16개의 다른 조각밖에 얻을 수 없다는 것이므로, 우리가 얻으려고 하는 이 27개의 조각이라는 특정 경우에 대해서는 그 가능성을 배제할 수 있다는 것입니다. 이제 다섯 번은 조금 더 흥미롭습니다. 원칙적으로 재배열을 통해 다섯 번의 절단으로는 최대 32개의 작은 조각을 얻을 수 있지만, 여기서는 특별히 이 작은 조각들이 평면에 놓여 있어야 합니다. 즉, 1x1x1 큐브여야 합니다.

그리고 자르면서 어떤 영리한 재배열을 할 수 있는지 직관적으로 알기 어렵습니다. 만약 이것을 전에 본 적이 없다면 잠시 멈추고 시도해 보세요. 저는 이렇게 좋은 질문을 너무 빨리 스포일러하는 것이 싫지만, 오늘 영상에서는 어쩔 수 없습니다. 제가 이 이야기를 꺼내는 유일한 이유는 답이 우리가 그 까다로운 문제 6에 접근하는 방법에 대한 통찰력을 강조하는 데 도움이 될 것이기 때문입니다. 자, 준비되셨나요? 요령은 내부의 1x1x1 큐브에 집중하는 것입니다.

완전히 잘라내려면 여섯 면 각각에 고유한 슬라이스 하나가 필요합니다. 단일 슬라이스로는 한 번에 하나의 면만 해제할 수 있습니다. 따라서 아무리 재배열하고 원하는 대로 쌓아 올릴 수 있고, 상상하는 모든 창의성을 발휘하더라도, 총 6개 미만의 절단으로는 불가능합니다. 제가 이 이야기를 꺼낸 요점은 통찰력이 적은 절단을 찾는 어떤 영리한 전략에 관한 것이 아니라, 왜 6이 최적의 숫자인지 증명하는 방법에 관한 것입니다. 그리고 그 증명에는 내부 큐브의 면들에 집중하는 것이 포함됩니다.

그리고 이것이 우리의 타일링 퍼즐과 어떻게 관련되는지 아마 보실 수 있을 겁니다. 궁극적인 목표는 단순히 사용할 수 있는 가장 적은 수의 타일을 찾는 것(그 자체로 이미 의미 있는 도전입니다)에 그치지 않습니다. 궁극적인 목표는 우리가 찾은 것이 최고라는 것을 증명하는 것입니다! 저는 만약 여러분이 과거에 이 큐브 퍼즐이나 비슷한 것을 본 적이 있다면, 그것이 우리의 다이어그램에 X 표시된 모든 사각형의 모서리들에 대해 생각하도록 마음을 이끌 수 있다고 주장하고 싶습니다. 그리고 각 모서리가 하나의 타일과 연관되어야 한다는 것을 알아차릴 수도 있을 겁니다.

그리고 우리는 다른 방향으로도 좋은 점을 가지고 있습니다. 두 개의 X가 같은 열에 있지 않기 때문에, 주어진 타일의 왼쪽 또는 오른쪽 모서리는 최대 하나의 X와만 접촉할 수 있습니다. 그리고 마찬가지로 위쪽과 아래쪽도 각 주어진 타일의 네 면은 최대 하나의 X와만 접촉합니다. 이것을 실제로 어떻게 사용할지 직관을 얻고 싶으므로, 제가 이 두 가지 다른 타일링 패턴을 살펴보기를 바랍니다. 오른쪽의 패턴이 왼쪽의 패턴보다 눈에 띄게 적은 타일을 사용하고 있습니다. 오른쪽 패턴의 어떤 점이 더 효율적인가요?