Question

Cada vértice de un octágono regular se colorea independientemente de rojo o azul con igual probabilidad. La probabilidad de que el octágono se pueda entonces rotar de modo que todos los vértices azules queden en posiciones donde había habido vértices rojos es $\frac{m}{n},$ donde $m$ y $n$ son enteros positivos primos entre sí. Halla $m + n.$

Each vertex of a regular octagon is independently colored either red or blue with equal probability. The probability that the octagon can then be rotated so that all of the blue vertices end up at positions where there had been red vertices is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Respuesta

Solución:

Etiqueta los vértices $0, \ldots, 7$ y sea $B$ el conjunto azul, $b = |B|.$ La rotación por $k$ funciona exactamente cuando $(B + k) \cap B = \varnothing.$ Como $B + k$ debe caber dentro de las $8 - b$ posiciones rojas, $b \le 4.$ Sumar $|B \cap (B + k)|$ sobre las ocho rotaciones cuenta todos los pares $(i, j) \in B \times B$ una vez (vía $k = i - j$ ), un total de $b^2,$ y el término $k = 0$ aporta $b.$ Así que para $b \le 3$ las siete rotaciones no nulas comparten solo $b^2 - b \le 6$ solapamientos, y alguna rotación no tiene ninguno: las $1 + 8 + 28 + 56 = 93$ coloraciones con $b \le 3$ tienen éxito.

Para $b = 4,$ la disjunción obliga a que $B + k$ sea exactamente el complemento de $B.$ Si $k$ es impar, el ciclo $0, k, 2k, \ldots$ visita todos los vértices y debe alternar entre $B$ y su complemento, así que $B$ es el de los pares o el de los impares: $2$ conjuntos. Si $k \equiv 2 \pmod 4,$ entonces $B$ corta cada uno de los $4$ -ciclos $\{0, 2, 4, 6\}$ y $\{1, 3, 5, 7\}$ en un par antipodal: $2 \cdot 2 = 4$ conjuntos, como $\{0, 1, 4, 5\}.$ Si $k = 4,$ entonces $B$ contiene exactamente uno de cada par $\{i, i + 4\}:$ $2^4 = 16$ conjuntos. Las dos primeras familias contienen ambos miembros de algún par antipodal mientras que la tercera nunca lo hace, y los pares/impares toman ambos pares antipodales de un mismo $4$ -ciclo, así que las tres familias son disjuntas: $2 + 4 + 16 = 22$ conjuntos.

En total $93 + 22 = 115$ de las $2^8 = 256$ coloraciones funcionan, así que la probabilidad es $\frac{115}{256}$ y $m + n = 115 + 256 = 371.$

Label the vertices $0, \ldots, 7$ and let $B$ be the blue set, $b = |B|.$ Rotation by $k$ works exactly when $(B + k) \cap B = \varnothing.$ Since $B + k$ must fit inside the $8 - b$ red positions, $b \le 4.$ Summing $|B \cap (B + k)|$ over all eight rotations counts all pairs $(i, j) \in B \times B$ once (via $k = i - j$ ), a total of $b^2,$ and the $k = 0$ term contributes $b.$ So for $b \le 3$ the seven nonzero rotations share only $b^2 - b \le 6$ overlaps, and some rotation has none: all $1 + 8 + 28 + 56 = 93$ colorings with $b \le 3$ succeed.

For $b = 4,$ disjointness forces $B + k$ to be exactly the complement of $B.$ If $k$ is odd, the cycle $0, k, 2k, \ldots$ visits all vertices and must alternate between $B$ and its complement, so $B$ is the evens or the odds: $2$ sets. If $k \equiv 2 \pmod 4,$ then $B$ meets each of the $4$ -cycles $\{0, 2, 4, 6\}$ and $\{1, 3, 5, 7\}$ in an antipodal pair: $2 \cdot 2 = 4$ sets, such as $\{0, 1, 4, 5\}.$ If $k = 4,$ then $B$ contains exactly one of each pair $\{i, i + 4\}:$ $2^4 = 16$ sets. The first two families contain both members of some antipodal pair while the third never does, and the evens/odds take both their antipodal pairs from one $4$ -cycle, so the three families are disjoint: $2 + 4 + 16 = 22$ sets.

In total $93 + 22 = 115$ of the $2^8 = 256$ colorings work, so the probability is $\frac{115}{256}$ and $m + n = 115 + 256 = 371.$

2024 AIME I Problema 11

Solución:

El Problema 11 en otros años