Dado un cubo. Una hormiga se coloca en una esquina y no puede moverse. Una araña comienza desde la esquina opuesta y puede moverse a lo largo de los bordes del cubo en cualquier dirección (x, y, z) con probabilidad 1/3. ¿Cuál es el número esperado de pasos para que esta araña llegue a la hormiga?

Answer 1

Este problema es altamente simétrico, por lo que solo hay cuatro posiciones distinguibles:

[matemáticas] A [/ matemáticas]: vértice opuesto (1)

[matemática] B [/ matemática]: adyacente al vértice opuesto (3)

[matemática] C [/ matemática]: adyacente al vértice de la hormiga (3)

[matemáticas] D [/ matemáticas]: vértice de hormiga (1)

Es mucho más fácil trabajar con números naturales, así que lo que siempre hago es lo siguiente: considere que todas las caminatas posibles ocurren simultáneamente, encuentre la cantidad de caminatas que satisfagan sus condiciones y divida esa cantidad entre la cantidad total de caminatas posibles.

Después de que [math] t [/ math] se mueve, el número total de caminatas es claramente [math] 3 ^ {t} [/ math]. Sea [matemática] m \ izquierda (t \ derecha) [/ matemática] el número de caminatas que no han pasado por [matemática] D [/ matemática] hasta ahora, entonces la probabilidad de que la araña ya haya estado en [matemática] D [/ math] viene dado por [math] 1- \ frac {m \ left (t \ right)} {3 ^ {t}} [/ math].

Para encontrar una expresión para m [matemática] \ izquierda (t \ derecha) [/ matemática], considere una gráfica con 7 vértices (1 [matemática] A [/ matemática], 3 [matemática] B [/ matemática] y 3 [matemáticas] C [/ matemáticas]). El vértice [matemático] A [/ matemático] está conectado a los vértices [matemático] B [/ matemático], cada vértice [matemático] B [/ matemático] está conectado al [matemático] A [/ matemático] – vértices y 2 [matemáticas] C [/ matemáticas] -vertices, y cada [matemáticas] C [/ matemáticas] -vertex está conectado a 2 [matemáticas] B [/ matemáticas] -vertices. No estamos considerando el vértice [matemático] D [/ matemático], porque las caminatas que han pasado por [matemático] D [/ matemático] no pertenecen a [matemático] m \ left (t \ right) [/ math ] nunca más. No es difícil demostrar que cuando [matemáticas] t [/ matemáticas] es par, la araña debe estar en [matemáticas] A [/ matemáticas] o en [matemáticas] C [/ matemáticas], y cuando [matemáticas] t [ / math] es extraño, la araña debe estar en [math] B [/ math] (o eventualmente en [math] D [/ math]). Cuando [math] t [/ math] es impar, [math] m \ left (t + 1 \ right) = 3 \ cdot m \ left (t \ right) [/ math], porque la araña estará en un [ matemática] B [/ matemática] -vertex (cada uno con 3 formas posibles). Cuando [math] t [/ math] es par, [math] m \ left (t + 1 \ right) = 2 \ cdot c + 3 \ cdot a [/ math], donde [math] a [/ math] es la cantidad de caminatas que terminan en el vértice [matemático] A [/ matemático], y [matemática] c [/ matemática] es la cantidad de caminatas que finaliza en cualquier vértice C. Como dije antes, este problema es altamente simétrico: tenga en cuenta que (sin tener en cuenta las caminatas que ya han pasado por [matemáticas] D [/ matemáticas]), la relación entre las caminatas que terminan en una cierta [matemáticas] C [/ matemáticas ] -vertex ([math] \ frac {c} {3} [/ math]) y las caminatas que terminan en [math] A [/ math] -vertex ([math] a [/ math]) siempre es [ matemática] 2: 3 [/ matemática] cuando [matemática] t [/ matemática] es par. Eso significa que [matemáticas] c = 2a [/ matemáticas], y por lo tanto: [matemáticas] m \ izquierda (t + 1 \ derecha) = 2c + 3a = 4a + 3a = 7a = \ frac {7} {3} \ cdot m \ left (t \ right) [/ math] (cuando [math] t [/ math] es par).

Ahora podemos generar la secuencia para [math] m \ left (t \ right) [/ math], comenzando con [math] 1 [/ math] y [math] 3 [/ math]:

[matemática] 1 [/ matemática], [matemática] 3 [/ matemática], [matemática] 9 [/ matemática], [matemática] 21 [/ matemática], [matemática] 63 [/ matemática], [matemática] 147 [ / matemáticas], [matemáticas] 441 [/ matemáticas],…

Es fácil encontrar las fórmulas:

Cuando [math] t [/ math] es par, [math] m \ left (t \ right) = \ frac {9} {7} \ cdot (\ sqrt {7}) ^ {t} [/ math]

Cuando [math] t [/ math] es impar, [math] m \ left (t \ right) = 3 \ cdot (\ sqrt {7}) ^ {t-1} [/ math]

OK, volviendo a las probabilidades:

Cuando [math] t [/ math] es impar: [math] P = 1- \ frac {\ left (3 \ cdot (\ sqrt {7}) ^ {t-1} \ right)} {3 ^ {t }} = 1- \ left (\ frac {\ sqrt {7}} {3} \ right) ^ {t-1} [/ math]

Cuando [math] t [/ math] es par: [math] P = 1- \ frac {\ frac {9} {7} \ cdot (\ sqrt {7}) ^ {t}} {3 ^ {t} } = 1- \ frac {9} {7} \ cdot \ left (\ frac {\ sqrt {7}} {3} \ right) ^ {t} [/ math]

Tenga en cuenta que, para [matemáticas] t [/ matemáticas] impar, [matemáticas] P \ left (t \ right) = P \ left (t + 1 \ right) [/ math]

Esa fue la pregunta, ¿verdad?

Answer 2

Supongamos que se necesitan movimientos ‘x’ para alcanzar la hormiga cuando la araña está a un movimiento de distancia, que será desde la esquina adyacente, ‘y’ se mueve cuando la araña está a 2 bordes de distancia, es decir, desde donde la araña está a 2 bordes de distancia y ‘z’ se mueve desde el lado opuesto esquina, es decir, donde la araña está inicialmente presente.
Ahora digamos que la araña hace 1 movimientos desde la esquina opuesta. (2 aristas posibles para hacer un movimiento) Siempre alcanzará una posición que está a 2 aristas adyacentes, es decir, desde donde toma y mueve. entonces z = 1 + y.
Ahora digamos desde y, hace 1 movimiento más. En 2 casos llegará más cerca de la hormiga, es decir, en una esquina que está a 1 borde de la hormiga. Entonces y = 1+ (1/3) x + (1/3) x + (1/3) z.
De nuevo la araña hace 1 movimientos. En 1 caso alcanzará la posición final con probabilidad de 1/3 y en el resto 2 casos alcanzará una posición que está a 2 bordes de la hormiga, entonces x = 1 + (2/3) * y + (1/3) * 0.
3 ecuaciones en 3 variables … resuelve para obtener la respuesta … 🙂