2026 AIME I Problem 15

Attempt Problem 15 of the 2026 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2026 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

15.

Let a,a, b,b, and nn be positive integers with both aa and bb greater than or equal to 22 and less than or equal to 2n.2n. Define an a×ba \times b cell loop in a 2n×2n2n \times 2n grid of cells to be the 2a+2b42a + 2b - 4 cells that surround an (a2)×(b2)(a-2) \times (b-2) (possibly empty) rectangle of cells in the grid. For example, the following diagram shows a way to partition a 6×66 \times 6 grid of cells into 44 cell loops.

Find the number of ways to partition a 10×1010 \times 10 grid of cells into 55 cell loops so that every cell of the grid belongs to exactly one cell loop.

Answer: 83
Concepts:tilingextremal argumentrecursive counting
Difficulty rating: 3700
Solution:

Since the five loops cover (2(ai+bi)4)=100\sum \left(2(a_i + b_i) - 4\right) = 100 cells, (ai+bi)=60.\sum (a_i + b_i) = 60. Every loop has an even number of cells, so no odd-by-odd rectangle can be exactly filled by loops; and filling a rectangle whose shortest even side is ee requires at least e2\frac{e}{2} loops, since peeling off an outermost loop shrinks that side by exactly 22 while splitting a rectangle into smaller ones only adds up such requirements. Now consider the outermost loops of a partition (those whose rectangles lie inside no other loop's rectangle): their rectangles tile the 10×1010 \times 10 square. If outermost rectangle RiR_i has shortest even side ei,e_i, it uses niei2n_i \ge \frac{e_i}{2} loops and covers at most 10ei10\,e_i cells. Summing over the tiling, 10010ei20ni=100,100 \le \sum 10\,e_i \le 20 \sum n_i = 100, so equality holds throughout: each RiR_i spans the full 1010 in one direction, has even width ei,e_i, and is filled with exactly ei2\frac{e_i}{2} loops. Two full-length slabs in different directions would overlap, so the outermost rectangles are the whole square or parallel slabs, and the same equality argument repeats inside every loop's inner rectangle.

Let s(w)s(w) be the number of ways to fill a full-height slab of even width ww with w2\frac{w}{2} loops, subject to the slab's own 10×w10 \times w boundary being one outermost loop. (A split into smaller outermost slabs is counted later instead.) A width-22 slab is a single loop: s(2)=1.s(2) = 1. A width-44 slab is a 10×410 \times 4 loop around an 8×28 \times 2 loop: s(4)=1.s(4) = 1. A width-66 slab is a 10×610 \times 6 loop around an 8×48 \times 4 region holding two loops — either nested (8×48 \times 4 around 6×26 \times 2) or two 8×28 \times 2 slabs — so s(6)=2.s(6) = 2. A width-88 slab surrounds an 8×68 \times 6 region holding three loops: an 8×68 \times 6 loop around a 6×46 \times 4 region with two loops (22 ways as before), or full-height strips of widths 2+2+22 + 2 + 2 (11 way), or widths 2+42 + 4 in two orders (22 ways), so s(8)=5.s(8) = 5. The same recursion counts the full square: a 10×1010 \times 10 loop around an 8×88 \times 8 region with four loops, where the 4×4,4 \times 4, 6×6,6 \times 6, and 8×88 \times 8 regions admit 3,3, then 3+3+3=9,3 + 3 + 3 = 9, then 9+9+9=279 + 9 + 9 = 27 fillings (single nested loop, vertical strips, or horizontal strips at each stage).

Finally, tally the outermost structures. The single 10×1010 \times 10 rectangle gives 2727 partitions. For parallel slabs, the widths form a composition of 1010 into even parts with at least two parts, and orientations (vertical or horizontal) double the count: (2,2,2,2,2)(2,2,2,2,2) gives 1;1; (4,2,2,2)(4,2,2,2) in 44 orders gives 4;4; (4,4,2)(4,4,2) in 33 orders gives 3;3; (6,2,2)(6,2,2) in 33 orders gives 32=6;3 \cdot 2 = 6; (6,4)(6,4) in 22 orders gives 22=4;2 \cdot 2 = 4; and (8,2)(8,2) in 22 orders gives 25=10,2 \cdot 5 = 10, for 2828 per orientation. The total is 27+228=83.27 + 2 \cdot 28 = 83.

← Problem 14#14
Full Exam

Problem 15 in Other Years