¿Por qué funciona la solución de un párrafo al problema 6 de la OMI en 1988?
Emanouil Atanassov, que se dice que completó el problema de la OMI "más difícil" en un solo párrafo y recibió el premio especial, dio la prueba que se cita a continuación:
Pregunta: Sean ayb enteros positivos tales que $ab+1$ divide $a^2+b^2$ Muestra esa $\frac{a^2+b^2}{ab+1}$ es el cuadrado de un número entero
Prueba: $k=\frac{a^2+b^2}{ab+1} \implies a^2-kab+b^2=k, k\in \mathbb{Z}$ Asumir $k$no es un cuadrado perfecto. Tenga en cuenta que para cualquier solución integral$(a,b)$ tenemos $a>0, b>0$ya que k no es un cuadrado perfecto. Dejar$(a,b)$ ser una solución integral con $a>0, b>0$ y $a+b$mínimo. Produciremos a partir de ella otra solución integral$(a',b)$ con $a'>0 , \ b>0$ y $a'+b<a+b$. Contradicción (omitimos el argumento para llegar a$(a',b)$)
$a'=0$ es suficiente para $k$siendo un cuadrado, pero no es cierto en general. Esta prueba parece implicar$a'=0$ para todas las soluciones $(a,b)$. El único supuesto que se contradice es la minimidad de$a+b$, no la suposición $k$no es un cuadrado perfecto. ¿Cómo se sigue trivialmente la afirmación de esta prueba?
EDITAR: Aquí está la prueba modificada, pero sin la suposición $k$ no es un cuadrado perfecto.
$k=\frac{a^2+b^2}{ab+1} \implies a^2-kab+b^2=k, k\in \mathbb{Z}$ Dejar $(a,b)$ ser una solución integral con $a>0, b>0$ y $a+b$mínimo. Produciremos a partir de ella otra solución integral$(a',b)$ con $a'>0 , \ b>0$ y $a'+b<a+b$. Contradicción (omitimos el argumento para llegar a$(a',b)$)
También he eliminado la segunda oración, porque $a,b>0$se da en la pregunta. ¿Qué implica esta prueba que la primera no?
Respuestas
- Si hay soluciones $(a,b)$ para cual $k$ no es un cuadrado perfecto, entonces $a,b>0$.
- Además, si hay soluciones $(a,b)$ para cual $k$ no es un cuadrado perfecto, entonces habrá, entre esas soluciones, una para la cual $a+b$ es mínimo.
- Entonces el autor encuentra otra solución $(a',b)$ con $a'<a$, lo que implica que $a'+b<a+b$.
- Pero eso es imposible, ya que asumíamos que $(a,b)$ fue la solución para la cual $a+b$ toma el valor más pequeño.
Solución completa textualmente de en.wiki/Vieta jumping :
Salto estándar de Vieta
El concepto de salto estándar de Vieta es una prueba por contradicción y consta de los siguientes tres pasos:${}^{[1]}$
- Asumir ante una contradicción que existe alguna solución que viola los requisitos dados.
- Tome la solución mínima de acuerdo con alguna definición de minimidad.
- Demuestre que esto implica la existencia de una solución más pequeña, por lo tanto, una contradicción.
Ejemplo
Problema n. ° 6 en la OMI 1988: $a$ y $b$ ser enteros positivos tales que $ab + 1$ divide $a^2 + b^2$. Pruebalo$\frac{a^2 + b^2}{ab + 1}$ es un cuadrado perfecto.${}^{[2]}$${}^{[3]}$
- Arreglar algo de valor $k$que es un número entero positivo no cuadrado. Suponga que existen enteros positivos$(a, b)$ para cual $k = \frac{a^2 + b^2}{ab + 1}$.
- Dejar $(A, B)$ ser enteros positivos para los cuales $k = \frac{A^2 + B^2}{AB + 1}$ y tal que $A + B$ se minimiza y sin pérdida de generalidad asumir $A \ge B$.
- Fijación $B$, reemplazar $A$ con la variable $x$ ceder $x^2 – (kB)x + (B^2 – k) = 0$. Sabemos que una raíz de esta ecuación es$x_1 = A$. Por las propiedades estándar de las ecuaciones cuadráticas, sabemos que la otra raíz satisface$x_2 = kB – A$ y $x_2 = \frac{B^2 – k}{A}$.
- La primera expresión para $x_2$ muestra que $x_2$ es un número entero, mientras que la segunda expresión implica que $x_2 \ne 0$ ya que $k$no es un cuadrado perfecto. Desde$\frac{x_2^2 + B^2}{x_2B + 1} = k > 0$ además se sigue que $x_2$es un número entero positivo. Finalmente,$ A \ge B$ implica que $x_2 = \frac{B^2 − k}{A} < A$ y por lo tanto $x_2 + B < A + B$, que contradice la minimidad de $A + B$.
Creo que lo he resuelto y aludiré a la prueba de Wikipedia dada en la respuesta de Alexey, ya que los argumentos son los mismos y creo que la fuente no ha sido confiable al "omitir" los pasos.
La minimidad de $A+B$se contradice. (2) y (3) son irrelevantes para$k$. (4) dice$x$ no puede ser $0$ Si $k$no es un cuadrado perfecto. Entonces$x\neq 0$. Pero si$x\neq 0$, puramente a través del álgebra, independiente de $k$siendo cuadrados o no, contradecimos la minimidad. Entonces, el quid,$(A,B)$ minimiza $A+B$. sólo si$x_2=0$. Dado que no hay un mínimo de$(A,B)$ pares cuando $k$ no es un cuadrado, podemos concluir que no existen tales pares.
Si Atanassov encontró esto tan trivial que lo mantuvo en su cabeza, sigue siendo un misterio.