The Last IMO Problem AI Couldn't Solve

In 2024, Google DeepMind's AlphaProof team developed a model that successfully answered four out of six questions on that year's International Mathematical Olympiad (IMO) exam.

By 2025, various organizations had developed models capable of solving all but Problem 6, indicating rapid advancements in AI's ability to tackle competitive mathematics with a mix of Lean-based logic and natural language processing, albeit with human assistance in translating problems into formal systems like Lean.

The critical constraints are that each row and each column must have exactly one unit square not covered by any tiles, with a total of 2025 empty gaps in the problem. The objective is to find the minimum number of tiles required for this specific arrangement and provide a rigorous proof of its optimality.

The host notes that what often appears as genius is simply the 'residue of experience,' an accumulation of insights from past challenges like his cube-slicing puzzle.

The host introduces a cube-slicing puzzle as a parallel example to illustrate this concept.

This comparison aims to teach viewers the importance of patience and the search for broader patterns before attempting to solve complex problems directly.

Each 'X' represents a gap in the grid, which cannot share a row or column with another 'X', similar to how rooks are placed on a chessboard.

Tiles that touch four 'X's are considered the most efficient in covering the grid.

The 'X's positioned at the corners of tiles facilitate conflict-free 'windmill' patterns, such as those using 25 'X's in a specific configuration.

A grid with side lengths of k² can be covered by a pattern using (k-1)² square tiles, which provides optimal area coverage relative to the perimeter.

Square tiles, specifically k by k, prove to be optimal in terms of area coverage relative to their perimeter.

This construction utilizes (k-1)² square tiles in total, capitalizing on the square nature of the grid size, such as 2025, which is 45².

The total number of tiles for a grid of side length k is hypothesized by the speaker to be k² + 2k - 3.

The proposed formula for the minimum number of tiles is k² + 2k - 3.

This formula serves as a concrete conjecture to be tested and proven against the original IMO problem's conditions.

Attempting a one-to-one association by highlighting only the right edges of the 'X's reveals a clear weakness in the correspondence, which is reflected in a weak lower bound of k² - 1 tiles.

This method is inefficient because tiles on one side of the diagram remain unmatched, demonstrating that an arbitrary directional focus can create weak bounds, whereas respecting symmetry is crucial for stronger mathematical proofs.

Problem 6 on an International Mathematical Olympiad is known for its extreme difficulty.

Only six students achieved a perfect score on this particular problem during the actual IMO competition.

Significantly, this specific puzzle is the only one that has stumped all current AI models developed to solve IMO problems, highlighting a notable limitation in their capabilities.

A strategy is proposed to overcome the weakness of single-direction highlighting by simultaneously considering multiple directions.

This involves partitioning the grid into four distinct regions, each corresponding to a rightward, upward, leftward, or downward path.

X's located on the boundary lines between these regions can be assigned multiple highlighted edges, with the goal of ensuring each tile touches at most one highlighted edge to satisfy the lower bound proof.

The proof hinges on the crucial assumption that no single tile touches more than one highlighted edge.

Tiles within specific regions are constrained by a 'no highlight' rule for opposing directions; for instance, an 'X' to the left of a tile cannot have its right edge highlighted if the tile is in the leftward region.

This methodical approach ensures a consistent and tight association between tiles and edges, which is fundamental for validating the proof's lower bound.

As observed in examples, if a number is assigned to each tile indicating how many highlighted edges it touches, the result is consistently zero or one.

The core requirement to complete the proof, as Matilda notes, involves showing that the sum of the longest increasing and decreasing subsequences of the associated permutation is at least 2k, where k denotes the square root of the permutation size.

This transforms the original grid tiling problem into a purely mathematical question focused on permutations.

In this context, 'k' represents the square root of the permutation size, and achieving this result is identified as the core requirement to complete the overall proof.

This theorem establishes a relationship between the length of the longest increasing and decreasing subsequences within a sequence and the overall size of that permutation.

For instance, if the longest increasing subsequence has a length of 'n', the longest decreasing subsequence must also have a length of at least n/2.

The ingenious insight here is that all pairs (x, y), representing the lengths of the longest increasing and decreasing subsequences ending at a particular bar, must be unique.

If a second bar in the sequence is taller, its longest increasing subsequence length must be at least x + 1; conversely, if a second bar is shorter, its longest decreasing subsequence length must be at least y + 1.

This property ensures that each element within the permutation uniquely maps to a distinct lattice point, which is crucial for the proof.

The proof leverages two distinct paths that represent the longest increasing and decreasing subsequences.

These paths effectively divide the diagram into four separate regions, which are then used to identify specific subsets of edges.

Each highlighted edge is designed to correspond to a unique tile, thereby confirming the minimum tile count of k² + 2k - 3.

Reinforcement learning environments face significant hurdles with these structures, as Dang Luong noted the necessity of grasping the feel of a problem before writing a formal solution, a process far more difficult than purely symbolic reasoning.

Reinforcement learning environments find it difficult to tackle problems that necessitate a deep, intuitive understanding before a formal solution can be constructed.

Dang Luong emphasized that a fundamental grasp and 'feel' for a problem are essential prerequisites before attempting to formulate a written solution.

Historically, mathematical progress has served as a guiding light for human insight, furthering our collective understanding.

Generating proofs that do not inherently come with human understanding fundamentally undermines the purpose of the mathematical discipline.

Therefore, there is a growing need for new metrics to assess whether published mathematical work, especially that involving AI, genuinely advances human comprehension.

The intrinsic value of a mathematical question, much like art or literature, can be deeply human, extending beyond mere computational verification.