Alice y Bob picking juego

Question

Alice y Bob jugar el siguiente. Hay un montón de $N$ piedras. Alice y Bob se turnan para sacar piedras de la pila. Alice siempre comienza por escoger al menos uno, pero menos de $N$ piedras. A partir de entonces, en cada turno, un jugador debe escoger al menos una piedra, pero no más piedras que fueron recogidas en el inmediatamente anterior turno. El jugador que toma la última piedra de la gana. Con lo que la propiedad de $N$, Alice ganar? Cuando va a Bob ganar?

Por extraño $N$ el resultado es bastante claro, como Alice va a empezar eligiendo una piedra y hacer cumplir la victoria. Pero entonces ¿qué?

Answer 1

Alicia gana al $N$ no es una potencia de 2.

Deje $i(N)$ ser la máxima $i$ tal que $N$ es divisble por $2^i$.

Alice estrategia: Si hay $m$ piedras a la izquierda, Alice recoge $2^{i(m)}$ piedras.

Permítanme explicar por qué esta estrategia es ganadora de Alice. Supongamos que Bob ganó mediante la selección de $b > 0$ restante de las piedras. Suponer que antes de que Alice escogió $2^j$ piedras. Por definición,$j = i(2^j + b)$. Por lo tanto $2^j + b$ es divisible por $2^j$. Por lo tanto, $b$ es también divisible por $2^j$. Esto significa que $b\ge 2^j$. Por otro lado, por las reglas del juego $b\le 2^j$. Por lo tanto,$b = 2^j$.

Pero, a continuación,$i(2^j + b) = i(2^j + 2^j) = j + 1$, contradicción.

Esta estrategia es la correcta debido a que (a) $N$ no es una potencia de 2, Alice recoge menos de $N$ piedras en la primera vuelta; (b) Alice nunca recoge más piedras de Bob en el turno anterior. En efecto, supongamos que Bob recogió $b$ piedras, antes de que Alice escogió $2^j$ piedras, y nos quedamos con $m > 0$ piedras.

Comprobaremos que $2^{i(m)} \le b$. Vamos a hacerlo mostrando que $b$ es divisble por $2^{i(m)}$.

En efecto, mediante la definición de Alice estrategia de la $j = i(2^j + b + m)$ y por las reglas de juego de la $b\le 2^j$. Vamos a mostrar que $i(m) \le j$. De hecho, si $i(m) > j$, $b$ es divisble por $2^j$, ya que tanto $2^j + b + m$ $m$ son divisble por $2^j$. Pero desde $b\le 2^j$, esto significa que $b = 2^j$. Esto contradice el hecho de que $j = i(2^j + b + m)$. En efecto, desde el $i(m) > j$,$i(2^j + b + m) = i(2^{j + 1} + m) \ge j + 1$.

Por lo tanto hemos probado que la $i(m) \le j$. Esto significa $2^j + b + m$ es divisble por $2^{i(m)}$, así como el $m$. Por lo tanto $b$ también es divisble por $2^{i(m)}$ como se requiere.

Bob gana al $N$ es una potencia de 2. Suponga que $N = 2^i$ y Alice recoge $a$ piedras. Entonces Bob puede usar Alice la estrategia descrita anteriormente. Sólo tenemos que verificar que Bob, a continuación, selecciona en la mayoría de las $a$ piedras. En efecto, supongamos que $j$ es tal que $2^i - a$ es divisible por $2^j$. A continuación, $a$ es también divisible por $2^j$ por lo tanto $2^j \le a$.

Answer 2

En primer lugar, se establece que siempre que $N = 2^m$, Bob gana. Lo haremos por inducción. Supongamos que Bob está garantizada la victoria para $2^k$ piedras. Considere la posibilidad de un juego a partir de con $2^{k+1}$ piedras. Estos pueden ser agrupados en dos grupos de $2^k$ piedras cada uno. Desde que Bob tiene una estrategia ganadora para $2^k$ piedras, Él tiene una estrategia que le permitirá jugar la jugada que termina el primer grupo de $2^k$ piedras, obligando a Alice a jugar con $2^k$ piedras restantes. Esta es una situación en la que Bob gana, por nuestra hipótesis. El caso base es fácil Si sólo hay 2 piedras, Bob gana.

Si $N \neq 2^m$, a continuación, Alicia gana . En tal caso, escribir $N = 2^k +r$ donde $2^k$ es el mayor poder de $2$, que todavía es menor que $N$. Alice se puede empezar por tomar de $r$ piedras. Ahora, ya $r$ < $2^k$, Bob no puede tomar todas las piedras que están a la izquierda. Así que Bob se ve obligado a jugar con $2^k$ piedras restantes, que Alice ahora gana (Bob es el juego de la mudanza al $2^k$ piedras son de la izquierda.)