# The last IMO problem AI could not solve

## Executive summary

This video analyzes a challenging problem from the 2025 International Math Olympiad (IMO), which requires finding the minimum number of rectangular tiles to cover a $2025 imes 2025$ grid while ensuring every row and every column has exactly one uncovered unit square ('X'). The solution involves advanced combinatorics, establishing a conjecture for the minimum tile count ($k^2 + 2k - 3$, where $k= ext{side length}/ ext{root}$), and proving a rigorous lower bound using concepts related to Longest Increasing Subsequences (LIS) and Longest Decreasing Subsequences (LDS) of permutations. The discussion also reflects on the role of human intuition and creativity in mathematics compared to current AI capabilities.

## Key takeaways

- The IMO Tiling Problem: The goal is to find the minimum number of tiles required to cover a grid such that every row and column has exactly one gap ('X'). The optimal construction, conjectured to be the minimum, uses a pattern of square tiles of side length $k$, resulting in a total tile count of $k^2 + 2k - 3$.
- Proof Methodology (Lower Bound): A rigorous lower bound is established by defining a special subset of highlighted edges on the 'X' squares. By ensuring that every tile touches at most one highlighted edge, the number of tiles must be at least the number of highlighted edges. This leads to a bound based on the lengths of the LIS and LDS of the underlying permutation.
- The Role of Permutations and Subsequences: The problem is mapped onto a permutation of numbers from 1 to $N$. The final proof step requires showing that the sum of the lengths of the LIS and LDS must be at least $2k$ (where $k= ext{side length}/ ext{root}$), which is achieved by applying the Arithmetic Mean-Geometric Mean inequality and referencing the Erdős–Szekeres Theorem.

## Technical details

- Grid Tiling and Optimization: The problem involves tiling an $N imes N$ grid with rectangular tiles, subject to the constraint that every row and column must contain exactly one uncovered unit square (X). The optimal construction is conjectured to yield $k^2 + 2k - 3$ tiles, where $k$ is the side length of the constituent square tiles.
- Combinatorial Lower Bound: The lower bound for the number of tiles is derived by counting highlighted edges on the 'X' squares. If $A$ is the length of the LIS and $B$ is the length of the LDS, the number of tiles must be at least $ ext{LIS} + ext{LDS} - 4$ (or $ ext{LIS} + ext{LDS} - 2$ if paths intersect).
- Mathematical Theorems: The proof relies on the Erdős–Szekeres Theorem, which provides a bound on the product of the LIS and LDS lengths relative to the size of the permutation. The final step uses the AM-GM inequality to show that $ ext{LIS} + ext{LDS} ext{ must be } ext{at least } 2k$.

## Practical implications

- The problem demonstrates how abstract mathematical concepts (like LIS/LDS) can be used to solve concrete optimization problems (tiling).
- The methodology of establishing a lower bound by creating a unique correspondence (highlighted edges $ ightarrow$ tiles) is applicable to resource allocation and structural integrity analysis in engineering.
- The need for a 'motivated explanation' suggests that the process of understanding and articulating a solution is as valuable as the solution itself, a concept relevant to technical documentation and knowledge transfer.

## Topics

Combinatorics, Number Theory, Optimization, Algorithm Design, Artificial Intelligence (AI), 3b1b Talent, IMO-2025 Notes (Evan Chen), Dedekind Cuts Video

Source: https://www.youtube.com/watch?v=Nbwv5wHQoj0