Question

Una hormiga realiza una sucesión de movimientos sobre un cubo, donde un movimiento consiste en caminar de un vértice a un vértice adyacente a lo largo de una arista del cubo. Inicialmente la hormiga está en un vértice de la cara inferior del cubo y elige uno de los tres vértices adyacentes al que moverse como su primer movimiento. Para todos los movimientos posteriores al primero, la hormiga no regresa a su vértice anterior, sino que elige moverse a uno de los otros dos vértices adyacentes. Todas las elecciones se hacen al azar, de modo que cada uno de los movimientos posibles es igualmente probable. La probabilidad de que, tras exactamente $8$ movimientos, la hormiga esté en un vértice de la cara superior del cubo es $\frac{m}{n}$ , donde $m$ y $n$ son enteros positivos primos entre sí. Halle $m + n$ .

An ant makes a sequence of moves on a cube where a move consists of walking from one vertex to an adjacent vertex along an edge of the cube. Initially the ant is at a vertex of the bottom face of the cube and chooses one of the three adjacent vertices to move to as its first move. For all moves after the first move, the ant does not return to its previous vertex, but chooses to move to one of the other two adjacent vertices. All choices are selected at random so that each of the possible moves is equally likely. The probability that after exactly $8$ moves that ant is at a vertex of the top face on the cube is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Respuesta

Solución:

Las $3 \cdot 2^7 = 384$ sucesiones de movimientos permitidas son igualmente probables, así que contamos las que terminan en la cara superior. Clasificamos la hormiga después de cada movimiento según su cara (inferior o superior) y según si su último movimiento fue vertical: tras un movimiento vertical, las dos continuaciones permitidas son las dos aristas horizontales en el nuevo vértice, mientras que tras un movimiento horizontal, una continuación es horizontal y otra es vertical.

Sea $(B_h, B_v, T_h, T_v)$ el conteo de sucesiones que terminan en la cara inferior o superior con el último movimiento horizontal o vertical. Cada sucesión se divide en dos, siguiendo $\begin{aligned} B_h' &= B_h + 2B_v, \\ T_v' &= B_h, \\ T_h' &= T_h + 2T_v, \\ B_v' &= T_h. \end{aligned}$ Tras el movimiento $1$ , los conteos son $(2, 0, 0, 1)$ , e iterando se obtiene $(2, 0, 2, 2)$ , $(2, 2, 6, 2)$ , $(6, 6, 10, 2)$ , $(18, 10, 14, 6)$ , $(38, 14, 26, 18)$ , $(66, 26, 62, 38)$ , y tras el octavo movimiento $T_h = 62 + 76 = 138$ y $T_v = 66$ .

Así que $138 + 66 = 204$ de las $384$ sucesiones terminan en la cara superior, lo que da probabilidad $\frac{204}{384} = \frac{17}{32}$ y $m + n = 17 + 32 = 49$ .

All $3 \cdot 2^7 = 384$ allowed move sequences are equally likely, so we count those ending on the top face. Classify the ant after each move by its face (bottom or top) and by whether its last move was vertical: after a vertical move the two allowed continuations are the two horizontal edges at the new vertex, while after a horizontal move one continuation is horizontal and one is vertical.

Let $(B_h, B_v, T_h, T_v)$ count sequences ending on the bottom or top with last move horizontal or vertical. Each sequence splits into two, following $\begin{aligned} B_h' &= B_h + 2B_v, \\ T_v' &= B_h, \\ T_h' &= T_h + 2T_v, \\ B_v' &= T_h. \end{aligned}$ After move $1$ the counts are $(2, 0, 0, 1),$ and iterating gives $(2, 0, 2, 2),$ $(2, 2, 6, 2),$ $(6, 6, 10, 2),$ $(18, 10, 14, 6),$ $(38, 14, 26, 18),$ $(66, 26, 62, 38),$ and after the eighth move $T_h = 62 + 76 = 138$ and $T_v = 66.$

So $138 + 66 = 204$ of the $384$ sequences end on the top face, giving probability $\frac{204}{384} = \frac{17}{32}$ and $m + n = 17 + 32 = 49.$

2021 AIME II Problema 8

Solución:

El Problema 8 en otros años