martes, 31 de enero de 2012
Problema del Día: Tomar números cuadrados
En una mesa hay piedras. Dos jugadores toman piedras alternadamente. En cada turno pueden tomar $x^2$ piedras, donde $x$ es un entero positivo. El jugador que no pueda tomar piedras, pierde. Muestra que hay una infinidad de posiciones iniciales para las cuales el segundo jugador tiene una estrategia ganadora.
Suscribirse a:
Comentarios de la entrada (Atom)
18 comentarios:
Supongamos que hay una cantidad finita de posiciones/numeros perdedoras/es para el primero que juega. (Perdedora y Ganadora siempre se referiran a si el primero pierde o gana, jugando optimamente ambos)
Entonces hay un $M$ tal que para todo $k\geq M$, $k$ es ganadora. En particular $(M+1)^2-1=M^2+2M\geq M$, entonces es ganadora.
Supongamos que quita $i^2$ piedras y quedan $t=(M+1)^2-1$.
Si $i\geq M+1$ entonces $t\leq -1$,lo cual deja piedras negativas, contradicción!
Entonces $i\leq M$. Asi que $t=(M^2-i^2)+2M\geq 2M\geq M$, entonces $t$ es ganadora. Pero entonces el primero que juegue ahí, que seria el segundo en el juego "absoluto", ganara. Lo cual hara que ambos ganen, contradicción!
Asi que como no existe tal $M$, hay posiciones perdedoras arbitrariamente grandes, y por lo tanto hay infinitas posiciones perdedoras.
Como dato adicional, como se pueden sacar $1^2=1$ piedras, entonces las perdedoras+1 son ganadoras, por lo que también hay infinitas ganadoras.
es $t=(M+1)^2-i^2-1$ *
Diremos que una posición es más grande si hay más piedras en el momento. Si iniciamos con una posición perdedora, entonces el segundo jugador, por definición, caerá siempre en una posición ganadora y por lo tanto tiene estrategia ganadora. Supongamos que el problema es falso y que hay una cantidad finita de posiciones perdedoras, digamos $i$ dónde el más grande es $A$ y el más pequeño es $2$ (pues el $1$ es ganadora el $2$ con facilidad revisamos que es perdedora). Veamos que como $5$ también es posición perdedora, entonces $A\geq 5$
Ahora consideremos un $k$ tal que $k^{2},2k-1\textgreater A$, entonces veremos que $k^{2}+1$ es posición ganadora por hipótesis. Pero entonces el primer jugador puede llevar al segundo jugador a una posición perdedora (por definición de posición ganadora). Sin embargo, si toma $k^{2}$, claramente lleva al segundo a una posición ganadora: el $1$, pues éste puede quitar $1$ y gana. Por lo mismo, el primer jugador debe quitar menos de $k^{2}$ y eso significa que quita a lo más $(k-1)^{2}$, pero esto nos lleva a que el segundo jugador tendrá al menos $2k$ piedras de dónde tomar después de esto, pero $2k\textgreater A$, así que hay una posición perdedora mayor a $A$, lo que es una contradicción a la definición de $A$. Por esto, hay infinitas posiciones perdedoras para el primer jugador. $\blacksquare$
A modo de contradicción, supongamos que existe un $\lambda$ tal que para si $\alpha \geq \lambda$, $\alpha$ es posición ganadora. En particular, $(\lambda+1)^2-1$ es posición ganadora (es fácil ver que es mayor que $\lambda$). Así, le puedo restar un cuadrado tal que el resultado sea positivo y $\textless \lambda-1$. Pero éste cuadrado es menos que $(\lambda+1)^2$ obviamente. Así, el cuadrado es al menos $\lambda^2$, por lo que el resultado es al menos $(\lambda+1)^2-1-\lambda^2=2\lambda \textgreater \lambda$. ¡Contradicción!. Así, nuestra hipótesis era falsa y sÃí hay infinitas posiciones perdedoras. Quod erat demonstrandum. $\clubsuit$.
Es claro que el primer jugador A gana si el num. de piedras q tiene al prinicipio es tal q al restarle un numero cuadrado positivo queda una cantidad de piedras que es perdedora; y para que pierda y entonces el primer jugador gane necesita estar en una posicion perdedora. Supongamos q hay una cantidad finita de posiciones iniciales para las cuales el segundo jugador tiene una estrategia ganadora, es decir hay una cantidad finita de posiciones perdedoras (e otro caso al empezar con toda esa infinidad de posiciones perderia A. Entonces hay un x tal que a partir de x todas son posiciones ganadoras. Pero $x^2$ + 1 > x, $x^2$ + 1 - $x^2$ = 1 y $x^2$ +1 - $y^2$ >= $x^2$ + 1 - $(x-1)^2$ = 2x > x, para y<= x-1. Entonces si $x^2$ + 1 es una posicion perdedora porq siempre t manda a posiciones ganadoras (1 es ganadora. Contradiccion porq no hay posiciones perdedoras mayores a x. Por lo tanto hay una infinidad de posiciones iniciales para las cuales el segundo jugador tiene una estrategia ganadora.
Sean $A$ y $B$ el primer y segundo jugador respectivamente. Al juego en donde hay $M$ piedras sobre la mesa lo llamaremos la posición $M$.
Definimos lo siguiente: la posición $M$ será perdedora si $A$ tiene la estrategia ganadora, y la posición $M$ será ganadora si $B$ tiene la estrategia ganadoras. Notemos que no hay empates en el juego, por lo tanto cada posición es o bien perdedora o ganadora.
Si al jugar de alguna forma estando en una posición ganadora pasamos a otra ganadora, entonces en esa nueva posición, $A$ tendría la estrategia ganadora, lo cual es una contradicción. Entonces cada posición ganadora solo nos lleva a otras perdedoras.
Ahora, procederemos por contradicción. Supongamos que a partir de cierta $K$ inclusive, todas las posiciones son perdedoras. Entonces tomamos un $2x+1$ mayor a $K$. Sabemos que $C=\left(x+1\right)^{2}+1$ y $2x+1$ son posiciones perdedoras, entonces Al jugar con $C$ piedras, en algún movimiento debemos caer en una posición ganadora, pero veamos que caemos en las posiciones
$\left(x+1\right)^{2}+1-1$
$\left(x+1\right)^{2}+1-4$
$\left(x+1\right)^{2}+1-9$
$\vdots$
$\left(x+1\right)^{2}+1-x^{2}=2x+2$
$\left(x+1\right)^{2}+1-\left(x+1\right)^{2}=1$
Y notemos que todas las posiciones anteriores mayores a $2x+1$ son perdedoras, y $1$ es perdedor, por lo que $C$ solo nos lleva a posiciones perdedoras y por lo tanto, es posición ganadora, contradiciendo el argumento que a partir de $K$ todas las posiciones son perdedoras. Entonces Hay una infinidad de posiciones ganadoras, pues si en algún punto no hubieran más, habría una contradicción, como queríamos.
Mi idea es escencialmente la misma a todas las anteriores.
Demostrando por contradicción supongamos que hay un $M$ para el cual el jugador que empieza siempre gana cuando hay $n$ mayor que $M$ piedras, entonces a partir de $M$ todas son posiciones ganadoras, la idea ahora es tomar dos cuadrados consecutivos que estén a distancia mayor que $M$ con lo cual claramente se llega a una contradicciíon, sinedo más específico si hay $(M+1)^2-1$ piedras entonces esa es una posición ganadora lo cual nos indica que quitando cierta cantidad de piedras se puede llegar a una perdedora, pero a lo más se pueden quitar $M^2$ piedras por lo que quedarán siempre más de $2M$ piedras que por lo que supusimos es una posición ganadora, con lo cual llegamos a una contradicción.
Llamaremos al primer jugador A y al segundo B.
Para comenzar, podemos asegurar que por el teorema de juegos, que existe una estrategia ganadora, para cada posición inicial.
Ahora, si $K$ es una posición en la cual, si el primero en mover juega de manera inteligente entonces gana la llamaremos POSICIÓN GANADORA. Si $K$ es un entero tal que si el segundo juega de manera inteligente, entonces él gana entonces es POSICIÓN PERDEDORA.
Ahora, como hay posiciones ganadoras y perdedoras, Siempre que la posición inicial sea en $K$ ganador, ganará A y si la posición inicial es $K$ perdedor, entonces B gana.
Si llamamos $S=\left \{a_{1},a_{2},...,a_{n} \right \}$ (ordenados crecientemente) al conjunto de números tales que B tiene la estrategia ganadora, entonces, en caso contrario al problema, S tiene un número finito de elementos.
Además, como B tiene la estrategia ganadora en estos, entonces cada elemento en $S$ es posición Perdedora.
Entonces, a partir de $a_{n}$ todas las posiciones son ganadoras. Tomemos a partir de eso un $x$ tal que $[(x+1)^2-1]-x^2=2x \textgreater a_{n}$. Entonces el número $(x+1)^2-1$ debería ser posición ganadora. Pero cuando A quite cualquier cuadrado, el resultante $R$ va a cumplir que $R \textgreater a_{n}$. Pero como B tiene que jugar ahora, la posición $R$ debe ser perdedora (para que B pierda). Entonces $R$ es posición perdedora y se ve una contradicción pues $a_{n}$ era la más grande posición perdedora.
Como no es posible que sean finitas, entonces hay un infinito de posiciones en las que B gana.
Supongamos que sí es finita, entonces debería de existir un n tal que sea el último en el que la 2a persona gane, y por lo tanto todo P>n gana el jugador en turno, en este caso el jugador 1 si se comienzan con P piedras.
Ahora tomemos este numero x^2 - 1, es claro que el mayor cuadrado que se le puede restar es (x-1)^2. Entonces tomemos a x^2 - 1 - (x-1)^2 > n ---> x>(n+2)/2
ahora como tenemos la desigualdad x^2 - 1 - (x-1)^2 > n , si le restamos en lugar de (x-1)^2 un cuadrado menor, siempre se cumpliría la desigualdad, por lo tanto sin importar cual cuadrado le deseariamos restar, siempre nos saldria un numero mayor a n, pero esto contradice a lo que supuse al inicio, pues entonces le tocaria al 2o jugador y tiene un P>n donde ganaría, pues es su turno.
entonces el numero de posiciones iniciales en las que gana el 2o jugador son infinitas.
Voy a proceder por reducción al absurdo. supongamos que hay una cantidad finita de posiciones ganadoras iniciales para el segundo jugador, digamos que a partir de un número $ n $ el jugador que tenga esa cantidad siempre gana y tomemos el número $ n^2 + 2n $, a lo más podemos quitar $ n^2 $ lo que le deja al segundo jugador 2n piedras, que por como definimos a $ n $ es una posición ganadora para el segundo jugador, lo cual es un absurdo.
Llamemos A al primer jugador y B al segundo. Supongamos lo contrario. Entonces existe N tal que para toda M mayor o igual a N, si la cantidad inicial es de M piedras entonces A tiene estrategia ganadora. Como A es el primero en jugar, significa que encontrarse con M piedras en la mesa es una posición ganadora, por lo que A siempre debe quitar suficientes piedras para dejar menos de N en la mesa. Veamos el caso M= $(N+1)^2-1$ (que claro es mayor a N). Como se debe quitar un cantidad cuadrado perfecto de piedras, la máxima cantidad que se puede quitar es $N^2$, así que al menos quedarían 2N piedras, que es mayor a N, así que llegamos a una contradicción.
Dios, casi todas las soluciones son iguales. y yo que creía que había sido una idea creativa :/
Según yo la mía usa $\left(x+1\right)^{2}+1$ en vez de $\left(x+1\right)^{2}-1$, pero es esencialmente lo mismo.
Tenemos que demostrar que hay infinitas posiciones perdedoras. Supongamos que son finitas. Entonces, para todo `$a\geq N$ para algún $N$ entero positivo, $a$ es una posición ganadora. Tomemos un entero positivo $x$ tal que $(x+1)^{2}>N+x^{2}$. Existe este número pues para que $x$ cumpla esto es suficiente que $2x+1>N$. Tomemos un entero positivo $n$ tal que $(x+1)^{2}> n\geq N+x^{2}$. Vemos que para todo $y\leq x$, $n-y^{2}\geq n-x^{2}\geq N$, de donde $n-y^{2}$ es posición ganadora. Por otro lado, si $y\geq x+1$, $n-y^{2}\leq n-(x+1)^{2}<0$, por lo que no es posible sustraer $y$ a $n$. Entonces, sólo podemos llegar a posiciones ganadoras desde $n$, por lo que $n$ es perdedora, pero como $n\geq N+x^{2}>N$, $n$ es ganadora, lo cual es una contradicción. Entonces, hay infinitas posiciones perdedoras.
Hay que demostrar que hay infinitas posiciones perdedoras, para que el segundo tenga infinitas posiciones iniciales ganadoras.
Si no hay infinitas, entonces son finitas, y como hay infinitas posiciones iniciales, entonces tendran que haber infinitas posiciones ganadoras.
Sea $k$ el mayor entero tal que con $k$ piedras pierdes. Sea $p$ un entero tal que $2p+1 \geq k+2$.
Vemos que pasa cuando hay $n$ piedras, con $n=p^2+k+1$.
Si el jugador A quita $x^2$ piedras, con $x\leq p$, van a quedar $n-x^2 \geq p^2+k+1-p^2=k+1 \textgreater k$, y por hipotesis esta va a ser una posicion ganadora.
Si el jugador A quita $x^2$ con $x\geq p+1$, van a quedar $n-x^2\leq p^2+k+1 - (p+1)^2=k-2p\leq -1$
Entonces no se van a poder $(p+1)^2$ o mas, y si quitamos $p^2$ o menos B va a quedar en posicion ganadora, por lo tanto $n$ es una posicion perdedora, contradiccion. Entonces hay infinitas posiciones ganadoras para las cuales B tiene estrategia ganadora.
Llamamos A al primer jugador y B al segundo. Suponiendo que B no tuviese infinitas posiciones iniciales ganadoras, habría un K tal que para todo $m \geq k$ tendremos que A tiene posición ganadora, pero entonces nos fijamos en x tal que $2x+1 \textgreater K $ entonces tenemos que $(x+1)^2 \textgreater (x)^2+k$ entonces en el numero $(x)^2+k$ tendremos que A dejara a B en su siguiente turno en un numero mayor o igual que K dado que puede tomar a lo mas $x^2$ piedras, lo que significa que haga lo que haga A, B ganaría por la suposición del principio, pero eso es una contradicción, por lo que B tiene infinitas posiciones iniciales ganadoras
Publicar un comentario