Provincial 2023 N3 P1

Problemas que aparecen en el Archivo de Enunciados.
Felibauk

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 OFO - Medalla de Oro-OFO 2023
FOFO 13 años - Medalla-FOFO 13 años OFO - Oro perfecto-OFO 2024 FOFO Pascua 2024 - Jurado-FOFO Pascua 2024
Mensajes: 73
Registrado: Dom 19 Ene, 2020 12:43 am
Medallas: 13
Nivel: 1

Provincial 2023 N3 P1

Mensaje sin leer por Felibauk »

Un entero positivo se dice simple si se puede escribir como suma de dos enteros positivos mayores que $1$ y coprimos entre sí. Por ejemplo, $102=35+72$ es simple pues $35$ y $72$ son coprimos ya que el único divisor común es el $1$.
Determinar todos los enteros positivos simples.
Aclaración: Dos enteros positivos $a,b$ son coprimos si el máximo común divisor entre $a$ y $b$ es $1$.
"La matemática es para pensar. El fútbol es para sacar mi instinto animal y decirle al árbitro hdp te voy a m4t4r." Anónimo
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024
Mensajes: 791
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 3
Nivel: 3
Contactar:

Re: Provincial 2023 N3 P1

Mensaje sin leer por drynshock »

1) Conjetura de Gold Bach (light version)

2) Me senti Perelman resolviendo esto

3) Orgulloso de ser el primero en subir la solución

Postulado de Bertrand
Spoiler: mostrar
Dado un numero entero $n > 1$, entonces existe un primo $p$ tal que:

$$n < p < 2n$$

O equivalentemente, lo que vamos a usar nosotros es con $n > 2$:

$$\frac{n}{2} < p < n$$
Solución:
Spoiler: mostrar
El problema nos dice que:
$n = a+b$
Con $mcd(a, b) = 1$, $n > 1$ y $a, b \in \mathbb Z^+$. Para evitar problemas con los casos bases podemos considerar $n, a, b$ arbitrariamente grandes.

Luego, tomemos $p$ tal que:

$$\frac{n}{2} < p < n$$
$$n = n - p + p$$

La primera afirmación es cierta por el teorema de Bertrand y la segunda simplemente sumamos y restamos $p$. Ahora veamos que por algoritmo de Euclides: $mcd(n-p, p) = mcd(n, p) \Rightarrow mcd(n, p) = 1 \vee mcd(n, p) = p$. Si miramos este ultimo caso, tenemos que para un entero $m$ se cumple que $p | n \Rightarrow n = p.m \Rightarrow \frac{p.m}{2} < p \Rightarrow m < 2 \Rightarrow m = 1 \Rightarrow p = n$ lo cual es una contradicción ya que $p < n$, luego $mcd(n-p, p) = 1$.

Esta claro que $p \neq 1$ pero eventualmente $n-p = 1 \Rightarrow n = p+1$. Para este caso tomemos un primo $q$ tal que:
$$\frac{p}{2} < q < p$$
$$n = p+1 = p+1-q + q$$

Se sigue que $mcd(p+1-q, q) = mcd(p+1, q) \Rightarrow mcd(p+1, q) = 1 \vee mcd(p+1, q) = q$. Si ocurre el primer caso, el problema esta termimado ya que $p+1-q>1$ y $q>1$. Analizando el ultimo caso tenemos que para un entero $m$ se cumple: $q | p+1 \Rightarrow p+1 = q.m \Rightarrow \frac{q.m-1}{2} < q \Rightarrow q.m < 2q +1$ de lo cual se desprende que $m = 1 \vee m = 2$. En caso que $m = 1$ entonces $q = p+1$ y como cambian de paridad y ambos son primos, entonces la única solución es $q = 3 \land p = 2$ pero $q < p$, clara contradicción. Se sigue que $m = 2 \Rightarrow p + 1 = 2q$

Hasta el momento tenemos $n = p+1 = 2q$. Ahora veamos que $2q = 2q - 3 + 3$ y $mcd(2q- 3, 3) = mcd(q, 3) = 1 \land q \neq 3$. Finalmente, nos queda checkear que $2q-3 > 1 \Rightarrow q > 4$. Entonces acabamos de construir un ejemplo para todo $n > 4 \land n \neq 6$. Es fácil ver que no existe otra forma de expresar a estos números excluidos como suma de dos coprimos, lo cual termina el problema.

$$n = a+b$$

$\blacksquare$
@Bauti.md ig
First place is winning, anything else is losing.
"Alexandra Trusova"
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024
Mensajes: 791
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 3
Nivel: 3
Contactar:

Re: Provincial 2023 N3 P1

Mensaje sin leer por drynshock »

drynshock escribió: Jue 20 Jun, 2024 3:58 am 1) Conjetura de Gold Bach (light version)

2) Me senti Perelman resolviendo esto

3) Orgulloso de ser el primero en subir la solución

Postulado de Bertrand
Spoiler: mostrar
Dado un numero entero $n > 1$, entonces existe un primo $p$ tal que:

$$n < p < 2n$$

O equivalentemente, lo que vamos a usar nosotros es con $n > 2$:

$$\frac{n}{2} < p < n$$
Solución:
Spoiler: mostrar
El problema nos dice que:
$n = a+b$
Con $mcd(a, b) = 1$, $n > 1$ y $a, b \in \mathbb Z^+$. Para evitar problemas con los casos bases podemos considerar $n, a, b$ arbitrariamente grandes.

Luego, tomemos $p$ tal que:

$$\frac{n}{2} < p < n$$
$$n = n - p + p$$

La primera afirmación es cierta por el teorema de Bertrand y la segunda simplemente sumamos y restamos $p$. Ahora veamos que por algoritmo de Euclides: $mcd(n-p, p) = mcd(n, p) \Rightarrow mcd(n, p) = 1 \vee mcd(n, p) = p$. Si miramos este ultimo caso, tenemos que para un entero $m$ se cumple que $p | n \Rightarrow n = p.m \Rightarrow \frac{p.m}{2} < p \Rightarrow m < 2 \Rightarrow m = 1 \Rightarrow p = n$ lo cual es una contradicción ya que $p < n$, luego $mcd(n-p, p) = 1$.

Esta claro que $p \neq 1$ pero eventualmente $n-p = 1 \Rightarrow n = p+1$. Para este caso tomemos un primo $q$ tal que:
$$\frac{p}{2} < q < p$$
$$n = p+1 = p+1-q + q$$

Se sigue que $mcd(p+1-q, q) = mcd(p+1, q) \Rightarrow mcd(p+1, q) = 1 \vee mcd(p+1, q) = q$. Si ocurre el primer caso, el problema esta termimado ya que $p+1-q>1$ y $q>1$. Analizando el ultimo caso tenemos que para un entero $m$ se cumple: $q | p+1 \Rightarrow p+1 = q.m \Rightarrow \frac{q.m-1}{2} < q \Rightarrow q.m < 2q +1$ de lo cual se desprende que $m = 1 \vee m = 2$. En caso que $m = 1$ entonces $q = p+1$ y como cambian de paridad y ambos son primos, entonces la única solución es $q = 3 \land p = 2$ pero $q < p$, clara contradicción. Se sigue que $m = 2 \Rightarrow p + 1 = 2q$

Hasta el momento tenemos $n = p+1 = 2q$. Ahora veamos que $2q = 2q - 3 + 3$ y $mcd(2q- 3, 3) = mcd(q, 3) = 1 \land q \neq 3$. Finalmente, nos queda checkear que $2q-3 > 1 \Rightarrow q > 4$. Entonces acabamos de construir un ejemplo para todo $n > 4 \land n \neq 6$. Es fácil ver que no existe otra forma de expresar a estos números excluidos como suma de dos coprimos, lo cual termina el problema.

$$n = a+b$$

$\blacksquare$
Drynshock, haceme el favor de borrar la cuenta
Spoiler: mostrar
Si $n$ es impar: $n = (2) + (n - 2)$ con $a = 2$, $b = n-2$ Formando así todos los impares mayores o iguales a $5$

Si $n$ es par:

Caso 1: $\frac{n}{2}$ es par $n = (\frac{n}{2}+1) + (\frac{n}{2} - 1)$ Entonces si $a = \frac{n}{2}+1$ y $b = \frac{n}{2}-1$ estamos ya que estos dos son claramente coprimos. Dado que $a,b >1 \Rightarrow \frac{n}{2}-1 > 1 \iff n > 4$.

Caso 2: $\frac{n}{2}$ es impar: $n = (\frac{n}{2}+2) + (\frac{n}{2} -2)$ Con $a = \frac{n}{2}+2$ y $b = \frac{n}{2}-2$ y $\frac{n}{2} - 2 > 1 \iff n > 6$

Es fácil ver que para $1, 2, 3, 4, 6$ no hay solución.
@Bauti.md ig
First place is winning, anything else is losing.
"Alexandra Trusova"
Responder