Solving the 2025 IMO tiling problem: windmill patterns, edges and the Erdos-Szekeres theorem

In this video, Veritasium examines a 2025 IMO tiling problem that asks for the minimum number of rectangular tiles needed to cover a 2025 by 2025 grid while leaving exactly one uncovered square in every row and every column. The presenter builds intuition with smaller cases, introduces a windmill tiling pattern using square tiles, and then outlines a rigorous proof that the minimum number of tiles is K^2 + 2K - 3 for K = 45, tying the construction to an Erdos-Szekeres type argument on sequences inside a permutation. The discussion also reflects on how problem solving blends patience, geometric intuition, and combinatorial tools, and considers why AI struggled with this problem on the IMO.

• Key insight: count edges around the gaps to bound tiles
• Windmill tiling: square tiles arranged so gaps sit at tile corners
• Permutation viewpoint and LIS/ LDS via Erdos-Szekeres
• Broader takeaway: balancing construction with rigorous, general bounds

Overview of the tiling problem

The video centers on a 2025 by 2025 grid, where Matilda places rectangular tiles along grid lines so that every unit square is covered at most once and every row and column leaves exactly one uncovered square. The aim is to minimize the total number of tiles while obeying this "one gap per row and per column" rule. The speaker uses progressively larger examples, showing how different tilings yield different tile counts and how the goal is to prove optimality, not just construct an example.

A constructive intuition from simpler puzzles

To gain intuition, the presenter first analyzes a 3x3 cube puzzle and a windmill tiling pattern on small grids. The windmill construction is built from square tiles and a ring of X marks that denote gaps. In the 5 by 5 interior tiling example, interior tiles touch four gaps, a pattern that looks highly efficient. Extending this idea, the speaker generalizes to tiles of side length K, tiling a K^2 by K^2 grid in a highly regular way that leaves K gaps per row and per column.

Counting strategy and the conjectured optimum

The formula for the total number of tiles in the windmill construction emerges as K^2 + 2K - 3. With the fact that 2025 equals 45^2, the proposed optimum count becomes 45^2 + 2*45 - 3 = 2112 tiles. The challenge, then, is to prove that no tiling requires fewer tiles for any arrangement of the gaps, at least in the square-number case.

Lower bounds via edge highlighting

One simple bound arises by highlighting every right edge of the gap squares. Each highlighted edge must touch a tile, and each tile can touch at most one such edge, yielding a baseline of K^2 - 1 tiles. The video then develops a stronger bound by refining the edge counting through a four region scheme, which balances efficiency across the diagram and yields the sharper bound K^2 + 2K - 3.

From edges to a permutation and LIS/LDS

The four region idea motivates a more precise counting in terms of two special paths, one following a longest increasing subsequence and another following a longest decreasing subsequence. Denoting A and B as the lengths of these sequences, the edge count translates to a bound involving A and B. A crucial observation is that for a grid of size K^2, the product AB must be at least K^2 by a permutation argument, and thus the average of A and B is at least K. This connects the tiling problem to a classic result in combinatorics known as the Erdos-Szekeres theorem.

The Erdos-Szekeres theorem and finishing the proof

The Erdos-Szekeres theorem asserts that in any permutation of N elements there exists a monotone subsequence of length at least sqrt(N). In the present setting N = K^2, so LIS and LDS are each at least K in many cases, and their product is at least N. Using the arithmetic mean-geometric mean inequality, the video shows that the average of LIS and LDS is at least sqrt(product) which, under the theorem, is at least K. Combining these facts with the edge counting bounds, one arrives at the sharper bound K^2 + 2K - 3 for the number of tiles, which matches the windmill construction when K = 45.

Putting it together and the concrete answer

Substituting K = 45 gives the exact minimum tiles for the original problem: 2112. The video emphasizes that the construction is not just a clever trick but a robust template whose optimality is proven by a clean, symmetric counting argument and a well known combinatorial theorem. The speaker closes by reflecting on how this problem illustrates the broader questions about AI, patience, and mathematical beauty, and on the value of a narrative explanation that helps humans understand proofs at a deeper level.