The last IMO problem AI could not solve

Grant Sanderson walks through IMO 2025 Problem 6 — a tiling puzzle that frontier models missed — and the visual patience it takes to prove a construction is optimal.

GSGrant SandersonSpeaker · 3Blue1Brown
Channel
3Blue1Brown
Published
Sep 18, 2026
Video
51:55
Read
29 min
Slides
29
Original
English
Open on YouTube
Scroll to read and the video shrinks to the bottom-right corner. Captions follow your reading language.
Reading languageAvailable in 2 languages
You're reading the original English.
SUMMARY

In 30 seconds

In 2025, IMO Problem 6 was the hardest question on the contest and the last one that AI systems failed to solve. Grant Sanderson, with collaborator Nishad Deulkar, treats it as a beautiful tiling puzzle rather than an AI scoreboard: cover an n×n grid with rectangles so that each row and each column has exactly one uncovered square, and find the minimum number of tiles, with a proof. The path runs through a cube-slicing analogy, a windmill of square tiles that exploits 2025 = 45², a weak edge-counting bound, then a four-region highlighting argument whose extra edges come from the longest increasing and decreasing subsequences of a permutation. Erdős–Szekeres plus the AM-GM inequality close the proof at k² + 2k − 3 tiles. Sanderson argues that what matters is not the numerical answer but a motivated explanation — the kind of human understanding proofs-as-proxies no longer measure well once machines can generate the proofs.

  1. 1The last IMO problem AI missedFewer than 1% of the 2025 IMO contestants scored full marks on Problem 6. That same year, multiple organizations’ models solved every other question on the paper, in Lean or in natural language. By 2026, prompting public reasoning models was enough for all six.
  2. 2One uncovered square per row and columnMatilda tiles a 2025×2025 grid with non-overlapping rectangles whose sides lie on the grid lines, leaving exactly one uncovered unit square in each row and each column. The task is the minimum number of tiles, together with a proof that nothing smaller exists.
  3. 3Efficient tiles touch four gapsEach edge of a gap must meet a tile, and each side of a tile meets at most one gap. The efficient pictures are the ones where as many tiles as possible touch four X’s, and those X’s sit at corners in a windmill rather than in the middle of an edge.
  4. 4A construction that uses 2025 = 45²Square k×k tiles with a windmill of gaps around their corners assemble into a slightly tilted grid of side k². Setting k = 45 tiles the contest grid with (k − 1)² interior squares plus 4(k − 1) boundary pieces, which expands to k² + 2k − 3.
  5. 5Four regions from two monotone pathsTwo paths through the gaps — one longest increasing, one longest decreasing — divide the board into four directional regions. Highlighting one (or, on the boundary, two) edges per gap yields a 1-to-1 match with tiles and a count of k² + A + B − 3 highlighted edges.
  6. 6Erdős–Szekeres finishes the boundThe remaining claim is that the longest increasing and decreasing subsequences of any permutation of n = k² elements satisfy LIS · LDS ≥ n, hence (LIS + LDS)/2 ≥ k by AM-GM. Labeling each prefix with the pair of those lengths and plotting unique lattice points proves the product bound.
  7. 7Credit motivated explanations, not only proofsOnce machines can emit proofs of famous open problems, using proof as the proxy for academic progress no longer measures whether human understanding moved. Sanderson argues for elevating motivated explanations to the same status proofs have historically had.

Takeaways

  1. IMO 2025 Problem 6 was the last International Mathematical Olympiad problem that frontier AI systems could not solve; by 2026, publicly available reasoning models could handle all six questions.
  2. Solving an olympiad problem means writing a rigorous proof, which here required patience and a feel for the setup before searching for a strategy — something Thang Luong said models had not been taught.
  3. A cube-slicing puzzle supplies the key analogy: prove optimality by matching each tile to an edge of an uncovered square, because each side of a tile can touch at most one gap.
  4. When the grid side length is a square k², a windmill of k×k squares plus a thin boundary uses (k − 1)² + 4(k − 1) = k² + 2k − 3 tiles, and 2025 = 45² makes that construction available on the actual contest.
  5. A tight lower bound comes from highlighting edges according to four regions cut by a longest increasing path and a longest decreasing path, then invoking the Erdős–Szekeres theorem and the AM-GM inequality.
  6. Sanderson wants the community to treat motivated explanations — narratives that make a proof feel almost inevitable — as a form of mathematical contribution with the same status as the proof itself.
FULL TEXT

Read the edited text by chapter

01

The one that AI missed

IMO 2025 Problem 6 was the hardest question on the paper and the last one AI failed. Sanderson frames the video as a deep dive into a beautiful proof, not an AI recap, and quotes Thang Luong on patience: models did not take time to understand the problem before trying to solve it.

In 2025 more than 600 teenagers gathered on Australia’s Sunshine Coast for the International Mathematical Olympiad. The contest has six problems; Problem 6 was the hardest by far. Despite every contestant being among the best in their country, fewer than 1% scored full marks on it. It also looks likely to be the last IMO problem that AI could not solve — a sentence that would have sounded ridiculous to people who know contest math even five years earlier.

If you are outside this world, the thing to understand is that these problems are designed to require imagination and creativity. They are not rote memorization or computation. Solving one does not mean producing a numerical answer. It means writing a full rigorous proof, and the spirit of the contest is that finding that proof should require a nuanced, deep understanding of a particular setup.

Step back to 2021. By then there had been impressive AI results in games, and scaling laws for natural language were already clear, but a lot of people still saw the IMO as a different ballgame. It mixes rigor with creativity, and the search space of logical moves while writing a proof is effectively infinite.

On Dwarkesh Patel’s podcast in 2023, one of his questions was whether an AI that can get gold at the IMO is just AGI. The very next year, Google DeepMind’s AlphaProof team produced a model that answered four of the six questions on that year’s exam. There is an asterisk: humans still had to translate the problems from English into Lean, a language in which mathematical proofs are programs. Even so, AlphaProof was doing the substance of finding the proof, and that alone surprised many people.

In 2025 multiple organizations tried the test, some in Lean and some purely in natural language. End to end, models answered every question except this Problem 6. By 2026, simply prompting reasoning models available to the public was enough to get correct answers on all six. That undersells how far the models have come: the IMO almost feels like ancient history as a benchmark, as everything has speed-run into research math over the last year.

Sanderson will come back to AI and math at the end. For now the video is mostly not about AI. It is a deep dive into a beautiful problem. As we see the path to solving it, it is worth asking what allowed a few brilliant students to find the answer when no machine could.

He put that question to Thang Luong, a director of research on the Google DeepMind team that built their reasoning model for that year’s test. Luong said they did not really have a way to teach the model to be patient: it did not take time to understand the problem, to get a feel for it, to not try to solve it yet. Patience is definitely required here, and so is something Sanderson wants to add: models, at least as he has interacted with them, do not seem to have a great sense for what makes a problem or a strategy beautiful, and finding this solution benefits from an appreciation of beauty.

02

The problem

Tile an n×n grid with rectangles so each row and each column has exactly one uncovered square. On a 10×10 sketch, naive placements use 21, then 17, then 16 tiles; the diagonal construction uses 2n − 1. The contest asks for the minimum and a proof that it is best.

The problem begins: consider a 2025×2025 grid of unit squares. That is unwieldy to draw, so the animations start with something smaller, a 10×10. Matilda wants to place rectangular tiles, possibly of different sizes, so that each side of every tile lies on the grid lines and every unit square is covered by at most one tile. The tiles do not overlap.

The question asks for the minimum number of tiles that follow a key rule: each row has exactly one unit square not covered by any tile. Those gaps are marked with X’s. Likewise, each column has exactly one uncovered square. On the 10×10 that means ten gaps; on the real board there would be 2,025.

A first 10×10 example uses 21 tiles and obeys the rule — no two X’s share a row or column — but it is not the smallest. A different set of gaps gets down to 17. Another attempt manages 16. Because this is the IMO, the task is not merely a numerical answer, and it is more than exhibiting a construction. The construction is part of it. The real challenge is to prove that whatever minimum you find really is the best.

It is hard even to think of generalizable descriptions of where the tiles go. The easiest case is to put all the X’s on a diagonal and cover the rest with horizontal tiles. For a grid of side n, that uses n − 1 tiles on the right and n − 1 on the left, for a total of 2n − 1. The construction is obvious, and it is unlikely to be what the IMO is asking for. What you want is some other general way to place the X’s and the tiles around them that gives a smaller count as a function of n.

03

Finding the optimal construction

A cube-slicing puzzle shows why matching tiles to gap edges is the right instinct. Tiles that touch four corner X’s in a windmill assemble into square k×k blocks on a k² grid. Because 2025 = 45², that construction is available, and it uses k² + 2k − 3 tiles.

How do you even begin? A general lesson about problem solving is that what can look like genius is usually the residue of experience. Insights do not come from nowhere. Before jumping into Problem 6, Sanderson wants you to be patient with a seemingly different brain teaser about slicing a cube — simpler than an IMO problem, very fun, and the kind of past experience that might inform the first steps on the tiling puzzle.

Imagine a 3×3×3 cube that you want to cut into 27 unit cubes, using as few cuts as possible. Each slice of the knife cuts along a single plane: no zigging or zagging. There is an obvious way to do it in six slices: two parallel cuts along each coordinate direction, dividing each edge into thirds and the whole cube into 27 little cubes.

The interesting variation is that after each slice you may rearrange the pieces, stacking chunks so the next cut goes through more material. How few slices can you use now? For an arbitrary shape, each new slice at most doubles the number of pieces, assuming you can line everything up in the plane of the cut. Four slices give at most 16 pieces, so they cannot produce 27 cubes.

Five slices could in principle produce 32 pieces, but the pieces specifically have to be 1×1×1 cubes, and it is not obvious what rearranging would make that possible. If you have never seen the puzzle, it is worth pausing. The reason for bringing it up is that the answer highlights the insight for Problem 6.

The trick is to focus on the inner unit cube. To cut it free, each of its six faces needs its own slice. A single slice never frees more than one of those faces. Therefore, even if you rearrange and stack as creatively as you like, you cannot use fewer than six cuts. The insight is not a clever strategy for fewer cuts. It is how to prove that six is optimal, by focusing on the faces of that inner cube.

You can see how this relates to the tiling puzzle. Finding a small number of tiles is already a challenge; the ultimate goal is to prove that what you find is the best. If you had seen the cube puzzle, it might direct you to the edges of the X’d-out squares. Each of those edges has to be associated with a tile.

There is a matching constraint the other way. Because no two X’s share a column, the left or right edge of a given tile can touch at most one of them, and likewise for the top and bottom. Each of the four sides of a tile touches at most one X.

Look at two tilings where the one on the right uses notably fewer tiles. What makes it more efficient? First place the X’s; the rule that no two share a row or column is the same as placing rooks that cannot attack each other. Highlight the four edges of each gap. Every time you add a tile, turn off the highlighted edges it touches.

Some tiles turn off multiple edges, sometimes as many as four; others turn off only one, or even zero. Eventually every highlighted edge has to be turned off — almost. There are four exceptions, the edges that already touch the outer boundary of the board. That is a clean way to say what is wasteful about the left-hand picture: those tiles touch only one X, or none.

On the right, each of the highlighted tiles touches four X’s. From the point of view that a tile’s primary duty is to cover a gap edge, those are as efficient as they can be. The intuition is fundamental enough to write down as a conjecture: the most efficient tiling should have as many tiles as possible touching four different X’s. If a tile ever touches fewer, it feels like a waste of its potential.

Abstract away from the grid and imagine the tiles freely floating, each touching four X’s somewhere on its boundary. The goal is to fit them together like a puzzle. Focus on one tile and try to fit two others above and below the X on its right side. Something is about to be inefficient. You want every tile to touch four X’s, but those two new tiles will conflict on their left edges: because those left sides align, and because no two X’s can share a column, they cannot both touch an X on the left. One of them has to give it up.

The same issue comes up whenever an X touches a tile in the middle of an edge. Slide that X up to the corner, and you can comfortably fit four tiles around it in a windmill without forcing a conflict. That is the next piece of intuition: not only should tiles touch four X’s each, but if they are going to work in harmony, those X’s have to sit at the corners.

You still have freedom to choose any rectangle, but it is natural to start with squares. Squares are symmetric, and math tends to reward you when you respect its symmetries. They also cover more area for a given perimeter, which feels efficient when you want to cover a grid with as few tiles as possible.

Once you hypothesize that the optimal tiling uses square tiles with X’s in a windmill around their corners, fitting them together really is a physical puzzle. The pieces stack nicely. Starting with 5×5 squares is arbitrary: after four of them, adding one more would put two X’s in the same column, so you attach the next one offset and keep building.

Continuing that way yields a slightly tilted 4×4 pattern of square tiles, each with a windmill of X’s, using 25 gaps in total. The X’s sit in distinct rows and columns, so a large grid around them fits the problem. You do need a couple of tiles around the edges to fill in, so it is not true that every tile touches four X’s — but all the interior ones do, which feels efficient.

Starting with 5×5 was arbitrary. 4×4 squares give a smaller arrangement with 16 holes; 3×3 squares give nine. In general, if k is the side length of those square tiles, the pattern tiles a big grid whose side length is k². If you are going into the 2025 IMO, you know that 2025 is a square, specifically 45². Setting k = 45 gives a pretty tiling of the original board, and a conjecture for the smallest possible number of tiles. Using the squareness of 2025 feels like the kind of construction the IMO might want.

On the theme that genius is the residue of experience, there is another way a 2025 contestant might have been drawn to the pattern: the floor of Australia’s Sunshine Coast Airport, where they would have landed, is tiled in the same staggered squares. We now have a conjectured best tiling. Keep k as the side length of the small squares and k² as the side of the big grid.

For k = 5 the interior uses 16 square tiles, which is (k − 1)². The boundary uses four tiles per side, which generalizes to k − 1 per side, or another 4(k − 1). Expanded, the count is k² + 2k − 3. That is a tangible conjecture. We are still far from done, because the aim now is to prove that this expression is the minimum: that every other arrangement of X’s and tiles uses at least this many, at least when the grid side is a square.

How do you prove something like that? The collection of every possible arrangement of gaps and every possible tiling around them is incredibly complicated. Getting a foothold on a rigorous claim that covers all of those patterns is the real challenge — as it should be. This is the hardest problem on an IMO. There is no world in which it was going to be easy.

04

A weak lower bound

Counting all four edges of every gap gives at least k² − 1 tiles, short of the extra term proportional to k. Highlighting only right edges makes the 1-to-1 matching cleaner but still misses a cluster of tiles on the opposite side — a symmetry the later proof will have to restore.

We do have an advantage, because the same intuition that guided the construction — tiles need to cover every edge of an X — also gives a toehold on the proof. The total number of X’s is k², nine in the small example on screen. Highlighting all of their edges gives 4k² highlighted edges, and every tile touches at most four of them, so you need at least k² tiles.

That is not quite right: the four highlighted edges on the outer boundary of the whole diagram do not need to be hit by any tile. So there are 4k² − 4 relevant edges, and each tile still touches at most four, which means at least k² − 1 tiles. On one hand, we have proved some kind of lower bound. On the other, it is weaker than we need. The conjectured construction has another term proportional to k, the square root of the grid size.

That extra term makes sense: in the arrangement we hope is optimal, not every tile touches four X’s. The ones around the boundary only touch two. Sanderson spent a long time in a notebook trying to find an elegant argument that would bound the number of tiles that must sit on the edge. An honest portrayal of the dead ends would make this a nine-hour video. Nothing really worked, and there is a fundamental reason why — but that is not to say we cannot still run with highlighted edges.

Think back to the cube. The key was a one-to-one correspondence between the faces of the inner cube and the slices of the knife. So far the tiling argument is more like a 4-to-1 correspondence between gap edges and tiles. There is a simpler way to get the same k² − 1 bound as a 1-to-1 association: rather than highlighting every edge, highlight only the right edges of the X’d-out squares.

Each of those right edges must touch a tile, and any given tile can touch at most one of them, because no two X’s share a column. Again there is a boundary exception: the rightmost edge does not need to touch a tile. So once more you need at least k² − 1 tiles. This framing is more productive because you can see where it is inefficient. You miss a lot of tiles specifically on the left side of the diagram.

If you instead highlighted only the top edges, you would miss many tiles around the bottom. For any one direction, the tiles you miss are clustered to one side. Math rewards you when you respect its symmetries, and here it punishes you if you do not. Choosing an arbitrary direction shows a clear weakness in the association, and that weakness is reflected in the weakness of the inequality: at least k² − 1, when what we want is k² + 2k − 3.

That k² + 2k − 3 was the number from the hoped-for optimal arrangement. For a savvy contestant aiming to prove the sharper bound, now is a good time to pause. This is P6 on an IMO. Only six students there got a perfect score on it, and it is the only one that all of the AIs stumbled on. Any proof we write is going to be something difficult to find.

05

Proving the construction is optimal

Two monotone paths through the gaps cut the grid into four regions. Highlighting edges by region, with extras on the boundary, never puts two highlighted edges on the same tile. The resulting count is k² plus the two path lengths, minus a small constant, which is tight if those lengths sum to at least 2k.

Take stock. The strategy is to highlight a specific subset of edges and argue that every such edge touches a unique tile, so the number of tiles is at least the number of highlighted edges. The one-direction version is tight near one side of the diagram and misses a cluster on the other. The goal is to improve k² − 1 to k² + 2k − 3. A natural question is how to modify the same strategy to fix the weakness.

Can you highlight a few more edges — preferably exactly k² + 2k − 3 of them — in a way that avoids the inefficiency of focusing on one direction? You have to be careful. For the strategy to work, when you ask how many highlighted edges a given tile touches, the answer must always be at most one. The whole premise is at least one tile per highlighted edge, so there can be no double counting.

There is something a little weird about the target. Look at k² + 2k − 3 as k gets large. If that is the final number of highlighted edges, then in the large cases most but not all of the X’s get a single highlighted edge, and on the order of 2√n of them get more than one. That might feel almost antithetical to a beautiful symmetric construction. The next step is the hardest in the whole argument to motivate, so it helps to start with a high-level sketch.

Highlighting the rightward edges of all the X’s felt more efficient near the right side. So what if you highlight the right edge of an X only when it falls in some rightward region of the grid? Similarly, highlight the top edges only in an upward region, the left edges only in a leftward region, and the bottom edges only in a bottom region. For the moment the four regions, and the boundaries between them, can stay vague. The sketch is just a way of avoiding the weakness of one direction at a time.

The same intuition suggests where the extra highlighted edges might come from. We need more tiles than there are X’s, so however we define the four regions, any X that sits on the boundary between them could get multiple highlighted edges, since it is part of two regions at once.

To make it concrete, scale down. Motivated by dividing the diagram into four regions, draw a path going up and to the right that connects a sequence of X’s, and another going down and to the right, leaving a big wobbly cross over the whole board. The reason to go through X’s is that we want them on the boundary so that highlighting multiple edges for those X’s raises the count.

Having chosen two paths, the regions can be defined exactly. If an X lies to the right of both paths, highlight its right edge. If it sits above both, highlight its top edge, and likewise for the left and the bottom. For any X on the boundary, highlight two of its edges depending on which quadrant it sits in. That is desirable: we ultimately need a few more highlighted edges than X’s.

Remember the goal. We want to argue that no matter how the X’s are arranged and no matter what pattern of tiles covers the remaining squares, the number of tiles is at least the number of edges we are highlighting. That is true as long as every highlighted edge touches one tile and every tile touches at most one highlighted edge. In the example on screen, if you put a number on each tile for how many highlighted edges it touches, you only ever get zero or one. No tile touches two.

Why can’t a tile touch two highlighted edges under this setup? The entire argument rests on that. Focus on a tile sitting in the left region. It may be touching four X’s, but only one of them has a highlighted edge against the tile. Any X above it could only ever have its left or top edge highlighted — the bottom edge cannot be, by how the regions were defined. Any X below it cannot have its top edge highlighted. The X to the left cannot have its right edge highlighted, which would require it to sit in the rightward region.

Dividing the grid into four regions not only makes a tighter association between highlighted edges and tiles. It also keeps the critical property that no two highlighted edges can touch the same tile. This diagram is the core of the proof. What remains is to show why the setup gives the specific tight bound k² + 2k − 3, which comes down to counting how many edges we have highlighted, and that in turn comes down to how many X’s lie on the two boundary lines that crisscross the diagram.

At this point it helps to put labels on the X’s rather than thinking purely pictorially. Above each X write the number of the row it sits in. Because every row has exactly one X, those labels are every number from 1 up to k², in some shuffled order: a permutation. A path going up and to the right corresponds to a strictly increasing sequence of labels — an increasing subsequence of the permutation. A path going down and to the right is a decreasing subsequence.

Call the length of the increasing subsequence A and the length of the decreasing subsequence B. To count highlighted edges: each of the k² X’s gets at least one, or rather almost all of them do. There should be four exceptions, the X’s touching the boundary of the grid, since those need not touch a tile. Subtract those off. Then there are extras: each X on the increasing subsequence gets a second edge, adding A, and each on the decreasing subsequence adds another B.

If we are being detail-oriented, which we have to be, there is one other possibility: an X that sits on both paths. In that case all four of its edges would be highlighted, but as counted so far it would have been counted only three times — once for existing, once for the increasing subsequence, once for the decreasing. In that special case we need to add another one. That expression is now tantalizingly close to what we want.

What we have effectively proven is that for any arrangement of X’s, described by a permutation of 1 through k², if you choose an increasing subsequence of length A and a decreasing subsequence of length B, the number of tiles must be at least this big. Contrasted with the conjecture, the natural hope is to argue that A + B ≥ 2k, twice the square root of the grid’s side length. Close, and a little weird: how can you guarantee that no matter what the X’s look like, you can choose an increasing subsequence and a decreasing subsequence whose lengths sum to at least twice the square root of the grid size?

06

One final conjecture

Taking the longest increasing and decreasing subsequences, the claim becomes that their average is at least √n. Motivating examples suggest their product is at least n, which with AM-GM would give the average bound. That product inequality is the Erdős–Szekeres theorem.

First specify that A is not just any increasing subsequence but the longest possible one, and rename it LIS. Likewise take the longest possible decreasing subsequence, LDS. Rearranging slightly, the final step of the proof is to show that the average of these two lengths is always at least k, the square root of the size of the permutation. That fact no longer has anything to do with the grid. It is a pure fact about permutations.

The visuals can abstract away from the grid, representing each number as a bar whose height equals that number. Permutations whose decreasing subsequences are all very short tend to have a very long increasing subsequence, and on the flip side, any permutation whose increasing subsequences are all short has a very long decreasing subsequence. To finish the proof we need to make that tradeoff quantitative: no matter the permutation, the average of LIS and LDS is at least the square root of n.

That is a mouthful, and we have already been through a lot. One more proof within a proof might strain the focus you can reasonably ask of a viewer, but the final step is a gem. An honest depiction of an olympiad student who had made it this far would have them cite something from training, the Erdős–Szekeres theorem. Sanderson does not want to pull a fact from out of the blue. He wants it to feel like something you could have discovered yourself, even if that adds a couple of minutes to an already long journey.

To build intuition, look at extremes. The trivial permutation that lists 1 through n in order has LIS of length n and every decreasing subsequence of length 1. Listing all the even numbers in order and then all the odds gives LIS at least n/2 — “at least,” because n might be odd — and LDS equal to 2. Counting up by threes, you get LIS at least n/3 and LDS equal to 3.

Mulling over that family of examples, you might conjecture that the product of the two numbers is always at least n. One example in the family looks very familiar. If n is a square, k², you get exactly the pattern of X’s in the optimal grid. There are many choices for a longest increasing subsequence, but all of them have length k, and likewise LDS is k. In that special case the product is k², precisely the size of the permutation.

The conjecture, based on these examples, is that for any permutation the product LIS · LDS is at least n. Compare that to the goal, which is that the average of the two is at least √n. To an olympiad student it would be immediately clear that the product bound gives what we need. A very common inequality they know like the back of their hand is that (a + b)/2, the arithmetic mean, is always at least √(ab), the geometric mean.

Applied here, the arithmetic mean of LIS and LDS is at least the square root of their product, and if the conjecture is true that whole expression is at least √n. Remember why we care: the highlighted-edge argument with two paths gave an expression in terms of those two lengths. We want it to be at least the number of tiles in the optimal construction, which boiled down to the sum of the path lengths being at least 2k. By AM-GM, that holds if the product of the two lengths is always at least n.

If that seems like a lot to hold in your head, this is a hard problem. Everything has now boiled down to one conjecture. Before stepping back to reflect, there is one last mile: why the inequality is true. We are not the first to conjecture it. It is well known in the study of permutations, and it is called the Erdős–Szekeres theorem.

07

The Erdős–Szekeres theorem

Label each position by the lengths of the longest increasing and decreasing subsequences ending there. Those pairs are unique, so they inject into a LIS-by-LDS box of lattice points, hence LIS · LDS ≥ n. Combined with AM-GM this proves at least k² + 2k − 3 tiles; for k = 45 that is the contest answer.

In the actual olympiad, a student could simply reference that theorem and be done. Sanderson could spare you the cognitive effort and do the same, maybe linking to Wikipedia and wrapping up. The proof of the fact is really pretty in its own right, and it would be a shame to rob you of it just to shave two minutes of runtime. It is a pleasing finishing touch before we step back.

The idea is to look partway through the list and ask about the longest increasing and longest decreasing subsequences ending at that point. For the bar highlighted on screen, those lengths are 2 and 3. Write that down as a pair of numbers under the bar, and do the same for every other term in the permutation. Pulling up another example: a bar might have LIS-ending-here of length 3 because two increasing bars sit to its left, while the longest decreasing subsequence ending there has length 2.

The clever idea is that all of these pairs must be unique. Focus on two bars, and say the left one is labeled (x, y). This is a permutation, so all the numbers are distinct, and one bar is taller than the other. If the second bar is taller, you can take the longest increasing subsequence that ends at the first bar, of length x, and extend it by one, so the longest increasing subsequence ending at the second bar is at least x + 1.

Analogously, if the second bar is shorter, you can extend the longest decreasing subsequence that ends at the first bar, of length y, so the second label on the second bar is at least y + 1. Either way, one of the two numbers in the second pair is bigger than the corresponding number in the first pair. The labels really are distinct.

Having written down a bunch of pairs, it is hard not to plot them as points on a coordinate grid. The longest overall increasing subsequence is the biggest x-coordinate, the width of a bounding box around the points. The longest overall decreasing subsequence is the biggest y-coordinate, the height of that box. The area of the box, width times height, is the same as counting the lattice points inside it.

Since every element of the permutation corresponds to a unique lattice point, the product of those two numbers must be at least the number of elements in the permutation. That was the conjecture. It is lovely, too beautiful not to share.

As a final piece, step back and summarize, because it was a lot. The problem asked for the smallest number of tiles that leave one gap per column and one per row. The claim is that the smallest number comes from the special grid pattern of square tiles of side k, using k² + 2k − 3 tiles in total. Most of the first half of the video was leading up to a diagram; that is where the proof you would write down actually begins.

For any tiling, consider the gaps, and draw two paths: one connecting a longest increasing subsequence and one connecting a longest decreasing subsequence. Those paths divide the diagram into four regions, which define a special subset of the edges of the X’d-out squares to highlight — right edges in the right region, top edges in the top region, two edges on the boundaries. Each such highlighted edge corresponds to a unique tile, so the number of tiles is at least the number of highlighted edges.

The number of highlighted edges works out to k² plus LIS plus LDS, all minus 4. If the paths intersect you get to add one, and the −4 becomes −3. There is a nuance glossed over so far: even if the paths do not intersect at an X’d-out square, you are still safe to add one, because then they intersect in a tile, and that middle tile would not be touching any highlighted edges. So you can add one to the count either way. That expression really is a lower bound on the number of tiles.

That in turn proves the bound we want, k² + 2k − 3 from the optimal tiling, as long as the sum of the two path lengths is at least 2k — which is what the last section proved, combining AM-GM with Erdős–Szekeres. Plug in k = 45 and you get the numerical answer to the original question. The numerical answer is a very small part of the point. The real point is the construction and a rigorous proof that it is optimal. It might have taken a while, and a fair bit of patience. We have done exactly that.

08

Reflections on AI in math

Sanderson refuses a Lee Sedol–versus–AlphaGo framing. The work with Nishad Deulkar was to invent a motivated explanation, not a new proof. As machines produce proofs without understanding, he argues the community should credit that kind of explanation as seriously as it credits proofs, a theme he also took to Terence Tao’s blog.

What is the point? What do we learn by seeing how to solve a problem like this? Sanderson switches to a face-to-face outro. He introduced the problem as the last IMO problem AI could not solve, which might suggest a conclusion framed like game four between Lee Sedol and AlphaGo: humanity’s last stand before the machines just got categorically better.

A lot of viewers have probably been asking what made this problem so hard for the AIs. There is natural speculation. A great deal of the work was visual intuition, which is harder to train for than purely symbolic reasoning. A more subtle point is the one Thang Luong made: this is the kind of problem you cannot immediately start writing a solution for. You have to understand it and get a feel for it first. That structure is intrinsically harder for a reinforcement-learning environment.

Sanderson’s own relationship to the problem points somewhere else, something more important in the broader story of AI and math, and it has nothing to do with when AI could and could not solve problems like this. He wrote the video with Nishad Deulkar. When they set out, the goal was not to find a new proof of an unsolved problem. The proof already existed. It even existed on YouTube: a channel called Dedekind Cuts covers a lot of IMO problems, including this one.

So why make the video? What was new to contribute? Knowing a proof is only a very small part of what it feels like to deeply understand a piece of math. This proof in particular was one where Deulkar and Sanderson looked at it and said, I see that this works, but how on earth would you come up with that? You define a longest increasing subsequence, a longest decreasing subsequence, a certain association between edges and tiles — and without leading context you can follow the steps and be left feeling it is a complete bolt from the blue.

In the video itself he talked about the qualitative difference between finding the construction and articulating a proof. What he did not mention is yet another level of engagement that also feels qualitatively different: creating a narrative by which a viewer can feel as if that proof is almost obvious. We know it is not obvious. Only six of the students solved this. It is a demonstrably hard question. But if they have done their job, by the time the proof itself was being articulated it did not feel like a bolt from the blue.

Finding that kind of narrative is deeply rewarding and very creative. He always comes out understanding a piece of math much better than he did by simply understanding the proof. It helps to give the other thing a name. For lack of a better one, he calls it a motivated explanation.

Step outside this toy problem to the broader world, where machines are producing proofs of famous unsolved problems, and you see mathematicians reflecting that the purpose of doing mathematics, as they understand the practice, has always been furthering human understanding. The role of proofs and open problems has been a guiding light, showing where and how to push that understanding forward. The solution is almost never something you plug into an application and get utility out of. It is more subtle than that.

For a human to find these proofs, they have to figure out patterns of thinking, constructs, and new mathematical objects that elevate their understanding enough to make the proof available. What is useful is not the proof or even the result. It is the surrounding understanding and the spillover effects it can have into the engineering world. If you generate proofs that do not come with human understanding, that kind of completely defeats the point.

That raises a serious question about how we measure academic progress. Using proof as a proxy is so deeply ingrained in what we give academic credit for that it exposes a stark need for a new, distinct way to measure whether someone’s published output really does push forward human understanding. Sanderson thinks the idea of a motivated explanation could do a lot to fill that void. The community should try to formalize what it means, then elevate it to the same status — and the same academic credit — that proof historically has.

He has more thoughts on the topic. He wrote a guest post for Terence Tao’s blog about it, and recorded it as a video on this channel. He guesses this will be the first of many thoughts he wants to express about AI and math. For today, back on this IMO problem from 2025, he closes with a sentiment from the comments on Patreon, where he posts videos early for supporters. One of them left a quote from a friend who had solved this problem.

“This question doesn’t contribute to a deep understanding of mathematics, nor is it particularly difficult when compared with mathematical research. Rather, the value of this question lies in the fact that it warmed my heart when I solved it. And it still warms my heart more than a year later. Like a good book or a touching song, the value here is human. Call me humanist, but I truly believe that the value of this question as a mathematical discovery exceeds that of the average PhD thesis.”

More from this channel