jueves, 12 de julio de 2018

(389) PROBLEMA 6, IMO 1988.

PROBLEMA 6, IMO 1988.


Puesto que estamos en días de celebración de la IMO (International Mathematical Olympiad) que este año se celebra en Rumanía (aquí dejo un enlace a su web), en este artículo se abordará la resolución del problema más difícil que ha aparecido en los exámenes de la IMO.

Resultado de imagen de international mathematical olympiad
Símbolo de la IMO.

Cabe destacar que el ganador de estas olimpiadas fue el célebre matemático Terence Tao (es la persona más joven de la historia en participar en la IMO teniendo solo 10 años y obteniendo una medalla de bronce a los 10, de plata a los 11 y de oro a los 12) que en este problema consiguió una puntuación de 1/7, lo cual hace pensar que el problema posee una dificultad notable.

Resultado de imagen de Terence Tao imo

Terence Tao recibiendo la medalla de oro por parte del primer ministro de Inglaterra Bob Hawke en 1988.

Resultado de imagen de Terence Tao IMO
Terence Tao en la IMO junto con el equipo nacional.

Otra anécdota que refleja la dificultad del problema es que Arthur Engel escribió lo siguiente sobre la dificultad del problema:

Ninguno de los seis miembros del comité australiano encargado de hacer los problemas de la IMO podía resolverlo. Dos de los miembros eran esposo y esposa George y Esther Szekeres , ambos famosos solucionadores y creadores de problemas. Como se trataba de un problema teórico de números, se envió a los cuatro teóricos de números australianos más famosos. Se les pidió que trabajaran en ello durante seis horas. Ninguno de ellos pudo resolverlo en ese momento. El comité del problema lo presentó al jurado del XXIX IMO marcado con un doble asterisco, lo que significaba un que el problema en cuestión es un problema muy complejo, posiblemente demasiado difícil de plantear. Después de una larga discusión, el jurado finalmente tuvo el coraje de elegirlo como el último problema de la competición. Once estudiantes dieron soluciones perfectas.

Entre los once estudiantes que recibieron la puntuación máxima para resolver este problema estuvieron el futuro medallista Fields Ngô Bảo Châu , el profesor de matemáticas de Stanford Ravi Vakil , el profesor de Mills College Zvezdelina Stankova y el político rumano Nicuşor Dan .

El enunciado del problema es el siguiente:

Let a and b be positive integers such that ab + 1 dividesShow that:


is the square of an integer.

En la resolución de este problema se hace uso del método Vieta jumping este método es usado en teoría de números. Se hace uso de él con frecuencia para problemas en los que se da una relación entre dos enteros positivos, junto con una hipótesis para probar sus soluciones. Existen múltiples métodos del Vieta jumping, todos ellos involucran el descenso infinito al encontrar nuevas soluciones a una ecuación usando las fórmulas de Vieta.
Las
fórmulas de Vieta son fórmulas que relacionan los coeficientes de un polinomio con sumas y productos de sus raíces. Mostraré las fórmulas básicas:

Sea P(x) 
R[x] o P(x) ∈ C[x] (R y C son los conjuntos de números reales y complejos respectivamentedefinido de la siguiente manera
{\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}
(donde n  ≠ 0) por el teorema fundamental del álgebra se sabe que P(x) tiene n (no necesariamente distintas) raíces complejas 1 ,  2 , ...,  n . Las fórmulas de Vieta relacionan los coeficientes del polinomio k , k=0,..., n con las sumas finitas y los productos de sus raíces i , i= ,...,n de la siguiente manera:
{\displaystyle {\begin{cases}x_{1}+x_{2}+\dots +x_{n-1}+x_{n}=-{\dfrac {a_{n-1}}{a_{n}}}\\(x_{1}x_{2}+x_{1}x_{3}+\cdots +x_{1}x_{n})+(x_{2}x_{3}+x_{2}x_{4}+\cdots +x_{2}x_{n})+\cdots +x_{n-1}x_{n}={\dfrac {a_{n-2}}{a_{n}}}\\{}\quad \vdots \\x_{1}x_{2}\dots x_{n}=(-1)^{n}{\dfrac {a_{0}}{a_{n}}}.\end{cases}}}



Equivalentemente indicado,  el coeficiente n  -  k )-ésimo de n - k se relaciona con la suma de todos los posibles subproductos de raíces, tomados k - a la vez:
\sum _{1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n}x_{i_{1}}x_{i_{2}}\cdots x_{i_{k}}=(-1)^{k}{\frac {a_{n-k}}{a_{n}}}

para k  = 1, 2, ..., n (donde escribimos los índices k en orden creciente para asegurar que cada subproducto de raíces se use exactamente una vez).



Los lados izquierdos de las fórmulas de Vieta son las funciones simétricas elementales de las raíces.

En álgebra conmutativa los polinomios simétricos elementales de n variables 1 , ..., n  
escritos de la forma k ( 1 , ..., n ) para k = 0, 1, ..., n , están definidos por
{\ displaystyle {\ begin {aligned} e_ {0} (X_ {1}, X_ {2}, \ dots, X_ {n}) & = 1, \\ [10pt] e_ {1} (X_ {1} , X_ {2}, \ dots, X_ {n}) & = \ sum _ {1 \ leq j \ leq n} X_ {j}, \\ e_ {2} (X_ {1}, X_ {2}, \ dots, X_ {n}) & = \ sum _ {1 \ leq j <k \ leq n} X_ {j} X_ {k}, \\ e_ {3} (X_ {1}, X_ {2}, \ dots, X_ {n}) & = \ sum _ {1 \ leq j <k <l \ leq n} X_ {j} X_ {k} X_ {l}, \\\ end {aligned}}}

y así sucesivamente, terminando con

{\ displaystyle e_ {n} (X_ {1}, X_ {2}, \ dots, X_ {n}) = X_ {1} X_ {2} \ cdots X_ {n}.}


en general, para 
k ≥ 0 se define

{\ displaystyle e_ {k} (X_ {1}, \ ldots, X_ {n}) = \ sum _ {1 \ leq j_ {1} <j_ {2} <\ cdots <j_ {k} \ leq n} X_ {j_ {1}} \ dotsm X_ {j_ {k}},}

de modo que k ( 1 , ..., n ) = 0 si k > n.

Por lo tanto, para cada entero positivo k menor que o igual a n existe exactamente un polinomio simétrico elemental de grado k en variables. Para formar el que tiene grado k , tomamos la suma de todos los productos de k -subconjuntos de las n variables.



Los polinomios simétricos elementales aparecen cuando ampliamos una factorización lineal de un polinomio monico: tenemos la identidad

\ prod _ {{j = 1}} ^ {n} (\ lambda -X_ {j}) = \ lambda ^ {n} -e_ {1} (X_ {1}, \ ldots, X_ {n}) \ lambda ^ {{n-1}} + e_ {2} (X_ {1}, \ ldots, X_ {n}) \ lambda ^ {{n-2}} + \ cdots + (- 1) ^ {n} e_ {n} (X_ {1}, \ ldots, X_ {n}).

Es decir, cuando se sustituyen los valores numéricos por las variables 1 , 2 , ..., n , obtenemos el polinomio mónico de una variable (con la variable λ ) cuyas raíces son los valores sustituidos por 1 , 2 , ..., n  y cuyos coeficientes son hasta su signo los polinomios simétricos elementales. Estas relaciones entre las raíces y los coeficientes de un polinomio son las fórmulas de Vieta.


Demostración: expandiendo la igualdad
a_ {n} x ^ {n} + a_ {n-1} x ^ {n-1} + \ cdots + a_ {1} x + a_ {0} = a_ {n} (x-x_ {1}) (x-x_ {2}) \ cdots (x-x_ {n})
(que es cierto desde  son todas las raíces de este polinomio), multiplicando los factores en el lado derecho e identificando los coeficientes de cada poder de 
Formalmente, si uno expande  los términos son precisamente  dónde  es 0 o 1, en consecuencia, está incluido en el producto o no, y k es el número de que están excluidos, por lo que el número total de factores en el producto es n (contando con multiplicidad k ) ( ya que hay n opciones binarias (incluir x ), hay términos: geométricamente, estos se pueden entender como los vértices de un hipercubo. Agrupando estos términos por grado produce los polinomios simétricos elementales en ) para xk, todos los distintos productos k- grupos de 

Nota: en Geometría un hipercubo 
 n-dimensional se trata de una figura cerrada, compacta y convexa cuyo esqueleto consiste en grupos de segmentos de línea paralelos opuestos alineados en cada una de las dimensiones del espacio, perpendiculares entre sí y de la misma longitud. Para n=2 es un cuadrado, para n=3 es un cubo, para n=4 es un teseracto... 
La  solución que se expondrá en el atículo será la del Dr. J. Campbell.
Si comparamos la sorprendente semejanza entre la sustitución


                                                                
que deja invariante

y la sustitución bien conocida


que deja invariante el máximo común divisor de a y b, se hace la siguiente conjetura.

Conjetura: Si a y b son enteros no negativos tales que:


es entero, entonces

Demostración: Si ab = 0, entonces el resultado es trivial. Si ab > 0 podemos suponer a ≤ b, y que el resultado está probado para valores pequeños de ab. Primero encontraremos un c∈ Z tal que:

y que cumpla


De ahí se deduce por inducción (puesto que ac < ab) que:

Para obtener c, resolveremos

y operando obtenemos que


despejando

Obsérvese que c es entero, y que mcd(a,c) = mcd(a,b). Por lo tanto, se conseguiría demostrar la conjetura si se demuestra (2). Para ello, por un lado se tiene:
con lo cual resulta (sabiendo que a ≤ b)

y esto es lo mismo que

es decir, c < b. Por otra parte



Q.E.D


Observaciones: Supongamos dadocon k entero positivo. Un estudio cuidadoso de la anterior demostración muestra que todas las soluciones (a,b) con a y b enteros no negativos de




se pueden obtener aplicando una sucesión de los operadores


a la solución (k, 0). Puesto que S² está elevado al cuadrado (es decir, S aplicado dos veces) y T² dejan invariable (a,b), toda solución de (4) tiene la forma

W(k, 0)
donde W denota una sucesión de S's y T's en la que operadores adyacentes nunca son iguales , Recíprocamente, si W es una sucesión de estas, entonces W(k,0) es una solución de (4) porque los operdores S y T dejan invariable la función


Para identificar las soluciones (a,b) = W(k,0) con a,b ≥ 0 se muestran las primeras aplicaciones de S y T a la pareja (k,0). Evidentemente, las soluciones (a,b) de la ecuación (4), con a,b ≥ 0 son:


(k, 0) (0, k) y W(k, 0)
donde la sucesión W termina en T (así que T se aplica primero a (k, 0)). Una observación final (cuya demostración se deja como ejercicio para el lector):
  • Si q=1 hay exactamente 3 soluciones.
  • Si q>1 hay infinitas soluciones.
Por lo tanto aquí termina el artículo que espero que haya sido de su agrado.

Artículo escrito por Carlos Saravia.