Dado que es un chocolate de tamaño $m\times n$. Anne y Birgitte juega un juego, con Anne de partida. En cada turno, el jugador tiene que dividir el chocolate en dos piezas rectangulares a lo largo de las líneas, y comer la parte más pequeña (o cualquier parte si ambos son iguales.) La primera persona a comer chocolate de tamaño $1\times 1$ pierde.
Que tiene una estrategia ganadora?
[Fuente: basado en Israel competencia problema]
Bueno, si la estrategia tiene que garantizar una victoria, entonces es imposible para una persona para ganar todo el tiempo.
Por ejemplo, 3 x 1 fuerzas en el primer jugador en perder. El primer salto de crear un 2 x 1 + 1 x 1 o 1 x 1 + 2 x 1, y en cualquier caso, se verían obligados a comer el 1 x 1, haciendo que Anna perder.
Sin embargo, con un 5 x 1, Birgette es forzado a perder. Anna primer movimiento tendría que ser la división de la barra en un 3 x 1 + 2 x 1, la obligó a comer el 2 x 1 pieza y dejando Birgette con el 3 x 1 pieza, que ya hemos visto a las fuerzas de la pérdida.
Los casos siguientes son las condiciones iniciales para que uno se vaya el primer paso se pierde el juego:
1)no existe k>=2 y u,v>=0, tal que n = (2k+1) * 2^u - 1, m = (2k+1) * 2^v - 1;
2)existen u,v>=0 tal que n = 2 * 2^u - 1 y m = 3 * 2^v - 1;
3)existen u,v>=0 tal que n = 3 * 2^u - 1 y m = 2 * 2^v - 1.
Si la condición inicial es diferente de la lista de arriba, a continuación, en el que va primero será el ganador.
Al completar la prueba es larga y un poco aburrida, pero me da la sensación que a través de los casos simples cuando n , m son pequeños. Las siguientes son las ideas principales.
Def:
1)Respecto ( n, m ) como el punto de la cuadrícula en el lugar, llamar a un punto malo si el que va a puño va a perder, y lo llaman un buen punto si el que va primero va a ganar;
2)Llamar a una secuencia de a[n], n>=0 una "secuencia típica", si satisface un[n+1] = 2 * a[n] + 1, y el plazo inicial de un[0] es 1 o incluso, lo que significa que uno vaya hacia atrás a partir de un[0] dejará de obtener un entero positivo.
Algunas observaciones:
1)Un punto de la rejilla debe ser de buena o mala;
2)Simetría: si ( n, m ) es malo/bueno, entonces que así sea ( m, n );
3)Si ( n, m ) es un punto malo, entonces también lo son todos los puntos ( k, m ), n<=k<=2n;
4)Si ( k, m ) es bueno para todos los n/2<=k<=n-1 y ( n, t ) es bueno para todos los m/2<=k<=m-1, entonces ( n, m ) debe ser un punto malo. Y si esta condición no se cumpla, entonces ( n, m ) es un buen punto.
La reivindicación principal:
Para todos los fijos m>=2, todos los puntos malos contenida en el conjunto {( n, m ) | n es un entero positivo} forma una secuencia típica cuya duración inicial es menor o igual a m.
La prueba de esta afirmación se puede hacer por segunda inducción matemática. Y la notificación de las observaciones, 3) y 4), así como la propiedad de simetría 2) que puede ser ignorado, todos juegan un papel esencial dentro de la prueba. Sin embargo, no hay ningún truco durante la prueba, es sólo una combinación de varios de casi trivial cheques.
Luego, al obtener la demanda principal, uno puede ver fácilmente, tal vez un dibujo de estos puntos en una coordenada de la tarjeta es necesario, todos los puntos malos se han encontrado.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
