¿Cuál es la cantidad mínima de movimientos que se necesitan para terminar este juego?

Question

Se trata de un pregunta de seguimiento de esta entrada que pregunté. La pregunta anterior fue respondida por Barry Cipra, y se me sugirió crear esta pregunta de seguimiento.

El juego:

Dos jugadores han $n$ tarjetas etiquetadas de $1$ a $n$ . Cada uno coge una carta del mazo al azar y se la pone en la frente. Los jugadores no pueden ver su propia carta, pero sí la de los demás.

Ahora los jugadores se turnan para adivinar si son "más altos" o "más bajos" que el otro jugador.

El objetivo es que ambos jugadores trabajen juntos para descifrar cada una de sus respectivas posiciones. El juego termina cuando uno (no los dos) de los jugadores decide que está seguro de su posición. El jugador no terminará el juego a menos que esté 100% seguro de que tiene razón.

Otras condiciones previas son:

• Ambos jugadores saben $n$ .
• Ambos jugadores son lógicos perfectos con memoria infinita y ambos saben también que el otro jugador es un lógico perfecto.
• Los jugadores saben que siempre elegirán la opción más probable, y elegirán al azar si ambas opciones tienen las mismas probabilidades de suceder. Pero no puede haber otra estrategia predeterminada.

En resumen, quiero encontrar una función, $M(a, b, n)$ que devuelve la cantidad mínima de movimientos que tardaría el jugador A con la carta $a$ y el jugador B con la carta $b$ para terminar el juego, dado $n$ la carta máxima de la baraja.

Por la respuesta detallada de Bram28, ya se sabe que para $n < 11$ las partidas nunca pasarán de 3 movimientos.

Actualización :

Vale, lo he pensado un poco más. En realidad, resulta que la mayoría de los juegos terminan muy rápidamente . Por simetría, siempre podemos elegir A para ir primero y para B una carta que sea $b \leq n/2$ incluso $n$ .

• Turno 1: A dirá "más alto".
• Turno 2, Caso 1: Ahora B sabe que debe ser menor que $n/2$ . Si la carta de A es mayor que $n/2$ entonces B dice "abajo" y el juego termina en 2 turnos.
• Turno 2, Caso 2: En caso contrario, si A es menor o igual que $n/2$ B tendrá que decir "más alto" o "más bajo", según corresponda, pero no puede concluir su posición.
• Turno 3: Si el juego llega al turno 3, entonces A sabe que está en el Caso 2, y puede concluir algo de la respuesta de B en el turno 2. Ahora tanto A como B saben que son menores que $n/2$ pero no podemos estar seguros de su posición relativa, así que, hemos vuelto al principio del juego, excepto con $n/2$ tarjetas.

La condición para que la partida termine en el turno 2 es que B sea menor que $n/2$ y A sea mayor que $n/2$ (o al revés), que se trata de un medio de la posible elección de cartas para A y B.

También podemos aplicar esto recursivamente, para encontrar un límite en los mazos con $ n = 2^m$ para el que la cantidad máxima de movimientos que se pueden realizar es $2\log_2 n = 2m$ . Para los números pares en general, los 2 jugadores pueden "eliminar" los factores de 2 hasta quedarse con un número impar, lo cual es complicado ya que tenemos el término medio, donde A no puede hacer ninguna inferencia sobre su posición en el primer turno.

Gracias por leerme.

Answer 1

Además de mi largo análisis anterior obtuve algunos resultados más:

Para $n=13$ y $n=14$ ¡todavía son sólo 3 movimientos! Si después de dos movimientos la partida aún no ha terminado, entonces si llegamos a $HH$ sabemos que $A$ es mirar un número (es decir $B$ tiene el número) de $2-7$ mientras que $B$ debe estar mirando un número (es decir $A$ tiene el número) $3$ o $4$ . Por lo tanto, si $A$ ve $2$ o $3$ , $A$ sabe que su propio número es mayor que $B$ y cuando $A$ ve en cualquier lugar de $4-7$ , $A$ sabe que su número es inferior a $B$ por lo que en todos los casos $A$ puede acabar con el partido. Lo mismo ocurre con $HL$ , $LH$ y $LL$ .

Para $n=15$ finalmente necesitamos $4$ se mueve: Si después de dos movimientos llegamos a $HL$ eso significa $A$ está estudiando $2-8$ y $B$ está estudiando $5-7$ . Por lo tanto, si $A$ ve cualquier cosa menos $6$ , $A$ puede terminar el juego, pero si $A$ ve $6$ entonces $A$ tiene que decir algo ... después de lo cual $B$ sabe que $A$ está mirando a un $6$ y puede terminar el juego en el turno $4$

OK, así que parece que va a ser una función logarítmica: Con $n=2$ se necesita $1$ mover, pero para $n=3$ tarda un máximo de $2$ movimientos: si $A$ ve una $2$ , $A$ tiene que decir algo, y $B$ terminará la partida en el siguiente movimiento, sabiendo que $A$ está mirando a un $2$ (si no, $A$ habría terminado el partido inmediatamente). Con $n=4,5,6$ el juego aún tarda un máximo de $2$ movimientos, pero subimos a $3$ movimientos para $n=7$ . Y ahora vemos que para $n=14$ todavía tenemos un máximo de $3$ se mueve, pero entonces para $n=15$ pasamos a $4$ . En otras palabras, la hipótesis es que se necesitará un máximo de

$$\lfloor log_2 (n+1) \rfloor$$

mueve para terminar el juego.

OK, a la prueba ....

Lo hacemos por inducción, por supuesto. Demostremos que para cualquier $n$ donde $2^m-1 \le n \le 2^{m+1}-2$ el juego con $n$ tarjetas tarda un máximo de $m$ se mueve.

Base: ya verificado hasta $n=15$

Paso:

Digamos que tenemos $n$ tarjetas. Está claro que para llegar al máximo número de juegos, $A$ y $B$ necesitan tener sus dos cartas en la mitad inferior (que incluye la carta del medio si $n$ es impar), o ambas en la mitad superior (que de nuevo incluye la carta central si $n$ es impar), o de lo contrario el juego termina muy rápidamente. Así que, por simetría, podemos suponer que ambos están en la mitad inferior y que $A$ dice "superior". Esto significa que $B$ no tiene tarjeta $1$ o $A$ habría acabado con el partido de inmediato. Por lo tanto, en efecto, ahora estamos en una situación en la que tenemos cartas $2$ a través de $\lfloor (n+1)/2 \rfloor$ todavía en juego.

El límite inferior es $2$ porque el juego no terminó todavía después de $A$ turno. Por supuesto, si $B$ ve una $1$ , $B$ terminaría el juego allí mismo también, pero eso es simplemente la contrapartida de $A$ poder terminar el juego al ver la carta más baja (o más alta).

El límite superior es $\lfloor (n+1)/2 \rfloor$ porque si $n$ es par, entonces el límite superior de la mitad inferior de las cartas es exactamente $n/2$ que es igual a $\lfloor (n+1)/2 \rfloor$ y si $n$ es impar, entonces el límite superior debe incluir la carta del medio, que es $(n+1)/2$ . Y de nuevo, mientras $B$ podría terminar el juego inmediatamente al ver la carta del medio después de $A$ no debemos descartar ésta. Más bien: $B$ ver la carta del medio sería la contrapartida de $A$ ver $n$ a su vez $1$ y al igual que $A$ podría terminar el juego al ver $n$ , $B$ puede terminar el juego al ver $(n+1)/2$ .

OK, así que si el juego no termina en $A$ y estamos en un juego de "turnos máximos", entonces efectivamente hemos acabado con un juego con cartas $2$ a través de $\lfloor (n+1)/2 \rfloor$ o, lo que es lo mismo, un juego con cartas $1$ a través de $\lfloor (n-1)/2 \rfloor$ .

Ahora, con un poco de matemática básica se puede verificar que si $2^m-1 \le n \le 2^{m+1}-2$ entonces $2^{m-1}-1 \le \lfloor (n-1)/2 \rfloor \le 2^{m}-2$ :

Para el límite inferior $n=2^m-1$ obtenemos que :

$$\lfloor (n-1)/2 \rfloor = \lfloor (2^m-1-1)/2 \rfloor = \lfloor (2^m-2)/2 \rfloor = 2^{m-1}-1$$

mientras que para el límite superior $n=2^{m+1}-2$ que tenemos:

$$\lfloor (n-1)/2 \rfloor = \lfloor (2^{m+1}-2-1)/2 \rfloor = \lfloor 2^m-1-1/2 \rfloor = 2^m-2$$

y por lo tanto por la hipótesis inductiva tomará un máximo de $m-1$ movimientos para terminar este juego que, combinado con $A$ significa que el juego con $2^m-1 \le n < 2^{m+1}-1$ tarjetas tomarán efectivamente un máximo de $m$ se mueve hasta el final.