Un juego de adivinar un número elegido

Question

Tu oponente (honesto) elige un número al azar del 1 al 13, ambos inclusive. Tienes que adivinar el número, y ganas si la adivinación es correcta. Si no lo es, tu oponente reduce el número elegido en uno o lo aumenta en 1, y vuelves a adivinar.

La pregunta es: ¿cuál es el número mínimo de intentos necesarios para garantizarte una victoria?

No soy capaz de entender el problema.

Además, (una nueva variante que se me acaba de ocurrir), ¿cuántos aciertos se deben permitir para un juego justo o "lo más cercano a lo justo"?

Answer 1

EDIT: No es óptimo porque no examiné bien los límites. Ver la respuesta de Marc van Leeuwen para un mejor análisis en 22 pasos.

Mi estrategia sería barrer $G = \{g_i\} = \{1, 2, ..., 13, 1, 2, ..., 12\}$ , requiriendo un total de 25 pasos.

¿Por qué debería funcionar?

Dejemos que $x_1$ sea el número inicial elegido por el adversario. Tenga en cuenta que cada movimiento cambia el número en exactamente $\pm 1$ . Así, $x_{2i} - x_1$ es impar y $x_{2i+1} - x_1$ es incluso para $i \in \mathbb{N}$ .

Caso 1: $x_1$ es impar. Entonces el primer barrido de $g_1$ a $g_{13}$ tendrá éxito.

Tenga en cuenta que como $x_1$ es impar, $x_{2i}$ debe ser par y $x_{2i+1}$ debe ser impar. También hay que tener en cuenta que en el primer barrido, $g_{2i}$ es par y $g_{2i+1}$ es impar. Así, $2|(x_i - g_i)$ para todos $1\le i \le 13$ .

Supongamos que $x_i < g_i$ . Entonces, en algún momento, $x_i = g_i - 1$ (ya que estamos empezando el barrido en $g_1 = 1$ ). Sin embargo, eso es una contradicción porque demostramos que la diferencia entre $x_i$ y $g_i$ es siempre uniforme. Por lo tanto, $x_i \ge g_i$ para $1 \le i \le 13$ lo que implica que debemos tener éxito en el primer barrido si $x_1$ es impar.

Caso 2: $x_1$ es par. Entonces el primer barrido no tendrá éxito. Sin embargo, el segundo barrido $g_{14}$ a $g_{25}$ voluntad, porque si $x_1$ es par, entonces $x_{14}$ debe ser impar. Por lo tanto, un argumento idéntico al dado anteriormente para el caso 1 es válido. No necesitamos comprobar $13$ esta vez porque $x_i$ tendría que ser $12$ el paso anterior, que ya estamos comprobando. (En sentido estricto, la comprobación $13$ tampoco es necesario en la primera ronda por la misma razón, pero necesitamos desperdiciar un movimiento antes de comenzar el segundo barrido)

Por lo tanto, se necesitan como máximo 25 movimientos.

Dado que se necesitan dos barridos para garantizar, 12 movimientos es un juego "lo más cercano a lo justo", ya que eso es lo que se requiere para un solo barrido, haciendo que el resultado dependa de si la elección inicial fue par o impar.

Answer 2

La estrategia óptima para $n=13$ impar es intentar $2,\ldots,n-1=12$ primero, que atrapará al oponente si y sólo si comenzó en un número par; si el oponente aún no es atrapado, uno está seguro de que comenzó en impar y ahora está (después de $n-2=11$ movimientos) en un número par (en particular no en $n=13$ ), e intentar $12,11,\ldots2$ es seguro que la atrapará, para un total de $2*11=2n-4=22$ intentos.

El mismo esquema funciona para $n=12$ incluso: intentar $2,\ldots,n-1=11$ primero, que atrapará al oponente si y sólo si comenzó en un número par; si todavía no lo atrapó, uno está seguro de que lo está ahora (después de $n-2$ movimientos) de nuevo un número impar (en particular no en $n=12$ ), e intentar $n-1=11,\ldots2$ está seguro de atrapar al oponente, para un total de $2*10=2n-4=20$ intentos.

Añadido: Aquí está el análisis completo del juego. Claramente se divide en dos partidas paralelas, una en la que el oponente empieza impar y otra en la que empieza Parejo. El oponente elige un juego al principio y tiene que atenerse a él, pero no sabemos cuál es, así que tenemos que reducir el número de posiciones potenciales restantes en ambos juegos a $0$ . En cada movimiento eliminamos una de las posibles posiciones, pero entonces las restantes posiciones posibles se sustituyen por el conjunto de todas sus vecinas; esto también ocurre en la partida en la que no jugamos. Si se pasa de una partida a otra (jugando la partida $A$ Entonces, al menos una vez el juego $B$ entonces de nuevo juego $A$ ), entonces el antes del segundo movimiento en el juego $A$ el número de posiciones potenciales en el juego $A$ (si el primer movimiento no lo redujo a $0$ ) ha vuelto a crecer hasta alcanzar al menos el mismo número que tenía antes de la anterior mudanza en $A$ Por lo tanto, una estrategia óptima debería evitar este tipo de cambios. Por lo tanto, debemos elegir un juego para jugar primero, terminar ese juego por completo, y luego comenzar a jugar en el otro juego.

Centrándonos ahora en un solo juego (por lo que se conoce la paridad de las posibilidades en cada momento), se puede comprobar que el sólo tipo de movimiento que realmente reduce el número de posibilidades restantes es cuando esas posibilidades forman un "intervalo" (en el sentido de los números de una paridad dada en un intervalo dado) que contiene uno de los extremos del conjunto total: al jugar el otro extremo del intervalo, las posibilidades se reducen a las de la paridad opuesta entre los extremos del intervalo original. (La afirmación "sólo" no es del todo cierta: (1) siempre que las posibilidades se hayan reducido a un único elemento, se puede tocar éste para reducirlo a $0$ y (2) si $n$ es impar y todos los números Impares siguen siendo posibles, su número está destinado a disminuir independientemente de nuestro movimiento. Sin embargo, estas posibilidades son marginales y no afectan a nuestro análisis). Después de una jugada así no se puede volver a reducir el número en la siguiente jugada, pero jugando de nuevo en el mismo extremo del (nuevo) intervalo se puede al menos preparar su disminución en la jugada siguiente.

Hay cuatro tipos de juegos, según la paridad de $n$ y de las posibilidades iniciales. Las dos variantes con $n$ pares son imágenes especulares izquierda-derecha, y el "par inicial" se puede ganar en $n-2$ se mueve jugando $2,3,\ldots,n-1$ . Así que puede el juego "inicial incluso" con $n$ impar. El juego con $n$ impar y posibilidades iniciales impar, sin embargo, necesita $n-1$ jugadas: la primera jugada no hace ninguna diferencia, y luego queda el juego "inicial parejo". Puesto que podemos elegir en qué juego jugar primero, y puesto que para $n$ impar el juego "inicial parejo" requiere un número impar de movimientos, podemos jugar eso primero y haber transformado el otro juego en otro "inicial parejo", así que al final todavía podemos ganar en $2(n-2)$ movimientos, independientemente de la paridad de $n$ .

Answer 3

Una forma de garantizar una victoria es adivinar el 13 dos veces, luego el 12 dos veces, luego el 11 dos veces, etc.

EDIT: No del todo. Volvemos a la mesa de dibujo.

Answer 4

Aquí está mi intento, pero no estoy seguro de que esto es la solución óptima con menos conjeturas, sin embargo. Para $n=13$ impar.

En primer lugar, vamos a suponer que tienes una "información extra" de que el número es par. Entonces, primero adivinas $n-1$ . Si ese no es el número, entonces sabes que el número3 es par y ni mayor que $n-3$ . Esto significa que el siguiente número será impar, y no mayor que $n-2$ . Así que adivina $n-2$ . Si ese no es el número, significa que el número es impar y no mayor que $n-4$ . Así que, estás adivinando para $n-4$ siguiente, y así sucesivamente. Siguiendo así, si no adivinas el número mientras tanto, sabrás que el número es par y no mayor que $2$ . Así que, estás adivinando $2$ y tu suposición es correcta. Lo que tenemos que hacer ahora es cómo conseguir la "información extra".

Supongamos que en cada una de las siguientes adivinanzas no aciertas. Digamos que cada día adivinas un número para facilitar la comprensión. El primer día, adivinaste $2$ . El tercer día, el número será $2$ si el primer día fue $4$ . Pero esto significa que el número fue $3$ el segundo día. o, el segundo día se adivina $2$ y la tercera la adivinaste $4$ . Esto garantiza que el número del tercer día no era $2$ o $4$ . Echemos un vistazo al quinto día. Ese día, el número no puede ser $2$ y puede ser $4$ si el tercer día fuera $6$ . Pero eso significa que el número del cuarto día fue $5$ . Así que, cuarto y quinto día adivinaste $5$ y $6$ . Así que, el quinto día, el número seguramente no es $2$ , $4$ o $6$ . Seguir así, después de $n-2$ días sabrás que $n-2$ n día el número no era $2$ , $4$ , ..., $n-3$ o $n-1$ . Así que esta es la estrategia para obtener la "información extra", y después de esto se mantiene como en el primer párrafo.

Así que mi opinión es que para impar $n$ Debes adivinar (si he contado bien las suposiciones) $(n-2)+(n-2)=2n-4=2*13-4=22$ .