Maratón de Problemas

[jhn]

Problema 290
Ana y Beto juegan a retirar piedras de un montón que inicialmente contiene [math]n\ge 1 piedras, alternadamente y comenzando por Ana. Cada jugador en su turno, si en el montón hay [math]m piedras, debe retirar un número [math]k>0 de piedras tal que o bien [math]k sea par y [math]k\le m/2 o bien [math]k sea impar y [math]m/2\le k\le m. El jugador que retire la última piedra gana. Determine, en función de [math]n, qué jugador tiene una estrategia ganadora

[Violeta]

Pequeña cuestión:

Cuando dices [math]k \leq n/2 y [math]n/2 \leq k \leq n aquí [math]k es la cantidad de piedras que hay en ese turno y no la cantidad inicial de piedras, verdad? Porque de otro caso, asumiendo [math]n=4 y escogiendo [math]k=3, no habría forma de proceder.

[Emerson Soriano]

Es claro que si [math]n es impar, gana Ana, ya que elige [math]k=n y retira todas las piedras. Lo que no me cuadra es cuando [math]n es par, porque entonces [math]n-1 es impar y Ana puede elegir [math]k=n-1 y de ese modo evita que Beto gane, ya que Beto no podrá realizar la próxima jugada, pero de ese modo el problema es sencillo y me hace pensar que estoy entendiendo mal el enunciado.

Acaso el [math]k está dependiendo cada vez del nuevo número de piedras? O es únicamente del valor inicial?

[Violeta]

Es claro que si [math]n es impar, gana Ana, ya que elige [math]k=n y retira todas las piedras. Lo que no me cuadra es cuando [math]n es par, porque entonces [math]n-1 es impar y Ana puede elegir [math]k=n-1 y de ese modo evita que Beto gane, ya que Beto no podrá realizar la próxima jugada, pero de ese modo el problema es sencillo y me hace pensar que estoy entendiendo mal el enunciado.

Acaso el [math]k está dependiendo cada vez del nuevo número de piedras? O es únicamente del valor inicial?

Lo que dijo él ^^

[Emerson Soriano]

Al parecer el [math]k va variante de acuerdo al nuevo número de piedras, siendo así, muestro mi solución.

Spoiler: mostrar

Es claro que si [math]n es impar, entonces Ana gana, pues elige quitar todas las piedras, y, por ende, quita la última piedra.

Si [math]n es par, entonces Ana, en su primera jugada, debe elegir necesariamente un [math]k par (considerando que juega de la mejor forma), pues de lo contrario deja un número impar de piedras a Beto y por lo dicho anteriormente, Beto ganaría.

Probaremos que Beto gana sólo cuado [math]n=2^m-2, donde [math]m\geq 2 y en otro caso de [math]n par, gana Ana. En efecto, para [math]m=2, tenemos [math]n=2. En este caso, Ana, en su primer turno, sólo puede quitar [math]1 piedra, entonces Beto quita la última piedra y gana. Supongamos que existe un entero positivo [math]m\geq 2 tal que Beto sólo gana cuando en el turno de Ana hay [math]2^i-2 piedras, para todo [math]i=2, 3, ... , m. Ahora, si la cantidad de piedras es [math]n (par), con [math]2^{m}\leq n\leq 2^{m+1}-4, entonces, como Ana puede elegir [math]k piedras, donde [math]k puede ser [math]2, [math]4, [math]6,
... ó [math]2^{m}-2, entonces ella puede elegir uno de esos números para que, en el turno de Beto, haya [math]2^m-2 piedras y así Ana garantiza su victoria. Luego, para [math]n=2^{m+1}-2, Ana sólo puede elegir en su primer turno: [math]2, [math]4, ... , [math]2^{m}-2 piedras, pero de cualquier forma, siempre le deja a Beto una cantidad [math]t de piedras tal que [math]2^m\leq t\leq 2^{m+1}-4, de este modo Beto gana, quedando completa la inducción.

[jhn]

Sí, disculpen, debí decir que cada jugador, en su turno, si hay [math]m piedras en el montón, retira un número [math]k>0 de piedras tal que o bien [math]k sea par y [math]k\le m/2 o bien [math]k sea impar y [math]m/2\le k\le m.

La solución de Emerson es correcta.

[Emerson Soriano]

Problema 291.
Para cada entero positivo [math]n, se define por [math]d(n) al número de divisores positivos de [math]n. Por ejemplo, [math]d(11)=2 y [math]d(6)=4.

Demostrar que existen infinitos enteros positivos que no se pueden expresar de la forma [math]a^{d(a)}+b^{d(b)}, donde [math]a y [math]b son enteros positivos.

[jhn]

Solución 291

Spoiler: mostrar

Es sabido que hay infinitos primos de la forma [math]4n+3, y que ninguno de ellos es representable como la suma de dos cuadrados. Pero [math]d(n) es par excepto cuando [math]n es un cuadrado perfecto, por lo tanto [math]a^{d(a)} es siempre un cuadrado perfecto y ningún [math]p=4n+3 puede ser de la forma [math]a^{d(a)}+b^{d(b)}.

[Emerson Soriano]

Está correcta la solución.

[jhn]

Problema 292
Sean [math]n un entero positivo y [math]a_1, [math]a_2,...,[math]a_n números reales tales que [math]a_1^2+\cdots+a_n^2=1. Pruebe que

[math]\sum_{1\le ij\le n} a_ia_j < 2\sqrt{n}.