Question

Sean $a,$ $b,$ y $n$ enteros positivos con $a$ y $b$ ambos mayores o iguales que $2$ y menores o iguales que $2n.$ Defina un lazo de celdas $a \times b$ en una cuadrícula de $2n \times 2n$ celdas como las $2a + 2b - 4$ celdas que rodean un rectángulo de celdas $(a-2) \times (b-2)$ (posiblemente vacío) en la cuadrícula. Por ejemplo, el siguiente diagrama muestra una manera de partir una cuadrícula de $6 \times 6$ celdas en $4$ lazos de celdas.

Halle el número de maneras de partir una cuadrícula de $10 \times 10$ celdas en $5$ lazos de celdas de modo que cada celda de la cuadrícula pertenezca a exactamente un lazo de celdas.

Let $a,$ $b,$ and $n$ be positive integers with both $a$ and $b$ greater than or equal to $2$ and less than or equal to $2n.$ Define an $a \times b$ cell loop in a $2n \times 2n$ grid of cells to be the $2a + 2b - 4$ cells that surround an $(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 \times 6$ grid of cells into $4$ cell loops.

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

Respuesta

Solución:

Como los cinco lazos cubren $\sum \left(2(a_i + b_i) - 4\right) = 100$ celdas, $\sum (a_i + b_i) = 60.$ Cada lazo tiene un número par de celdas, así que ningún rectángulo impar por impar puede llenarse exactamente con lazos; y llenar un rectángulo cuyo lado par más corto es $e$ requiere al menos $\frac{e}{2}$ lazos, ya que quitar un lazo más externo acorta ese lado exactamente en $2$ mientras que dividir un rectángulo en otros más pequeños solo suma tales requisitos. Ahora considere los lazos más externos de una partición (aquellos cuyos rectángulos no están dentro del rectángulo de ningún otro lazo): sus rectángulos teselan el cuadrado $10 \times 10$ . Si el rectángulo más externo $R_i$ tiene lado par más corto $e_i,$ usa $n_i \ge \frac{e_i}{2}$ lazos y cubre a lo sumo $10\,e_i$ celdas. Sumando sobre la teselación, $100 \le \sum 10\,e_i \le 20 \sum n_i = 100,$ así que la igualdad se cumple en todo: cada $R_i$ abarca los $10$ completos en una dirección, tiene ancho par $e_i,$ y está lleno con exactamente $\frac{e_i}{2}$ lazos. Dos losas de longitud completa en direcciones diferentes se solaparían, así que los rectángulos más externos son el cuadrado entero o losas paralelas, y el mismo argumento de igualdad se repite dentro del rectángulo interior de cada lazo.

Sea $s(w)$ el número de maneras de llenar una losa de altura completa y ancho par $w$ con $\frac{w}{2}$ lazos. Una losa de ancho $2$ es un solo lazo: $s(2) = 1.$ Una losa de ancho $4$ es un lazo $10 \times 4$ alrededor de un lazo $8 \times 2$ : $s(4) = 1.$ Una losa de ancho $6$ es un lazo $10 \times 6$ alrededor de una región $8 \times 4$ que contiene dos lazos, ya sea anidados ( $8 \times 4$ alrededor de $6 \times 2$ ) o dos losas $8 \times 2$ , así que $s(6) = 2.$ Una losa de ancho $8$ rodea una región $8 \times 6$ que contiene tres lazos: un lazo $8 \times 6$ alrededor de una región $6 \times 4$ con dos lazos ( $2$ maneras como antes), o tiras de altura completa de anchos $2 + 2 + 2$ ( $1$ manera), o anchos $2 + 4$ en dos órdenes ( $2$ maneras), así que $s(8) = 5.$ La misma recursión cuenta el cuadrado completo: un lazo $10 \times 10$ alrededor de una región $8 \times 8$ con cuatro lazos, donde las regiones $4 \times 4,$ $6 \times 6,$ y $8 \times 8$ admiten $3,$ luego $3 + 3 + 3 = 9,$ luego $9 + 9 + 9 = 27$ llenados (un solo lazo anidado, tiras verticales, o tiras horizontales en cada etapa).

Finalmente, cuente las estructuras más externas. El único rectángulo $10 \times 10$ da $27$ particiones. Para losas paralelas, los anchos forman una composición de $10$ en partes pares con al menos dos partes, y las orientaciones (vertical u horizontal) duplican el conteo: $(2,2,2,2,2)$ da $1;$ $(4,2,2,2)$ en $4$ órdenes da $4;$ $(4,4,2)$ en $3$ órdenes da $3;$ $(6,2,2)$ en $3$ órdenes da $3 \cdot 2 = 6;$ $(6,4)$ en $2$ órdenes da $2 \cdot 2 = 4;$ y $(8,2)$ en $2$ órdenes da $2 \cdot 5 = 10,$ para $28$ por orientación. El total es $27 + 2 \cdot 28 = 83.$

Since the five loops cover $\sum \left(2(a_i + b_i) - 4\right) = 100$ cells, $\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 $e$ requires at least $\frac{e}{2}$ loops, since peeling off an outermost loop shrinks that side by exactly $2$ 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 \times 10$ square. If outermost rectangle $R_i$ has shortest even side $e_i,$ it uses $n_i \ge \frac{e_i}{2}$ loops and covers at most $10\,e_i$ cells. Summing over the tiling, $100 \le \sum 10\,e_i \le 20 \sum n_i = 100,$ so equality holds throughout: each $R_i$ spans the full $10$ in one direction, has even width $e_i,$ and is filled with exactly $\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)$ be the number of ways to fill a full-height slab of even width $w$ with $\frac{w}{2}$ loops. A width- $2$ slab is a single loop: $s(2) = 1.$ A width- $4$ slab is a $10 \times 4$ loop around an $8 \times 2$ loop: $s(4) = 1.$ A width- $6$ slab is a $10 \times 6$ loop around an $8 \times 4$ region holding two loops — either nested ( $8 \times 4$ around $6 \times 2$ ) or two $8 \times 2$ slabs — so $s(6) = 2.$ A width- $8$ slab surrounds an $8 \times 6$ region holding three loops: an $8 \times 6$ loop around a $6 \times 4$ region with two loops ( $2$ ways as before), or full-height strips of widths $2 + 2 + 2$ ( $1$ way), or widths $2 + 4$ in two orders ( $2$ ways), so $s(8) = 5.$ The same recursion counts the full square: a $10 \times 10$ loop around an $8 \times 8$ region with four loops, where the $4 \times 4,$ $6 \times 6,$ and $8 \times 8$ regions admit $3,$ then $3 + 3 + 3 = 9,$ then $9 + 9 + 9 = 27$ fillings (single nested loop, vertical strips, or horizontal strips at each stage).

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

2026 AIME I Problema 15

Solución:

El Problema 15 en otros años