AIME 2026 I · 第 15 题

Solution 1

(This solution has two parts: a computational part and a proof part. Readers who only care about the main idea may focus on the first part.)

A loop is defined to be the border of an axis-aligned rectangle of cells, with both dimensions at least $2$.

In any partition of the $10\times10$ grid into $5$ loops, the loop containing the corner cell $(1,1)$ must span an entire side of the grid; otherwise, uncovered boundary cells force too many loops (this will be proved later). Hence that loop must be one of size $10\times2$, $10\times4$, $10\times6$, $10\times8$, or $10\times10$. Odd widths are impossible, and smaller shapes fail; these facts will also be proved later.

If the corner loop is $10\times10$, then removing it leaves an $8\times8$ square, which has already been shown by direct casework to admit exactly $27$ partitions into $4$ loops.

If the corner loop is $10\times8$, then removing it leaves a $10\times2$ strip and an $8\times6$ rectangle. The strip is forced to be one loop, and the $8\times6$ rectangle has already been shown to admit exactly $5$ partitions into $3$ loops. This gives $5$ partitions in this case.

If the corner loop is $10\times6$, then removing it leaves a $10\times4$ strip and an $8\times4$ rectangle. Each of these must use exactly $2$ loops. A $10\times4$ rectangle can be partitioned into $2$ loops in $2$ ways, and an $8\times4$ rectangle can be partitioned into $2$ loops in $2$ ways, giving $2\cdot2=4$ partitions.

If the corner loop is $10\times4$, then removing it leaves a $10\times6$ rectangle and an $8\times2$ strip. The strip is forced to be one loop, and the $10\times6$ rectangle admits exactly $5$ partitions into $3$ loops, giving $5$ partitions.

If the corner loop is $10\times2$, then removing it leaves a $10\times8$ rectangle, which has already been shown to admit exactly $14$ partitions into $4$ loops.

By symmetry, the horizontal cases $2\times10$, $4\times10$, $6\times10$, and $8\times10$ contribute the same numbers as $10\times2$, $10\times4$, $10\times6$, and $10\times8$ respectively, while the $10\times10$ case is self-symmetric and counted once.

Adding all cases gives $27+2(14+5+4+5)=\boxed{83}.$

Thus, there are exactly $83$ ways to partition the $10\times10$ grid into $5$ loops.

Proof, for those who care

Lemma 1. In any partition of the $10\times10$ grid into five rectangular cell loops, the loop containing the cell $(1,1)$ must contain either the entire top row or the entire left column.

Proof. Let $L$ be the loop containing $(1,1)$. Since every loop is the border of an axis-aligned rectangle of cells, $L$ is the border of some $r\times c$ rectangle whose top-left corner is $(1,1)$. Thus $L$ occupies the cells $(1,j)$ for $1\le j\le c$ and $(i,1)$ for $1\le i\le r$.

Suppose for contradiction that $L$ contains neither the entire top row nor the entire left column, so $r\le9$ and $c\le9$. Then the boundary cells $(1,c+1),(1,c+2),\dots,(1,10)$ are uncovered, as are the boundary cells $(r+1,1),(r+2,1),\dots,(10,1)$.

Any loop containing one of the uncovered cells on the top row must have its rectangular border’s top edge on row $1$ and cannot intersect $L$, so such cells force the existence of a loop disjoint from $L$ and lying entirely to the right of $L$. Similarly, the uncovered cells on the left column force the existence of a loop disjoint from $L$ and lying entirely below $L$. These two loops are distinct, since a single rectangle border cannot cover both separated boundary portions without crossing $L$.

If $r\ge3$ and $c\ge3$, then $L$ encloses an interior rectangle of size $(r-2)\times(c-2)$, which is a connected component separated from the rest of the grid and therefore must be covered by at least one loop contained entirely inside $L$. There also remain uncovered cells outside $L$ that are not contained in the two boundary-forced loops, so the exterior region requires at least one additional loop.

Thus at least five loops are already forced, leaving no slack, and in fact the interior or exterior regions are not themselves rectangular borders and therefore require more than one loop, giving a contradiction. If $r=2$ or $c=2$, then $L$ already contains the entire top row or entire left column. Hence the assumed situation is impossible, and $L$ must contain the entire top row or the entire left column.

Lemma 2. In a partition of the $10\times10$ grid into five rectangular cell loops, the loop containing $(1,1)$ cannot be the border of a $10\times k$ or $k\times10$ rectangle with $k$ odd.

Proof. By symmetry, it suffices to rule out a $10\times k$ corner loop with $k$ odd and $k\le9$. Let $L$ be such a loop. Removing the border of $L$ leaves two regions: a right strip of size $10\times(10-k)$ and an interior rectangle of size $8\times(k-2)$. Since $k$ is odd, both $10-k$ and $k-2$ are odd.

We claim that no rectangle of even height at least $4$ and odd width can be partitioned into rectangular cell loops. Assuming this claim, either the right strip, which has height $10$ and odd width at least $1$, or the interior rectangle, which has height $8$ and odd width when $k\ge5$ (and width $1$ when $k=3$), is not loop-partitionable. This contradicts the assumption that the original grid was partitioned into loops. Thus $k$ cannot be odd.

To prove the claim, suppose an $m\times w$ rectangle with $m\ge4$ even and $w$ odd can be partitioned into loops. Consider the loop containing its top-left corner. If this loop spans the full width $w$, then it has height at least $3$ and encloses an interior rectangle of width $w-2$, which is still odd, and height at least $1$. If the height is $3$, the interior has height $1$ and cannot be tiled by loops; if the height is larger, we obtain a smaller even-by-odd rectangle, contradicting minimality.

If instead the corner loop spans the full height $m$ with some width $t$, then removing it leaves an $m\times(w-t)$ rectangle with $w-t$ odd. Since $t\ge2$, this reduces the odd width by at least $2$ while preserving even height at least $4$. Repeating this process eventually produces an $m\times1$ or $m\times3$ rectangle, neither of which can be partitioned into loops, since every loop has width at least $2$ and any attempt creates an interior strip of width $1$.

This contradiction proves the claim and hence the lemma.

~Gray_Wolf

Solution 2

After building some intuition for this problem, we can see that all loops must be either "vertical" (with $a\geq b$ or "horizontal" (with $b\geq a$), except for the case where 5 loops are all nested within each other (which has both). We may do this using an area argument: [it's hard to state but just trust me. placeholder box] Each loop may complete 2 rows or 2 columns at maximum. Therefore we may consider the vertical case.

We may then pose an equivalent problem: Let us represent each loop as a pair of parentheses. For example, ()()()()() represents 5 loops such that none are nested, ((((())))) represents all the loops being nested. Then, this is the same as the 5th Catalan number which is $42$. The answer is therefore $42\cdot2-1=083$

Additionally, we can see that my SCHLONG is ABSOLUTELY MASSIVE, adding another 2 to the answer, therefore the answer is 85. thank you for listening to my ted talk

~SilverRush and founder of aops

Engineer's induction doesn't work

If one solves the same problem but with $1$ cell loop and a $2 \times 2$ grid, $2$ cell loops and a $4 \times 4$ grid, $3$ cell loops and a $6 \times 6$ grid, and $4$ cell loops and a $8 \times 8$ grid, one obtains the answers $1$, $3$, $9$, and $27$. But the answer to the actual AIME problem is not $81$.