FOFO 11 Años - Problema 9

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
Mensajes: 152
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

FOFO 11 Años - Problema 9

Mensaje sin leer por AgusBarreto »

Hallar todos los enteros positivos $n$ para los que existen enteros positivos $a_1,\ldots ,a_n,b_1,\ldots ,b_n$ tales que$$(a_1^2+\cdots +a_n^2)(b_1^2+\cdots +b_n^2)-(a_1b_1+\cdots +a_nb_n)^2=n.$$

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
Mensajes: 152
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: FOFO 11 Años - Problema 9

Mensaje sin leer por AgusBarreto »

Aquí publicaremos la solución oficial.

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
Mensajes: 1719
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 11
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: FOFO 11 Años - Problema 9

Mensaje sin leer por Gianni De Rico »

Respuesta:
Spoiler: mostrar
Los únicos $n$ para los que se puede son $n=3$ y $n=4$.
Solución:
Spoiler: mostrar
Para $n=1$ no se puede porque $a_1^2b_1^2-(a_1b_1)^2=0\neq 1$. Para $n=2$ no se puede porque $(a_1^2+a_2^2)(b_1^2+b_2^2)-(a_1b_1+a_2b_2)^2=a_1^2b_2^2-2a_1a_2b_1b_2+a_2^2b_1^2=(a_1b_2-a_2b_1)^2$, que es un cuadrado perfecto, pero $2$ no es un cuadrado perfecto. Para $n=3$ tenemos el ejemplo $a_1=3$, $a_2=5$, $a_3=2$, $b_1=4$, $b_2=7$, $b_3=3$. Para $n=4$ tenemos el ejemplo $a_1=a_2=2$ y $a_3=a_4=b_1=b_2=b_3=b_4=1$.

Supongamos que se puede para algún $n\geq 5$. La factorización que hicimos para $n=2$ se puede hacer en general, nos queda que$$(a_1^2+\cdots +a_n^2)(b_1^2+\cdots +b_n^2)-(a_1b_1+\cdots +a_nb_n)^2=\sum \limits _{i=1}^{n-1}\left (\sum \limits _{j=i+1}^n(a_ib_j-a_jb_i)^2\right ).$$Por comodidad vamos a llamar $S$ a esta suma. Sea $c_i=\dfrac{a_i}{b_i}$, para $i=1,\ldots ,n$; tenemos entonces que si $c_i=c_j$ para $i\neq j$, entonces $(a_ib_j-a_jb_i)^2$; y si $c_i\neq c_j$ para $i\neq j$, entonces $(a_ib_j-a_jb_i)^2\geq 1$ (porque $a_ib_j-a_jb_i\neq 0$ y es entero).
Entonces queremos contar la cantidad de veces que pasa que $c_i\neq c_j$, porque si son muchas (más de $n$), nos da $S>n$.
Supongamos que los $c_i$ toman $k$ valores distintos $d_1,\ldots ,d_k$, y que cada $d_i$ aparece $r_i$ veces. Entonces se cumple que $r_1+r_2+\cdots +r_k=n$ porque es la cantidad de $c_i$ que hay. Reordenando de ser necesario, podemos suponer que $r_1\geq r_2\geq \cdots \geq r_k$. Si $r_1=1$ entonces no hay dos $c_i$ iguales, así que $(a_ib_j-a_jb_i)^2\geq 1$ siempre, y como $S$ tiene exactamente $\binom{n}{2}$ términos, entonces $S\geq \binom{n}{2}=\frac{n(n-1)}{2}>n$ (pues $n-1>2$ al ser $n\geq 5$). Entonces tiene que ser $r_1>1$.
Separamos en casos:
  • Caso $1$: $k\geq 3$
    Tenemos que la cantidad de veces que $(a_ib_j-a_jb_i)^2=0$ es la cantidad de veces que $a_ib_j=a_jb_i$, que es la cantidad de veces que $\dfrac{a_i}{b_i}=\dfrac{a_j}{b_j}$, es decir que es la cantidad de veces que $c_i=c_j$. Tenemos $\binom{r_1}{2}$ formas de elegir $i,j$ tales que $c_i=c_j=d_1$, $\binom{r_2}{2}$ formas de elegir $i,j$ tales que $c_i=c_j=r_2$, y así siguiendo, tenemos en total$$\binom{r_1}{2}+\binom{r_2}{2}+\cdots +\binom{r_k}{2}$$formas de elegir $i,j$ tales que $c_i=c_j$.
    Ahora, tenemos la siguiente desigualdad$$\binom{A}{C}+\binom{B}{C}<\binom{A+B}{C}$$que se cumple porque $\binom{A+B}{C}$ cuenta todas las formas de elegir $C$ elementos entre $A+B$ posibles, que son todas las formas de elegir $C$ elementos entre los $A$ primeros, que son $\binom{A}{C}$, más todas las formas de elegir $C$ elementos entre los $B$ últimos, que son $\binom{B}{C}$ más todas las formas de elegir $C$ elementos sacando algunos de los $A$ primeros y otros de los $B$ últimos, que son más que $0$. Para una demostración más formal de esto, pueden ver la Identidad de Vandermonde.
    Bueno, entonces usando eso varias veces tenemos que$$\binom{r_1}{2}+\binom{r_2}{2}+\cdots +\binom{r_k}{2}<\binom{r_1}{2}+\binom{r_2}{2}+\cdots +\binom{r_{k-1}+r_k}{2}<\binom{r_1}{2}+\binom{r_2}{2}+\cdots +\binom{r_{k-2}+r_{k-1}+r_k}{2}$$y así hasta obtener$$\binom{r_1}{2}+\binom{r_2}{2}+\cdots +\binom{r_k}{2}<\binom{r_1}{2}+\binom{r_2+r_3+\cdots +r_k}{2}.$$Pero esta última expresión cuenta la cantidad de formas de elegir $2$ elementos de entre $r_1$ disponibles más la cantidad de formas de elegir dos elementos de entre $r_2+r_3+\cdots +r_k$ disponibles, si le sumamos a eso la cantidad de formas de elegir un elemento de entre $r_1$ disponibles y un elemento de entre $r_2+r_3+\cdots +r_k$ disponibles, que es $r_1(r_2+r_3+\cdots r_k)$, obtenemos la cantidad total de formas de elegir dos elementos entre $r_1+r_2+r_3+\cdots +r_k=n$, es decir, $\binom{n}{2}$. Nos queda entonces que$$\binom{r_1}{2}+\binom{r_2+r_3+\cdots +r_k}{2}=\binom{n}{2}-r_1(r_2+r_3+\cdots +r_k)$$(de nuevo, una demostración más formal de esto puede hacerse con la Identidad de Vandermonde).
    Entonces la cantidad de $(a_ib_j-a_jb_i)^2$ que son $0$ es menor que $\binom{n}{2}-r_1(r_2+r_3+\cdots +r_k)$, y como hay $\binom{n}{2}$ de estas expresiones en total, la cantidad que son mayores o iguales que $1$ es al menos $r_1(r_2+r_3+\cdots +r_k)+1$. Poniendo $r_1=x$ y $r_2+r_3+\cdots +r_k=y$, como $xy+1=(x-1)(y-1)+x+y=(x-1)(y-1)+n$, nos queda que$$r_1(r_2+r_3+\cdots +r_k)+1=(r_1-1)(r_2+r_3+\cdots r_k-1)+n>n$$pues $r_1>1$ y $r_2+r_3+\cdots +r_k>1$ al ser todos los $r_i\geq 1$ y $k\geq 3$.
    Entonces en $S$ hay más de $n$ términos que son mayores o iguales que $1$, con lo que $S>n$. Este caso no puede pasar.
  • Caso $2$: $k=2$
    De la misma forma que antes, tenemos que la cantidad de $(a_ib_j-a_jb_i)^2$ que no son $0$ es\begin{align*}\binom{r_1}{2}+\binom{r_2}{2} & =\frac{r_1(r_1-1)}{2}+\frac{r_2(r_2-1)}{2} \\
    & =\frac{r_1^2+r_2^2-(r_1+r_2)}{2} \\
    & =\frac{r_1^2+r_2^2-n}{2} \\
    & =\frac{(r_1+r_2)^2-n-2r_1r_2}{2} \\
    & =\frac{(r_1+r_2)^2-n}{2}-r_1r_2 \\
    & =\frac{n^2-n}{2} \\
    & =\frac{n(n-1)}{2}-r_1r_2 \\
    & =\binom{n}{2}-r_1r_2
    \end{align*}con lo que la cantidad de $(a_ib_j-a_jb_i)^2$ que son mayores o iguales que $1$ es$$r_1r_2=\frac{2r_1\cdot 2r_2}{4}=\frac{(n-r_2+r_1)(n-r_1+r_2)}{4}=\frac{n^2-(r_1-r_2)^2}{4}.$$Ahora, notemos que $r_1-r_2\equiv r_1-r_2+2r_2\equiv r_1+r_2\equiv n\pmod{2}$, y como $r_1-r_2<r_1+r_2=n$, entonces $r_1-r_2=n-2m$, con $m\in \mathbb{N}$.
    Si $m\geq 2$, entonces $r_1-r_2\leq n-4$, de modo que $(r_1-r_2)^2\leq (n-4)^2$ (ya que $r_1-r_2\geq 0$ por definición), entonces$$r_1r_2=\frac{n^2-(r_1-r_2)^2}{4}\geq \frac{n^2-(n-4)^2}{4}=2n-4>n$$donde la última desigualdad vale pues $n\geq 5$. Esto implica que $S>n$, absurdo, luego, debe ser $m=1$, es decir, $r_1-r_2=n-2$.
    Tenemos entonces que la cantidad de $(a_ib_j-a_jb_i)^2$ que son mayores o iguales que $1$ es$$r_1r_2=\frac{n^2-(n-2)^2}{4}=n-1.$$Sean $x_1,x_2,\ldots ,x_{n-1}$ los valores de los $(a_ib_j-a_jb_i)^2$ que son al menos $1$, con $x_i\neq x_j$ si $i\neq j$, entonces$$x_1^2+x_2^2+\cdots +x_{n-1}^2=S=n$$pero como los $x_i$ son cuadrados perfectos, si son mayores que $1$ entonces son mayores o iguales que $4$, luego, si hay alguno de ellos que es mayor que $1$, resulta$$n=x_1^2+x_2^2+\cdots +x_{n-1}^2\geq 4+\underbrace{1+1+\cdots +1}_{n-1\text{ veces}}=n+3$$lo que es absurdo, y si son todos iguales a $1$ entonces $n=x_1^2+x_2^2+\cdots +x_n^2=n-1$, que de nuevo es un absurdo. Este caso no puede pasar.
  • Caso $3$: $k=1$
    Entonces todos los $c_i$ son iguales, con lo que $(a_ib_j-a_jb_i)^2=0$ para todos $i,j$, es decir que $n=S=0$. Este caso no puede pasar.
Habiendo visto todos los casos, concluimos que no se puede para $n\geq 5$.

Entonces los únicos $n$ para los que se puede son $n=3$ y $n=4$.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Responder