# The last IMO problem AI could not solve

Free AI summary of this YouTube video by SumTube AI (sumtube.ai).

- Recap: https://sumtube.ai/r/the-last-imo-problem-ai-could-not-solve-Nbwv5wHQoj0
- Markdown: https://sumtube.ai/r/the-last-imo-problem-ai-could-not-solve-Nbwv5wHQoj0.md
- Source video: https://www.youtube.com/watch?v=Nbwv5wHQoj0
- Channel: 3Blue1Brown

## TL;DR

This video breaks down Problem 6 from the International Mathematical Olympiad, exploring its optimal tiling construction and rigorous proof. It examines why this complex puzzle challenged both human contestants and advanced AI models, highlighting the role of intuition, patience, and structured reasoning. Beyond the technical solution, the discussion reflects on how the evolution of AI in mathematics reshapes the value of human understanding and proof.

## Key takeaways

- True problem-solving requires exploring the underlying structure patiently before rushing to solve
- Rigorous proofs often rely on mapping complex constraints to known mathematical structures like the Erdős–Szekeres theorem
- As AI solves open mathematical problems, the intrinsic value of math shifts toward fostering deep human understanding rather than just producing formal proofs

## Detailed summary

### Introduction & Context of IMO 2025 (00:00:00)

The video introduces the International Mathematical Olympiad held on the Sunshine Coast, Australia, where over 600 teenagers competed. Among the six problems, Problem 6 stood out as the most difficult, with less than one percent of participants achieving a full score. It also represented a key benchmark in AI capabilities, being one of the final competition problems that state-of-the-art AI models failed to solve.
Unlike standard computation, IMO problems demand creativity, deep conceptual understanding, and rigorous proof construction. Historical context shows the rapid progression of AI in mathematics from 2021 to 2025. While models progressively mastered various problem types, human contestants retained an edge on problems requiring patient exploration and structural intuition.

### Understanding Problem 6 (00:04:09)

Problem 6 specifies a grid of unit squares with a given side length and asks for the minimum number of non-overlapping rectangular tiles needed to cover it, leaving exactly one uncovered square in every row and every column. To make the problem tractable, the video scales down the problem to a 10 by 10 grid, illustrating how gaps are created and how different tiling configurations yield different total tile counts.
The challenge is twofold: first, finding an optimal construction that minimizes the total number of tiles, and second, proving rigorously that no other arrangement can use fewer tiles. Initial experiments demonstrate how placing gaps along a simple diagonal requires 2(n-1) tiles, prompting a search for more sophisticated, lower-count arrangements.

### Finding the Optimal Construction (00:06:49)

To build intuition for the proof, the video presents a simpler 3D cube-slicing puzzle: dividing a 3x3x3 cube into 27 unit cubes with the minimum number of planar cuts. The key insight lies in focusing on the central unit cube, which requires 6 distinct cuts to free its 6 faces. This demonstrates that proving lower bounds often involves identifying central or restricted elements rather than searching for clever strategies.
Translating this insight to the 2D grid, an optimal tiling strategy emerges by arranging gaps and square tiles in a tilted 'windmill' pattern. For a grid whose side length is a square number k^2, using square tiles of side length k achieves a highly efficient construction. For the original 2025 grid (where 2025 = 45^2), setting k = 45 yields a total tile count given by the formula k^2 + 2k - 3.

### Proving the Construction is Optimal (00:18:52)

Having established a candidate construction using k^2 + 2k - 3 tiles, the next task is proving that no valid arrangement can use fewer. A naive approach of highlighting one edge per gap square proves a lower bound of k^2 - 1 tiles, which is weaker than the target. The boundary tiles that touch fewer gaps explain why this simple counting argument falls short.
To tighten the bound, the argument divides the grid into four regions defined by two intersecting paths connecting the gap squares. Highlighting specific edges of the gaps based on which region they inhabit ensures that every tile touches at most one highlighted edge. This establishes that the number of tiles must be at least as large as the total number of highlighted edges across all regions.

### The Erdős–Szekeres Theorem (00:40:08)

To complete the counting argument, the positions of the gap squares are represented as a permutation of numbers from 1 to k^2. The two intersecting paths through the gaps correspond to the Longest Increasing Subsequence (LIS) and Longest Decreasing Subsequence (LDS) of this permutation. Counting the highlighted edges yields a lower bound expressed as k^2 + LIS + LDS - 3.
The Erdős–Szekeres theorem states that for any permutation of size N, the product of LIS and LDS is at least N. Applying the AM-GM inequality shows that the average of LIS and LDS is at least the square root of N, which equals k. Substituting this result into the edge-counting formula proves that the minimum number of tiles required is indeed k^2 + 2k - 3, matching the earlier construction and completing the proof for 2112 tiles when k = 45.

### Final Thoughts on AI in Math (00:45:56)

The conclusion reflects on why AI struggled with this problem and what it reveals about the nature of mathematics. AI researchers noted that current models lacked the 'patience' to explore and develop a felt sense for a problem before attempting a formal solution. Problems like IMO 2025 P6 require qualitative intuition and structural experimentation that go beyond immediate symbolic reasoning.
As AI systems become better at generating formal proofs, the primary purpose of human mathematics increasingly centers on deep understanding and motivated explanations rather than raw output. Prominent mathematicians emphasize that proofs serve as guiding lights to elevate human insight, suggesting that academic progress should value clear, explanatory narratives alongside formal correctness.

## Questions this video answers

### What is IMO 2025 Problem 6 about?

The problem asks for the minimum number of rectangular tiles required to cover a 2025 by 2025 grid such that exactly one unit square per row and column remains uncovered. Solving it involves discovering an optimal geometric arrangement and rigorously proving that no configuration can use fewer tiles.

### How is the Erdős–Szekeres theorem used in the proof?

The proof maps the gaps in the grid to a permutation and uses the Erdős–Szekeres theorem to relate the lengths of the longest increasing and decreasing subsequences to the grid size. Combining this with the AM-GM inequality establishes a strict lower bound on the required number of tiles.

### Why did AI models struggle with this specific IMO problem?

AI reasoning models often attempt to solve problems immediately rather than spending time building visual and conceptual intuition first. Problem 6 required holistic structure-building and patience, qualities that reinforcement learning models lacked at the time.

---
Summary by [SumTube AI](https://sumtube.ai/) — free YouTube summarizer.
