OFO 2018 Problema 6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018
FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 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 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
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

OFO 2018 Problema 6

Mensaje sin leer por AgusBarreto »

Para cada entero positivo $n>1$ denotamos $p(n)$ al menor número primo que divide a $n$. Por ejemplo, $p(2018)=2$ y $p(35)=5$.
Determinar todas las parejas de enteros $(a,b)$, ambos mayores que $1$, que satisfacen la ecuación $$ a^2 + b = p(a) + p(b)^2. $$
1  
Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018
FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 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 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
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: OFO 2018 Problema 6

Mensaje sin leer por AgusBarreto »

Aquí vamos a publicar la solución oficial.
Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 OFO - Medalla de Oro-OFO 2024
Mensajes: 211
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 5
Nivel: Exolímpico

Re: OFO 2018 Problema 6

Mensaje sin leer por enigma1234 »

Spoiler: mostrar
Sea (a,b) una pareja que cumpla la ecuación dada. Es claro que $x\geq p(x)$ para todo $x$ mayor que 1.
Si b no es primo entonces es el producto de al menos 2 primos mayores iguales que $p(b)$ asi que entonces $b\geq p(b)^2$ y como $a\geq p(a)$ entonces $a^2\geq p(a)^2>p(a)$ dado que $p(a)$ es un primo osea mayor que 1. Sumando estas 2 cosas tenemos que $a^2+b>p(a)+p(b)^2$ lo cual es una contradicción.
Entonces b es primo.Entonces $p(b)=b$. En la ecuación inicial:$a^2+b=p(a)+b^2$ entonces como $a\geq p(a)$ tenemos que: $a^2+b\leq a+b^2$ de esto tenemos $0 \leq (b-a)(b+a-1)$ es claro que el segundo termino siempre es positivo dado que a y b son mayores que 1, entonces nos queda $a\leq b$.Si $a<b$ tenemos que $a\leq b-1$ reemplazando esto en la inicial tenemos que :$(b-1)^2+b\geq a^2+b=p(a)+b^2>b^2\geq b^2-(b-1)=(b-1)^2+b$ lo cual es una contradicción.
Entonces nos queda que $a\leq b$ y que $a\geq b$ entonces $a=b$ con $b$ primo.
Entonces todas las parejas (a,b) que cumplen son (p,p) para todo p primo y es claro que cumplen.

Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 68
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario

Re: OFO 2018 Problema 6

Mensaje sin leer por Fran2001 »

Spoiler: mostrar
Reescribamos primero la igualdad original como $a^2-p(a)=p(b)^2-b$.
Ahora notemos que $p(a)\mid a\Rightarrow p(a)\leqslant a\Rightarrow p(a)<a^2\Rightarrow 0<a^2-p(a)=p(b)^2-b\Rightarrow b<p(b)^2$. (1)
Notemos también que, al ser $p(b)$ el menor divisor primo de $b$; es también el menor divisor distinto de $1$.
Ahora, como $p(b)\mid b$; sea $x=\frac b{p(b)}\Rightarrow x\cdot p(b)=b$. Ahora tenemos $3$ casos:
  • $x>p(b)$
  • $x=p(b)$
  • $x<p(b)$
Caso $x>p(b)$
Spoiler: mostrar
En éste caso $p(b)^2=p(b)\cdot p(b)<x\cdot p(b)=b$; lo que es absurdo ya que contradice (1).
Caso $x=p(b)$
Spoiler: mostrar
En éste caso $p(b)^2=x\cdot p(b)=b$; lo que de nuevo es absurdo ya que contradice (1).
Caso $x<p(b)$
Spoiler: mostrar
Como $p(b)=\frac bx$ es entero, tenemos que $x\mid b$; pero como $p(b)$ es el menor divisor de $b$ distinto de $1$; y $x<p(b)$; entonces $x=1\Rightarrow p(b)=b$.
Sea $p$ el primo tal que $p=p(b)=b$; tenemos que $p(b)^2-b=p^2-p=p\cdot (p-1)$.
Sea $q=p(a)$. Ahora:
$\bullet$ Si $a=p(a)=q$ necesitamos que $a^2-p(a)=q^2-q=q\cdot (q-1)$ sea igual a $p\cdot (p-1)$; y como $p\cdot (p-1)$ es estrictamente creciente al crecer $p$; la igualdad sólo se cumple al ser $q=p\Leftrightarrow a=b=p$.
$\bullet$ Si $a\neq p(a)$ entonces $a>p(a)$ y queremos que se cumpla la igualdad $a^2-p(a)=p^2-p$
Lo separamos en $2$ casos: si $a\geqslant p$; o si $a<p$.
En el primer caso tenemos $a^2-p(a)>a^2-a=a\cdot (a-1)\geqslant p\cdot (p-1)=p^2-p$; lo que contradice la igualdad que buscamos.
En el segundo caso, $a<p\Leftrightarrow a\leqslant p-1$ (al ser ambos enteros positivos). Entonces $a^2-p(a)<a^2\leqslant (p-1)^2<p\cdot (p-1)=p^2-p$; lo que de vuelta contradice la igualdad que buscamos.
Por lo tanto los únicos pares que cumplen son los $(p;p)$; con $p$ primo.
1  
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4
Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 164
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 9
Nivel: Exolímpico
Contactar:

Re: OFO 2018 Problema 6

Mensaje sin leer por ¿hola? »

No se que tan bien estará
Spoiler: mostrar
miremos que $a^2>a\geq p(a)$ osea $a^2>p(a)$ y para que se cumpla la igualdad de la ecuación
$p(b)^2>b$ lo que implica $p(b )> \sqrt{b}$ y $p(b)$ es el menor primo que divide a $b$ nos que dan dos casos $b=p(b)^2$ que no cumple $p(b )> \sqrt{b}$, o $b=p(b)$ para el cual si se cumple $p(b )> \sqrt{b}$.
Entonces concluimos que $b$ es primo.

ahora $a^2 + b = b^2 + p(a)$ pasamos restando y tenemos $a^2 - p(a) +(b -b^2) = 0$
tomemos $a=p(a)k$
entonces $k^2 p(a)^2 - p(a) +(b -b^2) = 0$ que es una cuadrática en $p(a)$. resolvemos y nos queda

$p(a)=\frac{1 \pm \sqrt{1-4k^2(b-b^2)}}{2k^2}$

osea que $1-4k^2(b-b^2)=4k^2 b^2 - 4k^2b + 1$ es un cuadrado perfecto. Supongamos $k>1$

entonces $4k^2 b^2 - 4k^2b + 1 < 4k^2 b^2 - 4k^2b + k^2 = (2kb - k)^2$

ahora miremos la diferencia entre $4k^2 b^2 - 4k^2b + 1$ y $(2kb - (k+1))^2$

$4k^2 b^2 - 4k^2b + 1 - 4k^2 b^2 + 4k(k+1)b - (k+1)^2$

que es igual a $4bk - k^2 - 2k = k(4b-k-2)$

vamos a demostrar que $4b>k+2$

si $b \leq p(a)$ osea $b=p(a)-x$
tenemos $a^2 + b = b^2 + p(a)$ osea $k^2p(a)^2 + p(a)-x = p(a) + p(a)^2 - 2xp(a) + x^2$
osea $(k^2 -1)p(a) = x( x+1-2xp(a) )$ es claro aqui que el miembro izquierdo es mayor a $0$ ya que $k$ es mayor a $1$ y el miembro derecho es menor a $0$ que es absurdo asi que $ b>p(a) $
y tenemos $k^2p(a)^2 - p(a) = b^2 - b$ osea $b^2 > k^2p(a)^2 - p(a) $ si dividimos todo por $p(a)$ obtenemos
$b>k^2p(a) -1$ y como $p(a)$ es minimo $2$, $b>2k^2-1$ lo que implica que $4b>8k^2 -1>k+2$ para todo $k$ positivo
entonces $4b>k+2$ lo que implica que la diferencia entre $4k^2 b^2 - 4k^2b + 1$ y $(2kb - (k+1))^2$ es positiva
osea $(2kb - (k+1))^2< 4k^2 b^2 - 4k^2b + 1 <(2kb - k)^2$ por lo que $4k^2 b^2 - 4k^2b + 1$ no es un cuadrado perfecto lo que es absurdo.

Entonces $k=1$ lo que implica $a=p(a)$.
ahora remplazamos en la cuadrática $k$ por $1$ y nos queda $p(a)=b$, o $p(a)=1-b$que es absurdo.
osea que $p(a)=p(b)=a=b$ que claramente cumplen la ecuacion y son las únicas soluciones.
Yes, he who
Avatar de Usuario
davisbeckam18

OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Oro-OFO 2018
Mensajes: 19
Registrado: Sab 17 Dic, 2016 8:57 pm
Medallas: 3
Nivel: 2

Re: OFO 2018 Problema 6

Mensaje sin leer por davisbeckam18 »

Spoiler: mostrar
Respuesta: $(a,b)=(p,p)$, donde $p$ es primo.

Sea $p(n)$ el menor número primo que divide a $n$. Hallemos todas las parejas de enteros $(a,b)$, ambos mayores que 1, que satisfacen la ecuación $a^2+b=p(a)+p(b)^2$. Supongamos que $(a,b)$ sea una solución de la ecuación. Como $p(a)\mid a$ $\implies$ $p(a)\leq a$ $\implies$ $p(a)< a^2$ $\implies$ $b <p(b)^2$ $\implies$ $p(b)k <p(b)^2$ $\implies$ $k<p(b)$. Si $k$ es mayor que $1$, entonces tiene al menos un divisor primo el cual es mayor que $p(n)$. Contradicción. $\implies$ $k=1$ $\implies$ $b=p(b)=p$, con $p$ primo. Entonces $a$ satisface $a^2+p=p(a)+p^2$. Como $p(a)$ es un primo $q$ $\implies$ $q\mid a^2-q=p^2-p=p(p-1)$. Si $q=p$, entonces $(a,b)=(p,p)$. Si $q\neq p$, entonces $q\mid p-1$ $\implies$ $p=ql+1$ con $l\in \mathbb{N}$ $\implies$ $a^2+p=p(a)+p^2$ $\Leftrightarrow$ $a^2=q+p(p-1)$ $\Leftrightarrow$ $a^2=q+(ql+1)(ql)$ $\Leftrightarrow$ $(\frac{a}{q})a=1+(ql+1)l$ $\Leftrightarrow$ $(\frac{a}{q})a=ql^2+l+1$ $\Leftrightarrow$ $(\frac{a}{q})(\frac{a}{q})=l^2+\frac{l+1}{q}$ $\implies$ $q\mid l+1$ $\implies$ $l=qm-1$ con $m\in \mathbb{N}$ $\implies$ $(\frac{a}{q})^2= l^2 +m$ $\implies$ $m\geq 2l+1$. Pero como $\frac{l+1}{q}=m$ $\implies$ $l+1\geq q(2l+1)\geq 2(2l+1)=4l+2$ $\Leftrightarrow$ $0\geq 3l+1$ Contradicción.

Concluimos que las únicas parejas que cumplen son $a=b=p$ con $p$ primo.
Avatar de Usuario
BrunoDS

OFO - Medalla de Plata-OFO 2018 OFO - Medalla de Oro-OFO 2019
Mensajes: 99
Registrado: Dom 16 Nov, 2014 7:09 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Martínez

Re: OFO 2018 Problema 6

Mensaje sin leer por BrunoDS »

Spoiler: mostrar
Ordenando un poco tenemos que: $a^2-p(a)=p(b)^2-b$

Notemos que $p(a)\le a$ y $p(b)\le b$. Luego, tenemos que: $a^2-a\le a^2-p(a)=p(b)^2-b$. Como $a>1$, tenemos que $a^2>a \Rightarrow a^2-a>0$.

Luego tenemos que: $0<p(b)^2-b \Rightarrow b<p(b)^2$.

Si $b$ no fuese primo, entonces existe un primo $q$ tal que: $p(b)q \mid b$, de donde, recordando que $p(b)$ es el menor primo que divide a $b$: $b\geq p(b)q\geq p(b)^2$. Pero teníamos que $b<p(b)^2$. Luego, $b$ es primo, por lo que: $b=p(b)$.

Reemplazando en la ecuación original:

$a^2+b=p(a)+b^2 \Rightarrow a^2-b^2=p(a)-b \Rightarrow (a+b)(a-b)=p(a)-b$.

De donde: $a+b \mid p(a)-b$.

Si $p(a)-b\neq 0$, entonces: $a+b \le \mid p(a)-b\mid$

Si $p(a)-b>0$, luego $a+b\le p(a)-b\Rightarrow a+2b\le p(a)$. Pero $a<a+2b\le p(a)$, cuando $p(a)\le a$, contradicción.

Si $b-p(a)>0$, entonces $a+b\le b-p(a) \Rightarrow a+p(a)\le 0$, pero $a+p(a)>0$, contradicción.

Luego, $p(a)=b=p(b)$. Reemplazando en la ecuación original:

$a^2+b=b+b^2\Rightarrow a=b=p(a)=p(b)$.

Notemos entonces que $a$ y $b$ son números primos iguales.

Podemos verificar entonces que toda pareja $(a,b)$ con $a=b$ primos cumple.

Luego, las parejas $(a,b)$ que cumplen son $(p,p)$, donde $p$ es un número primo.

"No se olviden de entregar la prueba antes de irse..."
Avatar de Usuario
Elsa Muray

OFO - Medalla de Bronce-OFO 2018
Mensajes: 23
Registrado: Vie 26 Ene, 2018 3:10 pm
Medallas: 1
Nivel: 1
Ubicación: La Plata

Re: OFO 2018 Problema 6

Mensaje sin leer por Elsa Muray »

Quedé tan manija que ya estoy preparando la OFO $2021$
Spoiler: mostrar
Si $n$ es primo $p(n)=n$, caso contrario puedo escribir $n=pq$ con $p$ y $q$ ambos mayores que $1$, pero sabemos que la función que va del conjunto de los divisores de $n$ en los divisores de $n$ dada por $f(a)=n/a$ es una biyección, luego, para cada divisor de $n$ menor que la raíz cuadrada de $n$ existe uno mayor que su raíz cuadrada, y viceversa (en el peor de los casos para un $a$ puede pasar que $p(a)=a$ si $n=a^2$). Pero entonces o bien $p$ o bien $q$, alguno es menor o igual que la raíz cuadrada de $n$, por lo que se ve trivialmente que $p(n)\leq \sqrt{n}$ si $n$ no es primo.
Vamos a ver que onda separando en casitos el problema:
Si $a$ y $b$ son compuestos:
$a^2+b=p(a)+p(b)^2\leq \sqrt{a}+(\sqrt{b})^2$ y nos queda que $a^2\leq \sqrt{a}$ con lo que $a$ debería ser $1$ (ya que es entero), ABSURDO porque partimos de que era compuesto.
Si $a$ y $b$ son primos:
$a^2+a=a+b^2$, con lo que $a^2-b^2=(a+b)(a-b)=a-b$, luego $a+b=1$ (ABSURDO!) o $a-b=0$, con lo que $a=b$ y los pares $(a,a)$ con $a$ primo cumplen el enunciado.
Si $a$ es primo y $b$ es compuesto:
$a^2+b=a+p(b)^2\leq a+(\sqrt{b})^2$ y queda $a^2\leq a$, pero nuevamente llegamos a $a=1$ ABSURDO.
Si $b$ es primo y $a$ es compuesto (es claro que son distintos):
Si $a>b$:
$a^2+b=p(a)+b^2$ y queda $(a+b)(a-b)=p(a)-b < a-b \leq (a-b)(a+b)$ ABSURDO.
Si $b<a$:
$a^2+b=p(a)+b^2$ y tenemos $b^2-a^2=(b+a)(b-a)=b-p(a)<b+a \leq (b+a)(b-a)$ ABSURDO.

Luego, las únicas soluciones posibles son los pares $(a,a)$ con $a$ primo.
2  
Responder