Juan y Pedro están escribiendo un número de 20 dígitos usando sólo 1, 2, 3, 4 y 5. Pedro quiere que el resultado sea un múltiplo de 9. ¿Podría Juan detener a Pedro?

Question

Problema: Juan y Pedro están escribiendo un número de 20 dígitos usando sólo 1, 2, 3, 4 y 5. El primer dígito lo escribe Juan, luego Pedro y así sucesivamente. Pedro quiere que el número resultante sea divisible por 9. ¿Podría Juan destruir el deseo de Pedro?

Mi intento: Si la suma de los dígitos es divisible por 9, entonces el número es divisible por 9. Así que Juan tiene que asegurarse de que la suma de los dígitos es 0, 1, 2, 3 mod 9 después de su movimiento. En otras palabras, puede colocar 1, 2 o 3.

Si Juan colocó 2, Pedro colocó 1, entonces Juan tendría sólo 1, 2, 3, 4, 5 para colocar;

Si Juan colocó 2, Pedro colocó 2, entonces Juan sólo tendría 1, 2, 3, 4 para colocar;

Si Juan colocó 2, Pedro colocó 3, entonces Juan sólo tendría que colocar 1, 2, 3, 5;

Si Juan colocó 2, Pedro colocó 4, entonces Juan sólo tendría que colocar 1, 2, 4, 5;

Si Juan colocó 2, Pedro colocó 5, entonces Juan sólo tendría que colocar 1, 3, 4, 5;

Si Juan colocó 1, Pedro colocó 1, entonces Juan sólo tendría 1, 2, 3, 4, 5 para colocar;

Si Juan colocó 1, Pedro colocó 2, entonces Juan tendría sólo 1, 2, 3, 4, 5 para colocar;

Si Juan colocó 1, Pedro colocó 3, entonces Juan tendría sólo 1, 2, 3, 4 para colocar;

Si Juan colocó 1, Pedro colocó 4, entonces Juan sólo tendría que colocar 1, 2, 3, 5;

Si Juan colocó 1, Pedro colocó 5, entonces Juan sólo tendría que colocar 1, 2, 4, 5;

Por lo tanto, parece que para Juan es mejor empezar con 1. Sin embargo, deberíamos ver una tabla de valores que Juan podría elegir para hacer restos de 1, 2 o 3 mod 9:

Si Juan coloca 1, Pedro coloca 1, entonces Juan no tendría nada que colocar;

Si Juan colocó 1, Pedro colocó 2, entonces Juan no tendría nada que colocar;

Si Juan colocó 1, Pedro colocó 3, entonces Juan no tendría nada que colocar;

Si Juan colocó 1, Pedro colocó 4, entonces Juan tendría sólo 5 para colocar;

Si Juan colocó 1, Pedro colocó 5, entonces Juan tendría sólo 4, 5 para colocar;

Si Juan colocó 2, Pedro colocó 1, entonces Juan no tendría nada que colocar;

Si Juan coloca 2, Pedro coloca 2, entonces Juan no tendría nada que colocar;

Si Juan colocó 2, Pedro colocó 3, entonces Juan tendría sólo 5 para colocar;

Si Juan colocó 2, Pedro colocó 4, entonces Juan tendría sólo 4, 5 para colocar;

Si Juan colocó 2, Pedro colocó 5, entonces Juan sólo tendría 3, 4, 5 para colocar;

Si Juan colocó 3, Pedro colocó 5, entonces Juan sólo tendría que colocar 2, 3, 4;

Si Juan colocó 3, Pedro colocó 4, entonces Juan tendría sólo 3, 4, 5 para colocar;

Si Juan colocó 3, Pedro colocó 3, entonces Juan tendría sólo 4, 5 para colocar.;

Si Juan colocó 3, Pedro colocó 2, entonces Juan tendría sólo 5 para colocar;

Si Juan colocó 3, Pedro colocó 1, entonces Juan no tendría nada que colocar;

Así que, básicamente, John debería empezar con 3, y luego actuar según la tabla. Creo que las tablas son las mismas para cada movimiento, pero la parte "Si Juan colocó x" debería cambiarse por "Si Juan colocó algo para hacer un resto de x".

Entonces, la respuesta es no, no es posible que Juan destruya el plan de Pedro para hacer un múltiplo de 9. A menos que, Pedro sea un ser humano normal.

Mis problemas con esto: No creo que sea muy elegante usar tablas en las soluciones, ¿alguien podría ayudarme con eso? Además, ¿estoy realmente en lo cierto?

Answer 1

La forma segura de analizar este tipo de partidos es trabajar hacia atrás desde el final del juego. Como se observa, sólo importa la suma de los dígitos módulo 9, por lo que podemos simplemente enumerar cuáles de las 9 posiciones son ganadoras para cada jugador en cada paso de la partida.

Con 0 dígitos para elegir, $\{1,2,3,4,5,6,7,8\}$ ganar para John y $\{0\}$ gana para Peter.

En el paso anterior, Peter ganará si la posición es una que puede alcanzar $0$ de. De lo contrario, John gana.

A falta de un dígito para elegir, $\{4,5,6,7,8\}$ ganar para Peter, y $\{0,1,2,3\}$ ganar para John.

En el paso anterior, Juan ganará si la posición es una desde la que puede llegar a 0, 1, 2 o 3. En caso contrario, ganará Pedro.

A falta de dos dígitos para elegir, $\{0,1,2,4,5,6,7,8\}$ ganar para John, y $\{3\}$ gana para Peter.

Pero esta es esencialmente la misma situación que la de $0$ dígitos para elegir, ya que hay un único residuo que ganará para Pedro, y todo lo demás gana para Juan. Así que el análisis se repetirá cada dos turnos -sólo que en un punto diferente del ciclo de residuos posibles- y podemos avanzar rápidamente:

Con 4 dígitos para elegir, $\{6\}$ gana para Pedro y todo lo demás va para Juan.

Con 6 dígitos para elegir, $\{0\}$ gana para Pedro y todo lo demás gana para Juan.

Y en general, con $2n$ dígitos que quedan para elegir, Peter puede forzar una victoria si la posición es equivalente a $3n$ modulo $9$ .

Así, a falta de 20 dígitos para elegir, Pedro ganará si la posición es equivalente a $30$ modulo $9$ . Pero la posición inicial real es $0$ (ya que aún no se han elegido los dígitos), y $0\not\equiv 30\pmod 9$ . Así que John tiene una estrategia ganadora .

---

En particular, este análisis nos permite construir una estrategia ganadora fácil para Juan:

Escoge $1$ como primer dígito. Para cada uno de los siguientes nueve dígitos que John puede elegir, escoge $6-a$ donde $a$ es el dígito que Peter acaba de elegir. Entonces, cuando Peter está a punto de hacer su último pick, la suma de los dígitos será $1+9\times 6$ y no hay manera de que Peter lo convierta en un múltiplo de $9$ añadiendo algo entre $1$ y $5$ .

Answer 2

John tiene una estrategia ganadora como la siguiente:

Siempre pone $2$ primero. Entonces, si Pedro pone su dígito como $n$ A continuación, pone $6-n$ .

Siguiendo este camino hasta el $17$ donde encontramos la suma de todos los dígitos son $50$ .

Aquí hay planes de acción para Juan: 1) Si Pedro pone un número menor que $4$ , digamos que $n$ , entonces Juan pone $4-n$ para que la suma de los dígitos sea $54$ y Peter tiene que añadir otro número que sea al menos $9$ , que no puede.

2) Si Pedro pone cuatro o cinco, Juan pone $1$ . Así, la suma de dígitos es $55$ ou $56$ que no puede ser completado por Pedro con los dígitos que tiene, ya que necesita al menos un $7$ .

Ejemplo: Juan empieza por 2: $2$ .

A continuación, Peter pone $4$ Así que John pone $2$ : $242$ .

Pedro pone $5$ Así que John pone $1$ : $24251$ .

Pedro pone $3$ , por lo que Juan pone $3$ : $2425133$ .

Pedro pone $3$ , por lo que Juan pone $3$ : $242513333$ .

Pedro pone $4$ , por lo que Juan pone $2$ : $24251333342$ .

Pedro pone $1$ Así que John pone $5$ : $2425133334215$ .

Pedro pone $2$ Así que John pone $4$ : $242513333421524$ .

Pedro pone $1$ Así que John pone $5$ : $24251333342152415$ .

Ahora hay $17$ dígitos, que suman $50$ . Supongamos que Pedro pone un $1$ , entonces Juan pone $4-1=3$ Así que entonces: $24251333342152415$ . Lo que sea que Peter añada a esto, no puede conseguir un múltiplo de $9$ ¡!

Por lo tanto, es Juan con la estrategia ganadora.

Si no te convence, ¡juguemos!