Maratón de Problemas

Eduardo aragon

FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Mención Especial-FOFO 9 años OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022
Mensajes: 14
Registrado: Sab 02 Feb, 2019 9:36 pm
Medallas: 6
Nivel: 3
Ubicación: Arequipa, Peru

Re: Maratón de Problemas

Mensaje sin leer por Eduardo aragon »

etiquetamos en la tabla de $8x8$
A,B,C,D,E,F,G,H
H,A,B,C,D,E,F,G,
G,H,A,B,C,D,E,F
F,G,H,A,B,C,D,E,
E,F,G,H,A,B,C,D,
D,E,F,G,H,A,B,C
C,D,E,F,G,H,A,B
B,C,D,E,F,G,H,A
(no se como enviar imagenes jejejje)
en vez de colocar casillas negras o blancas, colocaremos 1 o 0 respectivamente
diremos que $x(A)$ es la suma de todas las casillas con 1's y 0's que estan en las casillas de A por ejemplo si solo la esquina superior izquierda esta pintada entonces $x(A)=1$ y $x(B)=0$
notemos que cualquier operacion afectara a todas las letras y que aplicando solo una operacion $x(A)$ aumentara o disminuira en 1 (obviamente esto ocurre tambien con $x(B)$, $x(C)$, etc.)
de aqui podemos ver una invariante:
el residuo de $x(A)-x(B)$ en $mod2$ esto es porque al hacer la operacion la paridad de $x(A)$ y $x(B)$ cambia de par a impar o viceversa, de aqui es facil ver que en $mod 2$ su residuo no cambia (basta ver que $par-par=impar-impar$ y otro caso mas)

luego:
a) supongamos que es posible
como una esquina esta pintada entonces $x(A)=1$ y $x(B)=x(C)=x(D)=...=x(H)=0$ y para el tablero requerrido seria $x(A)=X(B)=X(C)...=x(H)=8$ de esto cualquier diferencia en mod 2 seria 0 pero vemos que al comienzo hay diferencias en mod 2 igual a 1 como $x(A)-x(B)$ contradiccion

b)por lo anterior visto todas las diferencias del tablero requerido en mod 2 son 0, entoces al comienzo debe ser tambien asi. Como $x(A)\geq 1$
entonces $x(B)\geq 1,x(C)\geq 1,...,x(H)\geq 1$ y sumando seria que el tablero del comienzo es mayor o igual que 8 y un ejemplo seria pintar toda la primera fila que claramente es posible mediante operaciones realizar lo pedido. luego como minimo es necesario pintar de negro 7 casillas
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

Esto lleva demasiado tiempo inactivo, así que pongo un problema nuevo para revivirlo un poco

Problema 337
Santi y Cristina juegan en una mesa redonda al siguiente juego:
Sobre el borde de la mesa hay $99$ huecos, que forman los vértices de un polígono regular de $99$ lados. Se tienen bolitas de color rojo o azul, una cantidad ilimitada de bolitas de cada color. Comienza Cristina, que coloca una bolita en uno de los huecos, luego, alternadamente, cada jugador coloca una bolita en un hueco adyacente a otro que haya sido ocupado en alguno de los turnos anteriores. El juego termina cuando todos los huecos están ocupados.
Si al finalizar el juego hay $3$ bolitas de un mismo color que son los vértices de un triángulo equilátero, gana Santi. En otro caso, gana Cristina.

Decidir si alguno de los jugadores tiene una estrategia ganadora. Si la respuesta es sí, dar una estrategia para ese jugador y demostrar que es ganadora. Si la respuesta es no, explicar por qué ningún jugador tiene una estrategia ganadora.
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
jhn

OFO - Medalla de Plata-OFO 2018
Mensajes: 520
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela

Re: Maratón de Problemas

Mensaje sin leer por jhn »

Solución al 337
Spoiler: mostrar
Santi tiene una estrategia ganadora. Durante los primeros 33 movimientos se ocupan 33 huecos consecutivos, que numeramos en sentido horario del 1 al 33. En el movimiento siguiente Santi coloca una bolita en el hueco 99, del mismo color que la que está en el hueco 33. Como 33, 66 y 99 son los vértices de un triángulo equilátero, si Santi logra ocupar el hueco 66 gana, colocando una bolita del mismo color que las que están en 1 y 99. Para ello, si Cristina juega en 34 Santi lo hace en 98, y viceversa. Lo mismo hace con los pares (35,97), (36,96),...,(64,68). En este momento Cristina debe jugar en 65 o 67, a lo cual Santi juega en 66 y gana. (Claro que es posible que ya hubiese ganado antes, pero en el peor de los casos gana en su última jugada).
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
Avatar de Usuario
jhn

OFO - Medalla de Plata-OFO 2018
Mensajes: 520
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela

Re: Maratón de Problemas

Mensaje sin leer por jhn »

Problema 338
Hallar todos los polinomios $P(x)$ con coeficientes enteros tales que $P(P(n)+n)$ es un número primo para infinitos enteros $n$.
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: Maratón de Problemas

Mensaje sin leer por Matías »

Solución 338
Spoiler: mostrar
Aclaro que mi solución cumple considerando como primos solo a los positivos o a los positivos y negativos.

Si $P$ es constante, es decir $P(x)=c$ $\forall x\in R$, $c\in Z$, tenemos que $P(P(n)+n)=c$ es primo para infinitos $n\in Z$, por lo tanto $c$ debe ser primo, y está claro que todo polinomio $P(x)=c$ $\forall x\in R$ con $c$ primo cumple.

Si $P$ es lineal no constante, es decir $P(x)=mx+h$ $\forall x\in R$, $m, h\in Z$, $m\neq 0$, tenemos que $P(P(n)+n)=P((m+1)n+h)=m(m+1)n+mh+h=(m+1)(mn+h)$ es primo para infinitos $n\in Z$. Pero si $m=-1$ nos queda que $P(P(n)+n)=0$ $\forall n\in Z$ (absurdo), y si $m\geq 1$ o $m\leq -3$ tenemos que $|m+1|\geq 2$, por lo tanto si $(m+1)(mn+h)$ es primo necesariamente es $|mn+h|=1\implies n=\frac{1-h}{m}\vee n=\frac{-1-h}{m}$, lo cual no se cumple para infinitos $n\in Z$ (absurdo). Así que debe ser $m=-2$, con lo que nos queda que $P(P(n)+n)=2n-h$ es primo para infinitos $n\in Z$, lo cual es cierto si y solo si $h$ es impar, $h=2k+1$, $k\in Z$.
Entonces los polinomios que cumplen son ($P(x)=-2x+2k+1$ $\forall x\in R$) $\forall k\in Z$.

Si $P$ no es lineal ni constante tenemos que $gr(P)=m\in N$, $m\geq 2$. Como $P(x)\in Z[X]$ tenemos que $P(n)\in Z$ $\forall n\in Z$, y tenemos que $a-b\mid P(a)-P(b)$ $\forall a, b\in Z, a\neq b$ (ya que si $P(n)=c_0+\sum_{i=1}^{m}c_in^i$ $\forall n\in Z$, con $c_i\in Z$ $\forall(i\in N_0\wedge i\leq m)$, $c_m\neq 0$, tenemos que $P(a)-P(b)=c_0+\sum_{i=1}^{m}c_ia^i-c_0-\sum_{i=1}^{m}c_ib^i=\sum_{i=1}^{m}c_i(a^i-b^i)=(a-b)\sum_{i=1}^{m}c_i(\sum_{j=0}^{i-1}a^{i-1-j}b^j)$). Por otro lado, tenemos que existen a los sumo $m$ enteros $n$ tales que $P(n)=0$, ya que $gr(P)=m\in N$ por ende tiene a lo sumo $m$ raíces reales, por el mismo motivo existen a lo sumo $m$ enteros $n$ tales que $P(n)=1$ (ya que $gr(P(n)-1)=m$) y a lo sumo $m$ enteros $n$ tales que $P(n)=-1$ (ya que $gr(P(n)+1)=m)$. Así que considerando todos los $n\in Z$ con $|P(n)|\geq 2$, si tomamos $a=P(n)+n$ y $b=n$ nos queda que $(P(n)+n)-n\mid P(P(n)+n)-P(n)\implies P(n)\mid P(P(n)+n)-P(n)\implies P(n)\mid P(P(n)+n)$. De esta forma, si existieran infinitos $n\in Z$ tales que $P(P(n)+n)$ es primo, deberán existir o bien infinitos $n\in Z$ tales que $P(n)=P(P(n)+n)$ o bien infinitos $n\in Z$ tales que $P(n)=-P(P(n)+n)$. En el primer caso, el polinomio $Q(x)=P(x)-P(P(x)+x)$ tiene infinitas raíces, así que es el polinomio nulo y $P(x)=P(P(x)+x)$ $\forall x\in R$, pero $gr(P(x)+x)=m\implies gr(P(P(x)+x))=2m>m=gr(P(x))$ (absurdo). Y en el segundo caso, el polinomio $Q(x)=P(x)+P(P(x)+x)$ es el polinomio nulo, así que $P(x)=-P(P(x)+x)$ $\forall x\in R$, pero $gr(-P(P(x)+x))=2m>m=gr(P)$ (absurdo).

Por lo tanto concluimos que los polinomios que cumplen son ($P(x)=c$ $\forall x\in R$) $\forall c$ primo, y ($P(x)=-2x+2k+1$ $\forall x\in R$) $\forall k\in Z$.
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: Maratón de Problemas

Mensaje sin leer por Matías »

Problema 339

Hallar todos los tríos $(x,y,z)$ de números enteros tales que

$$2^x+2017^y=2019^z$$
Avatar de Usuario
jhn

OFO - Medalla de Plata-OFO 2018
Mensajes: 520
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela

Re: Maratón de Problemas

Mensaje sin leer por jhn »

Solución 339
Spoiler: mostrar
La única solución es (1,1,1).

En primer lugar es fácil ver que no hay soluciones con $x$, $y$ o $z$ negativos. Supongamos entonces $x, y, z\ge 0$. Tampoco hay soluciones con $z=0$, y con $z=1$ es claro que la única solución es (1,1,1). Supongamos ahora $z\ge 2$ y veamos que no hay más soluciones.

Módulo 2018 se tiene $2^x+(-1)^y\equiv 1\pmod{2018}$, luego $y$ debe ser impar (de lo contrario se tendría $2^x\equiv 0\pmod{2018}$, absurdo). Como $2019=3\cdot 673$ y $z\ge 2$ resulta que módulo 9 se tiene $2^x+1\equiv 0\pmod{9}$, de donde $x$ es de la forma $3+6k$ y en particular debe ser impar y mayor que 2. Módulo 4 se tiene $1\equiv (-1)^z\pmod{4}$, de donde $z$ debe ser par. Módulo 2017 se tiene
$2^x \equiv 2^z\pmod{2017}$, de donde $2^{|x-z|} \equiv 1\pmod{2017}$. Pero $|x-z|$ es impar, luego el orden $r$ de 2 módulo 2017 (el menor entero positivo $r$ tal que $2^r \equiv 1\pmod{2017}$) debe ser impar. Como por Fermat se cumple $2^{2016} \equiv 1\pmod{2017}$, $r$ debe ser un divisor impar de $2016=2^5\cdot 3\cdot 9$. Es decir que $r|63$ y entonces $2^{63} \equiv 1\pmod{2017}$ y $2^{64} \equiv 2\pmod{2017}$. Pero esto es falso, en efecto $2^{16}=65536\equiv 992\pmod{2017}$,
$2^{32}\equiv 992^2=984064\equiv 1785\equiv -232\pmod{2017}$ y
$2^{64}\equiv (-232)^2=53824\equiv 1785\equiv 1382\pmod{2017}$. Esta contradicción nos muestra que no hay soluciones con $z>1$.
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Maratón de Problemas

Mensaje sin leer por Turko Arias »

Ya que no hay problema publicado, es un buen momento para decir que este problema sigue sin ser resuelto :D :D
Turko Arias escribió: Dom 30 Jun, 2019 7:23 pm Buenas buenas, para darle vida a esto y aprovechar que se vienen las vacaciones cambio el problema en vigencia, que ya lleva un par de meses sin ser resuelto :D
Problema $335+\epsilon$, con $\epsilon$ arbitrariamente chico
Hallar el menor entero positivo $n$ tal que podemos escribir los números $1,2,\dots ,n$ en una cuadrícula de $18 \times 18$ de manera que:
$i)$ Cada número aparezca al menos una vez
$ii)$En cada fila y en cada columno, no haya dos números que difieran en $0$ o en $1$.
El problema dice que en cada fila y en cada columna NO HAYA DOS NÚMEROS QUE DIFIERAN EN $0$ O EN $1$, en ningún momento habla de números adyacentes, sino en toooda la fila y en tooooda la columna, la solución que pongo abajo de @jhn no funciona porque lo resuelve para números adyacentes, pero para el enunciado original no funciona porque, por ejemplo, $1$ y $2$ difieren en uno y se encuentran en la misma fila
jhn escribió: Vie 05 Jul, 2019 11:23 am Solución al $335+\epsilon$:
Spoiler: mostrar
El menor $n$ es 18. Es claro que si $n<18$ no se puede, pues en cada fila tendría que repetirse algún número. Para $n=18$ tomemos una permutación $a_1$, $a_2$,..., $a_{18}$ de los enteros del 1 al 18, tal que $|a_{i+1}-a_i|>1$ para $i=1,2,\ldots,17$ y $|a_{18}-a_1|>1$, por ejemplo 1,3,5,7,9,11,13,15,17,2,4,6,8,10,12,14,16,18 sirve. Coloquemos en la primera fila $a_1$, $a_2$,..., $a_{18}$, en la segunda fila $a_{18}$, $a_1$, $a_2$,..., $a_{17}$ y así sucesivamente, es decir que cada fila es igual a la anterior rotada cíclicamente un lugar hacia la derecha. Es claro que esta distribución cumple las condiciones.
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
jhn

OFO - Medalla de Plata-OFO 2018
Mensajes: 520
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela

Re: Maratón de Problemas

Mensaje sin leer por jhn »

En efecto, leí mal el enunciado y resolví un problema diferente al propuesto. El mínimo $n$ es 37, ya edité mi solución.
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
Avatar de Usuario
jhn

OFO - Medalla de Plata-OFO 2018
Mensajes: 520
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela

Re: Maratón de Problemas

Mensaje sin leer por jhn »

Problema 340
Hay 100 estudiantes tomando un examen. El profesor los llama uno por uno y les hace una sola pregunta: ¿Cuántos de los 100 estudiantes resultarán aprobados al finalizar este examen? La respuesta del estudiante debe ser un número entero. Una vez oída la respuesta, el profesor de inmediato y públicamente anuncia su veredicto, que puede ser aprobado o reprobado. Una vez examinados todos los estudiantes, llega un inspector que revisa si algún estudiante fue reprobado pero dijo la respuesta correcta. Si hay al menos un estudiante en esa situación, entonces el profesor es suspendido y todos los estudiantes aprueban el examen. De lo contrario, no se realiza ningún cambio. ¿Pueden los estudiantes ponerse de acuerdo en alguna estrategia que les permita aprobar el examen a todos?
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
Responder