2026 AIME I 第 15 题

先试着解答 2026 AIME I 第 15 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2026 AIME I 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

15.

aabbnn 为正整数,其中 aabb 都大于或等于 22,且小于或等于 2n2n。在一个 2n×2n2n \times 2n 的方格网中,定义一个 a×ba \times b格子环为围绕一个 (a2)×(b2)(a-2) \times (b-2)(可能为空)矩形的 2a+2b42a + 2b - 4 个格子。例如,下图展示了一种把 6×66 \times 6 方格网分成 44 个格子环的方法。

求把一个 10×1010 \times 10 方格网分成 55 个格子环的方法数,使得方格网中的每个格子都恰好属于一个格子环。

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.

答案:83
知识点:铺砖极端原理递推计数
难度评级:3700
解答:

因为五个环覆盖了 (2(ai+bi)4)=100\sum \left(2(a_i + b_i) - 4\right) = 100 个格子,所以 (ai+bi)=60\sum (a_i + b_i) = 60。每个环含偶数个格子,因此奇数乘奇数的矩形不能被环完全填满; 并且填充一个最短偶数边为 ee 的矩形至少需要 e2\frac{e}{2} 个环,因为剥去一个最外层环会使那条边正好缩短 22,而把矩形分成较小矩形只会把这些需求相加。现在考虑一个分割中的最外层环 (也就是其矩形不位于任何其他环的矩形内部的环):它们的矩形铺满 10×1010 \times 10 正方形。 若最外层矩形 RiR_i 的最短偶数边为 eie_i,它使用 niei2n_i \ge \frac{e_i}{2} 个环, 且最多覆盖 10ei10\,e_i 个格子。对这个铺法求和, 10010ei20ni=100100 \le \sum 10\,e_i \le 20 \sum n_i = 100,所以处处取等:每个 RiR_i 都在一个方向上跨满长度 1010,宽度为偶数 eie_i,并且恰好由 ei2\frac{e_i}{2} 个环填充。 两个不同方向的全长板条会相交,所以最外层矩形要么是整个正方形,要么是平行板条;同样的等号论证可在每个环的内部矩形中重复。

s(w)s(w) 为填充一条全高、偶数宽度为 ww 的板条的方法数,其中使用 w2\frac{w}{2} 个环,并要求板条自身的 10×w10 \times w 边界是一个最外层环。 宽度 22 的板条是一个单环:s(2)=1s(2) = 1。宽度 44 的板条是一个 10×410 \times 4 环围住一个 8×28 \times 2 环:s(4)=1s(4) = 1。宽度 66 的板条是一个 10×610 \times 6 环,围住一个 8×48 \times 4 区域,内部有两个环:要么嵌套 (8×48 \times 4 围住 6×26 \times 2),要么是两条 8×28 \times 2 板条,所以 s(6)=2s(6) = 2。宽度 88 的板条围住一个 8×68 \times 6 区域,内部有三个环: 一个 8×68 \times 6 环围住一个含两个环的 6×46 \times 4 区域(如前有 22 种); 或全高板条宽度为 2+2+22 + 2 + 211 种);或宽度为 2+42 + 4 的两种顺序 (22 种),所以 s(8)=5s(8) = 5。同样的递推计数整个正方形:一个 10×1010 \times 10 环围住一个含四个环的 8×88 \times 8 区域,其中 4×44 \times 46×66 \times 6, 和 8×88 \times 8 区域分别有 33,再有 3+3+3=93 + 3 + 3 = 9,再有 9+9+9=279 + 9 + 9 = 27 种填法(每一步为单个嵌套环、竖直板条或水平板条)。

最后统计最外层结构。单个 10×1010 \times 10 矩形给出 2727 种分割。若为平行板条, 其宽度构成 1010 的偶数部分有序拆分,且至少有两部分,并且方向(竖直或水平)使计数翻倍: (2,2,2,2,2)(2,2,2,2,2) 给出 11(4,2,2,2)(4,2,2,2)44 种顺序给出 44(4,4,2)(4,4,2)33 种顺序给出 33(6,2,2)(6,2,2)33 种顺序给出 32=63 \cdot 2 = 6(6,4)(6,4)22 种顺序给出 22=42 \cdot 2 = 4(8,2)(8,2)22 种顺序给出 25=102 \cdot 5 = 10,每个方向共 2828 种。 总数为 27+228=8327 + 2 \cdot 28 = 83

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.

← 第 14 题#14
完整试卷

其他年份的第 15 题