Nacional 2012 P2 N3

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

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Mención-OFO 2021
Mensajes: 388
Registrado: Sab 17 Sep, 2011 8:01 pm
Medallas: 4
Nivel: Exolímpico
Ubicación: Villa Ramallo, Buenos Aires

Nacional 2012 P2 N3

Mensaje sin leer por julianferres_ »

Determinar todos los números naturales $n$ para los que existen $2n$ enteros positivos distintos $x_1,\ldots ,x_n,y_1,\ldots ,y_n$ tales que el producto$$\left (11x_1^2+12y_1^2\right )\left (11x_2^2+12y_2^2\right )\cdots \left (11x_n^2+12y_n^2\right )$$es un cuadrado perfecto.
Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 563
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Re: Nacional 2012 P2 N3

Mensaje sin leer por Nacho »

Me re gustó :P
Spoiler: mostrar
Afirmo que para todo [math] par existen números, y que para [math] impar no.

En efecto, exploremos el caso [math]. La desigualdad de Cauchy-Schwarz nos dice que
[math]

con igualdad si y sólo si [math] con [math] constante. Tomamos el caso de igualdad pues es un cuadrado perfecto. Luego tenemos infinitas cuadrúplas [math] que cumplen.

Para todo [math] par, lo podemos partir en varios grupos de dos productos así, que podemos hacer que sean cuadrados perfectos. Por lo tanto, para todo [math] par se puede lograr el objetivo.

Sólo resta ver que es imposible para [math] impar. Supongamos que existen tuplas [math] y tomemos la que tiene suma mínima. Para ello, miremos al producto módulo [math]. Nos queda que:
[math]
Notemos que [math]. Luego, si [math] para todo [math], tenemos que [math], que no es un residuo cuadrático. Entonces [math] para algún [math], y así [math].

Ahora, analicemos el producto [math]. Notemos que [math] dado que si lo dividiera, podríamos tomar la misma tupla pero con [math] e [math], que seguiría dando un cuadrado perfecto y tendría suma menor. Entonces [math].

Como el producto debe ser un cuadrado perfecto, debemos tener que [math] divide al producto de todos los otros factores exceptuando [math] y así mirando módulo [math] tenemos que [math] para algún [math], de donde [math]. Nuevamente vamos a tener que [math].

Consideremos todo el producto, pero dividamos a los factores [math] y [math] por [math]. El producto nos queda:
[math]
Mirando nuevamente módulo [math], vamos a ver que [math] divide a alguno de los [math], con [math]. Si continuamos realizando este procedimiento, vamos viendo que siempre encontramos pares de números [math] tal que [math] los divide a los dos y los descartamos. Pero como [math] es impar, nos va a quedar un número al final. Por lo que llegamos al absurdo, y estamos. [math]
1  
"Though my eyes could see I still was a blind man"
Avatar de Usuario
Prillo

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 401
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Nacional 2012 P2 N3

Mensaje sin leer por Prillo »

Spoiler: mostrar
Usamos el siguiente lema: si un número es congruente con [math] módulo [math] entonces tiene una cantidad impar de divisores primos congruentes con [math] módulo [math] (contando repeticiones). La demostración de este hecho es sencilla: para un entero positivo [math] sea [math] la cantidad de sus factores primos congruentes con [math] módulo [math] y sea [math] la cantidad de sus factores primos conruentes con [math] módulo [math]. Luego es evidente que [math], y como [math] por suposición, entonces [math] debe ser impar. La idea es probar que este resultado vale también para los números de la forma [math]. Sea [math] e [math] donde [math] y [math] son impares. Supongamos que [math]. Luego [math]. Como [math] (pues [math] es impar), por el lema nuestra afirmación vale en este caso. Supongamos ahora que [math]. Luego [math]. Notemos que [math], por lo cual al mirar el segundo factor módulo [math] obtenemos que [math] y nuevamente por el lema nuestra afirmación vale en este caso. El último caso es cuando [math]. Tenemos que [math]. Esta vez [math], pero no todo está perdido. Notemos que todo número impar elevado al cuadrado tiene resto [math] en la división por [math]. Luego [math] y podemos escribir [math] y ahora sí el factor derecho es congruente con [math] módulo [math], lo cual prueba nuestra afirmación en este último caso. Habiendo analizado todos los casos, hemos probado la afirmación.

Volviendo al problema original, usando el resultado anterior se deduce fácilmente que [math] debe ser par. En efecto, cada factor de la forma [math] aporta una cantidad impar de divisores primos congruentes con [math] módulo [math] al producto total. Pero para que el producto total sea un cuadrado perfecto, esta cantidad tiene que ser par, lo cual fuerza a que haya una cantidad par de estos factores. Así, [math] debe ser par. Por otra parte, es fácil ver que si [math] es par existen soluciones: Basta tomar los pares [math]. El producto nos queda igual a [math], que si [math] es par es un cuadrado perfecto.
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 FOFO 14 años - Mención-FOFO 14 años
Mensajes: 1128
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: Exolímpico
Contactar:

Re: Nacional 2012 P2 N3

Mensaje sin leer por drynshock »

Spoiler: mostrar
Caso $n$ par:
Tomando $x_i = 2i-1, y_i = 2(2i-1)$ tenemos

$$\prod_{i=1}^{n}(11(2i-1)^2+12(2(2i-1))^2) = \prod_{i=1}^{n}(2i-1)^2.\prod_{i=1}^{n}(11+12.4) = [(2n-1)!!]^2(59)^{n}$$

Y como $n$ es par, entonces eso es un cuadrado perfecto.

$\blacksquare$

Caso $n$ impar:

Antes de seguir con el problema, digamos que $d = (x, y)$, siendo $(x, y)$ el máximo común divisor, luego $x = d.x', y = d.y' \Rightarrow 11x^2+12y^2 = d^2(11x'^2+12y'^2)$, por lo tanto $v_p(11x^2+12y^2) \equiv v_p(11x'^2+12y'^2) \pmod 2$, es decir que la cantidad de factores primos $\pmod 2$ (que es lo que nos interesa para que sea un cuadrado perfecto) no varia. Por lo tanto podemos asumir que $x_i, y_i$ son coprimos.

Notar que

$$\prod_{i=1}^{n}(11x_i^2+12y_i^2) \equiv 11^n(\prod_{i=1}^{n}(x_i))^2 \equiv -(\prod_{i=1}^{n}(x_i))^2 \pmod 3$$

Entonces, si ningún $x_i$ es múltiplo de $3$ sabemos que el producto al cuadrado tiene resto $1 \pmod 3$ (pues los cuadrados perfectos $\pmod 3$ dejan resto $0$ o $1$, siendo $0$ si solo si el numero es múltiplo de $3$). Y en ese caso $-(\prod_{i=1}^{n})^2 \equiv 2 \pmod 3$ el cual no es un cuadrado perfecto, absurdo. Por lo tanto existe un $x_i$ tal que $x_i \equiv 0 \pmod 3$. WLOG tomemos $x_n = 3x_n'$. Luego, $11x_n^2+12y_n^2 = 3(33x_n'^2+4y_n^2)$ y como $x_n$, e $y_n$ son coprimos, entonces $3 \nmid y_n$ y por lo tanto $33x_n'^2+4y_n^2 \equiv 1 \pmod 3$. Pero entonces, el producto hasta el momento tiene un solo factor $3$, y para que sea un cuadrado perfecto debe tener una cantidad par, por consiguiente existe otro $x_i$, distinto a $x_n$, que también es múltiplo de $3$. WLOG tomamos $x_{n-1} = 3x_{n-1}'$.

El producto se reescribe como

$$3^2(33x_n'^2+4y_n^2)(33x_{n-1}'^2+4y_{n-1}^2)\prod_{i=1}^{n-2}(11x_i^2+12y_i^2)$$

Pero, notar dos cosas, $3^2$ ya es un cuadrado perfecto de por si, entonces el resto del producto también ha de serlo. Y $(33x_n'^2+4y_n^2)(33x_{n-1}'^2+4y_{n-1}^2) \equiv 1 \pmod 3$, entonces con un razonamiento análogo al anterior, tenemos que

$$\prod_{i=1}^{n-2}(11x_i^2+12y_i^2) \equiv -(\prod_{i=1}^{n-2}x_i)^2 \pmod 3$$

Entonces, tenemos el mismo problema que antes pero esta vez para $n-2$, luego, si seguimos repitiendo este proceso vamos a obtener el mismo caso problema para $n-4$ lo mismo para $n-6$ y así siguiendo hasta $1$ (pues $n$ es impar), dejándonos con que $-(11x_1^2+12y_1^2) \pmod 3$ es un cuadrado perfecto, por lo que $x_1 = 3x_1'$ y entonces todos los $x_i$ tienen el factor $3$, lo cual implica que el producto final tiene $3^{n}$ factores $3$, y por lo tanto el producto no es un cuadrado perfecto.

Concluimos que no se puede para $n$ impar.
$\blacksquare$
Spoiler: mostrar
Esto intente usarlo para resolver el problema y no me sirvió, me pareció lindo así que lo comparto igual.

Supongamos que la ecuación $11x^2+12y^2 = z^2$ tiene solución, dado que $x, y, z$ son enteros positivos, existe una terna $(x, y, z)$ tal que $x+y+z$ sea mínimo, entonces fijemos los valores de $x, y, z$ para que la suma sea mínima.

$$11x^2+12y^2 = z^2 \iff 4.3(x^2+y^2) = z^2+x^2$$

Pero por El teorema de Navidad de Fermat un numero puede expresarse como suma de cuadrados solo si sus factores primos de la forma $4k+3$ están elevados a una potencia par, luego como en el LHS tenemos el factor $3$, sabemos que $x^2+y^2 \equiv 0 \pmod 3$ y como los residuos cuadráticos $\pmod 3$ son $0, 1$, la única forma de que la suma nos de $0$ es que $x \equiv y \equiv 0 \pmod 3 \Rightarrow x = 3x', y = 3y'$ y entonces la ecuación se reescribe como $11.9x'^2+12.9y'^2 = z^2$ de donde $z = 3z' \Rightarrow 11x'^2+12y'^2 = z'^2$. Se sigue, que acabamos de generar una solución con suma mas chica (pues $x'+y'+z' < 3(x'+y'+z') = x+y+z$) lo cual nos lleva a un absurdo porque $x+y+z$ era mínimo.

Concluimos que la ecuación no tiene solución.

$\blacksquare$
@Bauti.md ig
Winning is first place, anything else is losing.
"Alexandra Trusova"
Responder