Question

Sea $S$ el conjunto de vértices de un $24$ -ágono regular. Halla la cantidad de maneras de dibujar $12$ segmentos de igual longitud de modo que cada vértice de $S$ sea extremo de exactamente uno de los $12$ segmentos.

Let $S$ be the set of vertices of a regular $24$ -gon. Find the number of ways to draw $12$ segments of equal lengths so that each vertex in $S$ is an endpoint of exactly one of the $12$ segments.

Respuesta

Solución:

Dos cuerdas de un círculo que pasa por puntos igualmente espaciados tienen igual longitud exactamente cuando saltan el mismo número de vértices, así que los $12$ segmentos unen pares de vértices que distan exactamente $k$ para un valor común $k \in \{1, \ldots, 12\}.$ Fijado $k,$ forma el grafo sobre los $24$ vértices uniendo cada $i$ con $i \pm k \pmod{24}:$ necesitamos un emparejamiento perfecto en este grafo. Para $k \lt 12$ el grafo es una unión disjunta de $\gcd(24, k)$ ciclos de longitud $24/\gcd(24, k),$ mientras que para $k = 12$ son $12$ diámetros disjuntos.

Un ciclo de longitud par tiene exactamente $2$ emparejamientos perfectos (aristas alternas), y un ciclo de longitud impar no tiene ninguno. Así que cada $k \lt 12$ con longitud de ciclo par aporta $2^{\gcd(24, k)}:$ $k = 1, 5, 7, 11$ dan $2$ cada uno; $k = 2, 10$ dan $4$ cada uno; $k = 3, 9$ dan $8$ cada uno; $k = 4$ da $16;$ $k = 6$ da $64.$ Para $k = 8$ los ciclos tienen longitud impar $3,$ dando $0.$ Para $k = 12$ el emparejamiento está forzado: $1$ manera.

El total es $4 \cdot 2 + 2 \cdot 4 + 2 \cdot 8$ $+ 16 + 64 + 0 + 1$ $= 113.$

Two chords of a circle through equally spaced points have equal length exactly when they skip the same number of vertices, so all $12$ segments join pairs of vertices exactly $k$ apart for one common $k \in \{1, \ldots, 12\}.$ For fixed $k,$ form the graph on the $24$ vertices joining each $i$ to $i \pm k \pmod{24}:$ we need a perfect matching in this graph. For $k \lt 12$ the graph is a disjoint union of $\gcd(24, k)$ cycles of length $24/\gcd(24, k),$ while for $k = 12$ it is $12$ disjoint diameters.

A cycle of even length has exactly $2$ perfect matchings (alternate edges), and a cycle of odd length has none. So each $k \lt 12$ with even cycle length contributes $2^{\gcd(24, k)}:$ $k = 1, 5, 7, 11$ give $2$ each; $k = 2, 10$ give $4$ each; $k = 3, 9$ give $8$ each; $k = 4$ gives $16;$ $k = 6$ gives $64.$ For $k = 8$ the cycles have odd length $3,$ giving $0.$ For $k = 12$ the matching is forced: $1$ way.

The total is $4 \cdot 2 + 2 \cdot 4 + 2 \cdot 8$ $+ 16 + 64 + 0 + 1$ $= 113.$

2025 AIME II Problema 11

Solución:

El Problema 11 en otros años