AIME II del 2003. Problema 13

un [ __ ] comienza a caminar en el vértice de un triángulo equilátero en cada movimiento elije aleatoriamente uno de los dos vértices donde no se encuentra parado y se arrastra a lo largo del lado del triángulo ha dicho vértice dado que la probabilidad de que el [ __ ] se mueva a su vértice inicial en el décimo movimiento es m / n donde m y n son enteros positivos y primos relativos calcula m + n muy bien entonces esencialmente cuando nos dicen que me llene son primos relativos nos están diciendo que no hay factores en común entre m y n y si no hay factores en común quiere decir que está esta fracción está simplificada lo más que se puede ya estar lo más simplificada posible muy bien entonces ahora lo que lo que vamos a hacer es un dibujo para visualizar bien qué está pasando con este [ __ ] curioso porque dice que tenemos un triángulo un triángulo equilátero y que este tiene tres vértices digamos abc suponemos que hay un [ __ ] que se mueve de esta forma como indica digamos que empieza en el vértice a muy bien tenemos aquí nuestro [ __ ] que se mueve a lo largo de los lados de este triángulo para ir llegando a los otros vértices entonces la elección es al azar entonces estando en nada tiene probabilidad un medio de moverse ave y probabilidad un medio de moverse hace nos dicen la información de que me entrene es la probabilidad de que haya regresado al vértice a después de 10 movimientos así que vamos viendo qué va pasando en cada movimiento digamos con el vértice a el vértice b y el vértice c qué pasa con el primer movimiento bueno cuál es la probabilidad de que al moverse una vez quede nada bueno pues empezó en nada así que no puede volver a llegar a porque siempre se tiene que mover así que la probabilidad de llegar a es cero sin embargo cuál es la probabilidad de llegar a ver dado que estén a la probabilidad de llegar a veces un medio porque lo elige al azar lo elige a la aleatoriamente lo mismo pasa para ser verdad como esta en a pues puedes saltar hace con probabilidad un medio vamos a ver qué pasa en el segundo movimiento muy bien segundo movimiento cuando como puede llegar al vértice a al vértice a perdón en el segundo movimiento puede ser que esté en b y después elija llegará pero cuál es la probabilidad de que estén b en el paso anterior pues es un medio así que tenemos un medio de que esté en b por un medio de que elija llegar a pero no sólo eso también podemos pensar que estaba en seco y eso es y eso ocurre con probabilidad en medio y dado que estén se elija llegar a que eso tiene probabilidad de un medio entonces tenemos un medio por un medio es un cuarto más un medio por un medio que es otro cuarto son dos cuartos y esos son eso es exactamente un medio ahora bien cuál es la probabilidad de que en el segundo movimiento esté en b bueno pensemos que estaba en a entonces en el primero puede llegar a veo hace entonces realmente para que en el siguiente movimiento llegue a be sólo puede ser que parta desde ese porque si en él si en el primer movimiento llegaba ave pues no se puede quedar ahí mismo se tiene que mover así que sólo puede pasar que en el movimiento anterior esté en cee y eso ocurre con probabilidad un medio y estando en se decide a pasarse al vértice be que ocurre con probabilidad en medio y esto es un cuarto muy bien entonces lo mismo pasa para hacer verdad como no podía estar en el paso anterior ence entonces necesariamente viene del vértice b que eso ocurre con probabilidad de un medio y elegir saltar al vértice c ocurre con probabilidad de un medio y que es un cuarto entonces si nos fijamos primero en una una forma de ver que más o menos estamos haciendo las cosas bien es ver que la suma de los de las probabilidades es siempre una verdad por ejemplo aquí es cero más un medio más un medio es uno un medio más un cuarto más un cuarto también es uno muy bien pero podemos pasar a un caso más general digamos digamos que estamos en el paso n muy bien digamos que estamos en el paso n y queremos ver no podemos decir digamos que la probabilidad de que estemos en el paso en el vértice a es pda que la probabilidad de estar en el vértice pspv y la probabilidad de estar en el vértice se desperece como calculamos la probabilidad de que esté en el vértice a en el paso n 1 pues esencialmente nos dice bueno pues la probabilidad de que esté en b verdad y que decida saltar eso ocurre con probabilidad de un medio pero también puede pasar que estén se y elija con probabilidad un medio saltar y lo mismo pasa para b hay que ver la probabilidad de que estén ahí y que decida saltar ave más la probabilidad de que estén se decide a saltar ave y finalmente para la probabilidad de ese es la probabilidad de que esté en a y decía saltar hace más la probabilidad de que estén ve y decide saltar hace entonces si nos damos cuenta en todos estos es el promedio verdad es el promedio de las probabilidades de los otros vértices en el paso anterior y sí porque tenemos pdv por un medio más perece por un medio esto es lo mismo que prevé más pdc todo eso dividido entre dos y es un promedio y eso pasa para estas tres cantidades entonces con esto dicho ya va a ser mucho más sencillo calcular los siguientes los siguientes pasos vamos a seguir nuestra fila acá nuestras filas digamos estos a b vamos a ver qué pasa con el tercer movimiento bueno en el tercer movimiento tenemos que promediar para el vértice a lo que pasó en el segundo movimiento para dice que es un cuarto más un cuarto entre dos que es un cuarto verdad un cuarto y luego para ver tenemos que promediar el de a y el de c que es un medio más un cuarto estos son digamos tres cuartos verdad son dos cuartos más un cuarto son tres cuartos o lo que es lo mismo como no podemos dividirlo bien entre dos podemos pensar que son seis cuartos perdón seis octavos y al dividirlo entre dos son 33 octavos creo que lo dije bien otra vez tenemos un medio más un cuarto son tres cuartos que es lo mismo que seis octavos si lo promediamos es decir dividimos entre dos tenemos tres octavos también puedes pensar lo que la suma es perdón en si la suma de son tres cuartos y al dividirlo entre dos es como multiplicar por dos en el denominador que se dan tres octavos y realmente la probabilidad ahora en el vértice c es también tres octavos es también tres octavos porque se van son los mismos verdad la probabilidad de b y la probabilidad de c de hecho ya puedes aquí darte cuenta de algún patrón verdad al menos la probabilidad de be y la probabilidad de se van a tener que ser igualitos entonces vamos a ver qué pasa en el paso 4 el promedio de bs para que nos vea es tres octavos tres octavos de hecho también aquí puedes ver otro patrón siempre nos va a dar la probabilidad de a el promedio de b y c en el paso anterior muy bien ahora vamos a ver qué pasa con beige en este en este momento tenemos que sumar tenemos que sumar un cuarto más tres octavos un cuarto más tres octavos son dos octavos más cinco octavos y al dividir entre dos son cinco dieciseisavos cinco dieciseisavos y lo mismo para hacer cinco dieciseisavos vamos a ver qué pasa en el quinto movimiento digamos aquí la probabilidad de a es simplemente lo que hay en beijing sé que son dieciseisavos en vez vamos a ver tenemos que sumar tres octavos más cinco dieciseisavos tres octavos son seis dieciseisavos y cinco dieciseisavos son veintiuno dieciseisavos y entre dos son si se ven las cuentas creo que no verdad son seis y cinco son once 91 muy bien tenemos once dieciseisavos y al dividirlo entre dos son once 32avos tengo que cuidar mucho mis mis operaciones porque no sé por qué mi cabeza está pensando en eso lo mismo pasa para hace muy bien y entonces quizás también ya sigues viendo este tipo de patrones vamos a ver un último caso digamos para el caso de seis de seis muy bien en caso de seis se repiten estos que es 11 32 y ahora vamos a hacer el promedio de cinco dieciseisavos y 11 32 a 25 dieciseisavos son diez diez 32avos y 11 tenemos 21 32avos y dividido entre 2 tenemos 21 entre 64 y este se repite verdad entonces vamos a ver si podemos hacer algo en el séptimo paso se repiten son 21 entre 64 y vamos a ver qué tipo de patrón podemos encontrar por ejemplo para vamos a adelantarlo directamente los pasos 8 9 y 10 aunque podemos ver podemos ver que el denominador realmente sólo nos interesa saber la probabilidad de estar en verdad entonces si nos damos cuenta en el denominador son potencias de 2 verdad aquí es 2 4 8 16 32 64 y esencialmente aquí es 2 a la 12 a la 22 a la 32 a la 42 a las 5 entonces estamos elevando a la potencia anterior verdad es decir aquí estamos 2 elevando a las 5 que es el paso anterior verdad entonces por ejemplo en el paso 8 tendríamos 2 elevado a las 7 que es 2 por 64 que son 128 acá serían 256 y aquí serían 512 verdad entonces ahora al menos ya tenemos el denominador ya sabemos quién es nuestra n ahora sólo nos falta saber quién es el numerador así que piensa por ejemplo en este de aquí si nos damos cuenta esto lo podemos ver como 3 verdad 32 eso nos da 5 y 11 lo podemos ver como 5 más 6 que es el doble de este 21 lo podemos ver como 11 más el doble de 5 que es 10 así que el numerador parece ser que nuestro patrón va a ser el numerador anterior y el doble del numerador del anterior del anterior es decir de hace dos pasos muy bien entonces en este caso el doble de 11 serían 22 más 21 serían 43 ahora aquí tendríamos el doble de 21 serían 42 43 serían 85 y finalmente el doble de 43 son 86 85 171 muy bien entonces ya tenemos nuestra respuesta el numerador es 171 y 512 es el denominador pero no nos preguntan eso nos preguntan cuál es la suma de estos dos así que tenemos que calcular 512 más 171 y esto nos da 2 y 1 son 37 y 1 son 85 y 1 son 6 así que la respuesta es 600 683 ok pero bueno realmente no sé ustedes pero yo me siento un poquito incómodo porque no hemos visto realmente si la fórmula funciona así que solo solo por mera diversión vas a usar a demostrar la fórmula de que si es cierto muy bien tenemos la probabilidad de a la probabilidad de b y la probabilidad de c digamos en el paso n en el paso n es algo vimos que la probabilidad de a es un número 2 a la n muy bien 2 a la sala n creo que sn - uno muy bien dos a la n 1 ok y en vez tendremos b sobre 2 a la n 1 verdad fíjense muy bien en como lo hicimos acá como lo hicimos acá por ejemplo aquí en el 4 tenemos algo entre 2 al cubo y aquí sería entonces no es la n 1 es a la n muy bien ahí lo tenemos verdad porque aquí si es 2 a la 4 que son 16 y como en belén se son iguales entonces tendremos b entre 2 alain que pasa en el paso número n 1 entonces el promedio de a sera justamente se repetían el de verdad que es ve entre dos a la n iv en este tendremos que sumar el de a y el de cee que es a entre dos a la n menos uno más de entre dos a la n iv esto dividirlo entre dos cuanto vale esto bueno esto sería aquí podríamos multiplicar por dos y si multiplicamos por dos abajo también y nos queda dos a la n 2 a la n iv esto que es ya tenemos mismo denominador así que sólo nos queda 2 además b entre 2 por 2 a la n que es 2 a la n 1 muy bien pero en el paso n 2 en el paso n más 2 se repite lo que ya teníamos embellece que es 2a más b sobre 2 a la n 1 entonces esto verifica nuestra fórmula porque el denominador es la potencia de 2 elevado a un paso anterior que sn uno es un paso anterior de n 2 y nos dice que el numerador se calcula de la siguiente forma el doble de hace dos pasos más el numerador del paso anterior así que esto verifica nuestra fórmula que empezamos a deducir que vimos anteriormente y ya podemos quedarnos con un muy muy buen sabor de boca de nuestra respuesta que además de todo y está demostrada