Alice y Bob se turnan para eliminar números de una lista

Question

Alice y Bob juegan el siguiente juego. Al principio hay una lista de números.

PS

Alice comienza y quita 512 números de su elección. Bob continúa y elimina 256 números de su elección. Alice continúa y elimina 128 números de su elección, y así sucesivamente, hasta que solo quedan 2 números. Entonces Alice le paga a Bob la diferencia entre los dos números.

¿Cuáles son las estrategias óptimas para Alice y para Bob, respectivamente?

Answer 1

Dado un conjunto $X$, vamos a $A(X)$ denotar la mayor distancia entre dos puntos cualesquiera en $X$ e $B(X)$ denotar la menor distancia entre dos puntos diferentes en $X$. Para un elemento de conjunto, $A(X)=B(X)$. Empezamos con $A(X)=1024$ e $B(X)=1$. Voy a mostrar Alice puede reducir a la mitad el $A(X)$ en cada uno de sus turnos, y Bob puede doblar $B(X)$ en cada uno de sus turnos. Ya que ambos jugadores tienen 5 vueltas, esto significa que Alice puede asegurar que el resultado es, en la mayoría de los 32 y Bob puede garantizar el resultado es, al menos, 32.

Tenga en cuenta que en cada turno, el jugador se mueva es, dado un conjunto con un número impar de elementos.

Dado $X=\{x_0,\dots,x_{n/2},\dots,x_n\}$ ordenar en orden creciente, tenemos $A(X)=x_n-x_0 = (x_n - x_{n/2}) + (x_{n/2} - x_0)=A(\{x_{n/2},\dots,x_n\})+A(\{x_0,\dots,x_{n/2}\})$. Al menos uno de los dos sumandos es $\leq A(X)/2$. Por lo tanto, Alice elimina todos los de nivel superior o inferior todos los elementos en cada uno de sus turnos, dependiendo de la situación.

Dado $X=\{x_0,x_1,..,x_{n}\}$, Bob elimina $x_i$ tal que $i$ es impar. Es fácil ver que esto garantiza que $B(X)$ es al menos el doble.

Una ligera generalización: en el problema a Alice y Bob tienen el mismo número de vueltas. En general, si empezamos con $\{0,1,\dots,2^n\}$ y eliminar casi la mitad de los restantes elementos en cada vuelta, entonces la óptima rentabilidad será $2^k$ donde $k$ es el número de vueltas controladas por Bob y $n-k$ el número de vueltas controladas por Alice; los jugadores no tener que alternar.