Enunciados de la XVII Olimpiada Nacional de Matemática 2017

Programa Jóvenes Talento de El Salvador

Estimados lectores, es un placer informarles que los enunciados de la XVII Olimpiada Nacional de Matemática 2017 han sido publicados el día de hoy. Pueden acceder a los problemas de las siguientes maneras:

  1. Versión impresa: En la edición de la Prensa Gráfica del domingo 12 de febrero de 2017.
  2. Versión digital: Disponible en la página oficial http://jovenestalento.edu.sv.

Por otro lado, para facilitar la divulgación del evento pongo a su disposición el archivo de enunciados en formato PDF a través del siguiente enlace:

OLIMPIADA NACIONAL DE MATEMÁTICA 2017

Recomendamos a los estudiantes interesados leer cuidadosamente las instrucciones para participar en la primera página del archivo. Asimismo, estamos a su entera disposición para contestar sus preguntas, ya sea a través de este medio, o bien a través de la dirección electrónica onm (arroba) jovenestalento.edu.sv.

¡Muchos éxitos! \blacksquare

Atentamente,

Coordinación de Matemática
Programa Jóvenes Talento

Publicado en Olimpiadas | Etiquetado , , , , | 1 Comentario

Acerca de un teorema de Kronecker

En esta nota discutiremos un resultado elemental, atribuido a Leopold Kronecker, que hemos presentado en el coloquio de la Escuela de Matemática del mes de agosto de 2016.

Teorema. Si un polinomio mónico de coeficientes enteros tiene raíces que son no nulas y se encuentran en el disco unitario complejo, entonces todas ellas son raíces de la unidad.

\nabla

Preámbulo 1: Raíces de la unidad y polinomios ciclotómicos

Recordemos brevemente que una raíz n-ésima de la unidad es toda raíz compleja de la ecuación X^n-1=0. Estas pueden enumerarse explícitamente como

e^{2\pi \sqrt{-1}/n}, e^{2\cdot 2\pi \sqrt{-1}/n}, \ldots, e^{2(n-1)\pi \sqrt{-1}/n}.

Claramente todas las raíces de la unidad están contenidas en el círculo unitario S^1=\{z\in \mathbb{C}: |z|=1\}, que es un grupo respecto a la multiplicación. El orden de una raíz de la unidad \zeta dentro de este grupo (es decir, el menor entero no negativo n tal que \zeta^n=1) es a lo que nos referimos habitualmente como el orden de \zeta.

Una observación fundamental es que una raíz n-ésima de la unidad no es necesariamente de orden n: por ejemplo, -1 es una raíz cuarta, pero también es una raíz cuadrada. Una raíz n-ésima cuyo orden es exactamente n recibe el nombre de raíz primitiva n-ésima de la unidad.

El polinomio mínimo sobre \mathbb{Q} de una raíz \zeta de orden n (el único polinomio mónico de coeficientes racionales y grado mínimo que se anula en \zeta) recibe el nombre de n-ésimo polinomio ciclotómico. Puede demostrarse que, de hecho, las raíces de tal polinomio son exactamente las raíces primitivas n-ésimas de la unidad, y  —lo que es aún más sorprendente— es de coeficientes enteros.

\nabla

Preámbulo 2: Relaciones de Newton

Un tipo especial de polinomios son los llamados homogéneos (que son suma de monomios de grado constante) y otro tipo es el de los llamados simétricos (que son invariantes bajo toda permutación de sus variables). Ambas propiedades son ilustradas por los polinomios simétricos elementales, que son las sumas de todos los posibles monomios de grado fijo que se pueden formar con las variables dadas z_1, z_2, \ldots, z_n, a saber:

p_1=z_1+z_2+\cdots +z_n

p_2=\sum_{i \neq j} z_iz_j

\vdots

p_n=z_1z_2\ldots z_n

Otra familia de polinomios que satisficen las propiedades en cuestión son las sumas de potencias, es decir:

s_1=z_1+z_2+\cdots +z_n

s_2=z_1^2+z_2^2+\cdots +z_n^2

\vdots

s_n=z_1^k+z_2^k+\ldots +z_n^k

\vdots

Las relaciones de Newton brindan una colección de identidades entre ambas familias:

Proposición (Relaciones de Newton). Sea p_k el k-ésimo polinomio simétrico en las variables z_1,\ldots,z_n y sea s_k= z_1^k+\ldots +z_n^k la suma de las potencias k-ésimas de los z_k. Entonces para todo k>1 se tiene la identidad

s_k-p_1s_{k-1}+p_2s_{k-2}- \cdots + (-1)^{k-1}p_{k-1} s_1+(-1)^k kp_k=0.

Aquí p_k=0 si k>n.

\nabla

Volviendo al teorema

En primer lugar tenemos el siguiente

Lema. La cantidad de polinomios en \mathbb{Z}[X] que satisfacen la hipótesis del enunciado es finita.

Demostración. Sea f(X)=X^n+a_{n-1}X^{n-1}+\cdots +a_0 uno de tales polinomios, de raíces z_1,\ldots, z_n \in \mathbb{C}. La clave es observar que los coeficientes pueden acotarse usando las relaciones de Vieta:

|a_{n-1}| =|z_1+\cdots +z_n|\leq n

|a_{n-2}| = \left| \sum_{i \neq j} z_i z_j \right| \leq \binom{n}{2}

\vdots

|a_0| =|z_1\cdots z_n| \leq 1

Y como estos coeficientes son enteros, consecuentemente pueden tomar sólo un número finito de valores. \square

Ya podemos comenzar la prueba del teorema. Comenzando con f_1(X)=f(X), podemos construir una sucesión de polinomios f_k(X), donde k \geq 1:

f_k(X)=(X-z_1^k)\cdots (X-z_n^k).

Notemos que los f_k tienen todas sus raíces en el disco unitario complejo (pues si |z| \leq 1 entonces |z^k|=|z|^k \leq 1 para todo k). Además, sus coeficientes son, salvo signo, los polinomios simétricos elementales en z_1^k, z_2^k,\ldots,z_n^k. Se sigue de las relaciones de Newton que ¡los f_k son de coeficientes enteros! Y por tanto satisfacen la hipótesis del teorema.

Pero nuestro lema afirma que hay un número finito de tales polinomios, por lo cual debemos tener f_i=f_j para ciertos índices i \neq j, es decir

\{z_1^i,z_2^i,\ldots,z_n^i\}=\{z_1^j,z_2^j,\ldots,z_n^j\}.

Luego existe una permutación \sigma del conjunto \{1, 2,\ldots,n\} tal que z_k^i=z^j_{\sigma(k)} para todo k=1,2,\ldots,n. Pero llamando \ell al orden de la permutación \sigma (es decir, el menor entero tal que \sigma^\ell=\mathrm{id}) vemos de inmediato que

z_k^{i^\ell}=z_k^{j^\ell}

y como z_k \neq 0 concluimos que z_k^{i^\ell-j^\ell}=1, y por lo tanto z_k es una raíz de la unidad. \square

Finalmente, podemos hacer una observación adicional:

Corolario. Todo polinomio que cumple con las hipótesis del enunciado factoriza como producto de polinomios ciclotómicos.

Demostración. En efecto, sea \zeta una raíz (digamos de orden k) de tal polinomio f. Como f es mónico de coeficientes enteros  y \zeta tiene polinomio mínimo \Phi_k sobre \mathbb{Q}, resulta que este divide a f. Repitiendo el proceso con otra raíz de la unidad que no sea de orden k obtenemos otro polinomio ciclotómico como factor, y así sucesivamente. \blacksquare

Referencias

Damianou, Pantelis A., “Monic Polynomials in Z[x] with Roots in the Unit Disc”, Am. Math. Monthly 108 (3), March 2001, pp. 253-257.

 

 

Publicado en Álgebra, Matemática pura | Etiquetado , , | Deja un comentario

Las matemáticas de John Forbes Nash Jr. (1928-2015), primera parte

El matemático John Forbes Nash Jr. y su esposa Alicia Lardé han fallecido el 23 de mayo de 2015 en un accidente de tránsito en Nueva Jersey, EE. UU. Nash, cuyo nombre seguramente es familiar al lector gracias a la película Una mente brillante, constituye un raro caso de un científico que ha logrado ganarse un espacio en la cultura popular (más raro aún si pensamos sólo en matemáticos). En El Salvador se ha resaltado también la nacionalidad de Lardé, quien era salvadoreña, y su formación como científica en una prestigiosa universidad estadounidense. Como es de esperarse, esta triste noticia ha conmovido tanto a la comunidad científica como al público en general.

Nash junto con su esposa en su visita a El Salvador en 2002. Fuente: LPG

Nash junto con su esposa en su visita a El Salvador en 2002. Fuente: LPG

Probablemente la ocasión merezca un obituario o biografía de Nash, mas nuestra intención es dar un homenaje a su memoria exponiendo al lector un aspecto diferente de su vida: su obra matemática, que ha recibido muy poca atención en los medios aparte de la consabida teoría de juegos. Esta omisión es comprensible, pues explicar matemáticas avanzadas al público no es una tarea fácil, mas eso no quiere decir que debemos dejar de intentar. Así pues, en esta entrada no asumiremos ningún conocimiento matemático avanzado de parte del lector.

***

Preámbulo: ¿Qué es geometría?

Vamos a discutir primero qué es lo que entendemos por “geometría”. En un primer intento, podemos afirmar que es el estudio axiomático de figuras geométricas tal y como puntos, rectas, circunferencias,  etc. y las relaciones entre ellas. Esta razonable noción fue concebida y perfeccionada por los griegos y, así como en otros dominios del saber bajo influencia griega, dominó el pensamiento matemático occidental por cerca de 2000 años. Sin embargo, esto no es lo que un matemático o un físico entiende por “geometría” en nuestros días, pues nuevas geometrías comenzaron a gestarse en el siglo XIX. Entre el maremágnum de abstracciones desarrolladas desde entonces, el concepto de variedad ocupa un lugar central: he aquí las “figura geométricas” del mundo matemático actual.

Calabi_Yau_1

Las variedades de Calabi-Yau ocupan un lugar preeminente en la física moderna. Fuente: Wikipedia

¿Pero qué es una variedad? Veamos una ilustración sencilla. Nosotros habitamos en la superficie de la Tierra, que para efectos prácticos es una esfera. Todos conocemos muy bien que podemos emplear mapas, que son perfectamente planos, para modelar partes de la misma. Reuniendo mapas en un atlas exhaustivo que abarque todo el mundo, tendremos una idea razonable de la geometría del globo terráqueo sin tener que observarlo desde el espacio. De manera análoga, una variedad es una figura abstracta que puede ser descrita mediante un “atlas” de “mapas” basados en el espacio euclidiano. Esta definición tiene la virtud extraordinaria de que no necesitamos visualizar dentro del espacio el objeto a estudiar para poder definirlo. Esto contrasta con la geometría clásica de Euclides, en la que toda la teoría tiene lugar dentro del espacio euclidiano. Asimismo, ganamos la ventaja de poder describir una enorme variedad de figuras (el lector disculpará el juego de palabras): curvadas, con agujeros, en muchas dimensiones, etc.

Otro aspecto interesante es que, a través de los mapas, podemos dotar a una variedad de propiedades especiales del espacio euclidiano. Una de ellas la de poder medir distancias. Este es un privilegio no tan evidente en el caso de figuras curvadas, con agujeros o difíciles de visualizar. Cuando dotamos cada mapa de cierto “aparato medidor” (una métrica riemanniana), el concepto de distancia en nuestra figura cobra sentido y hablamos de una variedad riemanniana. Estos son los objetos concernientes al trabajo de Nash que deseamos presentar.

***

I. Geometría riemanniana

El concepto de variedad efectivamente engloba todas las figuras geométricas a las que estamos acostumbrados. Sin embargo,  el lector podría plantearse la siguiente pregunta filosófica: ¿Existe acaso alguna variedad imposible de concebir en el espacio que conocemos? Esta duda, que asaltó incluso a los matemáticos pioneros de esta teoría, fue resuelta en los años treinta con el famoso teorema de encajamiento de Whitney: toda variedad puede ser “encajada” (es decir, modelada sin alterar su geometría) en un espacio euclidiano de dimensión lo suficientemente grande. Por tanto el concepto de variedad no crea figuras “nuevas” o “imposibles”, mas es muy conveniente desde el punto de vista teórico y sigue siendo ampliamente utilizado en matemáticas.

Un matiz diferente de este problema surge al considerar variedades riemannianas: así como un atlas de la Tierra que no respete distancias o proporciones es poco menos que inútil, de nada serviría visualizar una variedad riemanniana dentro del espacio sin que las distancias dentro de la misma sean preservadas. La existencia de tal encajamiento es un problema notablemente difícil resuelto por Nash:

Teorema de encajamiento de Nash. Toda variedad riemanniana puede ser encajada isométricamente (preservando distancias) en un espacio euclidiano de dimensión lo suficientemente grande.

Tomemos como ejemplo un toro, el cual es un modelo abstracto de la figura de una dona. Se trata de un área cuadrada en la que ambos pares de lados opuestos están identificados de la forma en que se muestra en la figura (el lector probablemente lo asociará a la pantalla de un videojuego):

toro1

Fuente: Projet Hévéa

Un modelo más atractivo de esta figura en el espacio se obtiene al tomar un cuadrado elástico, unir un par de lados opuestos para formar un tubo, y luego unir ambos extremos. ¡El resultado es una dona!

toro2

Fuente: Project Hévéa

Usando un lenguaje más formal, el procedimiento anterior define un encajamiento del toro en el espacio euclidiano. Sin embargo, este encajamiento no preserva distancias: claramente la circunferencia transversal de la dona es mayor que la vertical. La culpa de este defecto la tienen los estiramientos que hemos hecho para ensamblar la figura.

Ahora recordemos que el teorema de Nash predice la existencia de un encajamiento isométrico: el modelo cuadrado del toro puede ser doblado y pegado preservando longitudes, es decir, sin estirar ni encoger. ¿Pero cómo es posible hacer esto entonces? Gracias al trabajo reciente de un equipo de matemáticos franceses (Hevea Project) podemos deleitarnos contemplando la respuesta en imágenes de alta resolución:

El pase de diapositivas requiere JavaScript.

El encajamiento isométrico visualizado se construye partiendo del modelo de la dona, que como hemos dicho no preserva las distancias del toro. Para remediar esto, se corruga ligeramente su superficie, para luego corrugar cada una de las protuberancias creadas, y así sucesivamente. En el límite, este procedimiento iguala las distancias en el toro que habían sido distorsionadas en la dona, tal y como puede apreciarse aquí:

isometric2

Fuente: Projet Hélvéa

Concluimos comentando brevemente el resultado de Nash: en realidad, no se trata de un problema de geometría ¡sino que de cálculo! Al estudiar una definición rigurosa veremos que el “aparato medidor” de la métrica riemanniana es un objeto expresado en términos de las derivadas de las funciones coordenadas de cada carta, por lo cual la preservación de la métrica bajo un encajamiento es equivalente a resolver un sistema de ecuaciones diferenciales parciales. Por mucho tiempo se creyó que encontrar una solución para tal sistema era imposible; el mérito de Nash consiste en haber ideado un método de solución completamente original y sin precedentes. El matemático británico John Horton Conway afirmó que el teorema de encajamiento de Nash es uno de los resultados analíticos más importantes del siglo XX; el ilustre matemático ruso Mikhail Gromov lo dijo mejor: “fue como un relámpago”. \blacksquare

Próxima entrega: geometría algebraica real, teoría de singularidades, ecuaciones diferenciales parciales elípticas y parabólicas.

Más información:

Noticia del fallecimiento de Nash y su esposa (en inglés) en el New York Times.

Puede encontrar más imágenes y videos sobre el encajamiento del toro en el sitio Projet Hévéa: les images.

Puede consultar los artículos originales de Nash sobre el problema del encajamiento riemanniano aquí: C¹ Isometric Imbeddings y The Imbedding Problem for Riemannian Manifolds.

Todos los sitios fueron consultados el 27 de mayo de 2015.

Publicado en Geometría | Etiquetado , , | 3 comentarios

Contando polinomios irreducibles sobre cuerpos finitos

En esta nota hablaremos de una preciosa fórmula debida a Gauss:

Sean q una potencia de un primo y n un entero positivo. El número de polinomios mónicos, de grado n y irreducibles sobre \mathbb{F}_q es

\displaystyle \frac{1}{n}\sum_{d|n} \mu\left(\frac{n}{d}\right)q^d.

Aquí \sum_{d|n} denota la suma sobre todos los divisores de n, mientras que \mu es la función de Möbius, a la cual dedicaremos unas líneas a continuación.

\ast \ast \ast

La función de Möbius

En este apartado referiremos varias veces al lector a nuestra publicación anterior Funciones aritméticas y un problema de Liouville [F].

Para cada entero positivo n definimos \mu(n) de la siguiente manera:

\mu(n)=\begin{cases} 1 &\mbox{si } n=1\\ (-1)^r &\mbox{si }n \mbox{ es producto de } r \mbox{ primos distintos}\\ 0 &\mbox{si } n \mbox{ es divisible por el cuadrado de un primo}\end{cases}

Esta es la función de Möbius, debida al matemático alemán August Ferdinand Möbius (1790-1868), aunque una definición equivalente ya había sido usada por Gauss en su célebre Disquisitiones Arithmeticae. (Cf. Ejercicio 1.) Como podemos ver, es una función que toma únicamente los valores 0, 1, -1, y además \mu(n)\neq 0 si y sólo si  n es “libre de cuadrados”, es decir no tiene factores primos repetidos.

El lector que haya leído [F] de antemano podrá anticipar que \mu es una función aritmética, y que además es multiplicativa: para cualesquiera m y n coprimos se cumple que \mu(mn)=\mu(m)\mu(n). (¡Compruébelo!) De hecho, \mu ocupa un lugar muy especial entre las funciones aritméticas debido a la siguiente propiedad, cuya deducción dejamos como ejercicio.

Proposición 1 (Fórmula de inversión de Möbius). Sean f y g funciones aritméticas tales que

\displaystyle g(n)=\sum_{d|n} f(d) \mbox{ para todo } n \geq 1.

Entonces

\displaystyle f(n)=\sum_{d|n} \mu(d) g\left(\frac{n}{d}\right) \mbox{ para todo } n\geq 1.

Nota. Usando la convolución de Dirichlet introducida en [F] podemos reescribir lo anterior como sigue: si f y g son dos funciones aritméticas tales que g=f\ast 1, entonces f=\mu \ast g. Aquí 1 representa la función constante igual a 1.

De manera informal, la fórmula anterior nos permite “despejar” el sumando f dentro del símbolo \sum_{d|n}.

Ejercicio 1. Demuestre que \mu(n) es igual a la suma de las raíces primitivas n-ésimas de la unidad. ¿Cómo se deduce la multiplicatividad de \mu a partir de esta definición alternativa?

Ejercicio 2.

(a) Demuestre la identidad

\displaystyle \sum_{d|n}\mu(d)=\begin{cases}1 &\mbox{si }n=1\\ 0 &\mbox{en caso contrario.}\end{cases}

(b) Verifique que (a) es equivalente a afirmar que \mu \ast 1=\epsilon, donde  \epsilon es la función definida como \epsilon(1)=1 y \epsilon(n)=0 para todo n>0.

Ejercicio 3. Demuestre la fórmula de inversión de Möbius. (Pista: Use la parte (b) del ejercicio anterior y el hecho de que la convolución de Dirichlet es conmutativa y asociativa.)

\ast \ast \ast

Primera demostración de la fórmula de Gauss

Procedemos ahora a comentar brevemente sobre la prueba más conocida de la fórmula de Gauss. Aceptaremos la veracidad del siguiente hecho sobre cuerpos finitos. (Cf. Jacobson [2], §4.13, Corollary 2.)

Proposición 2. El polinomio X^{q^n}-X  factoriza como el producto de todos los polinomios mónicos irreducibles sobre \mathbb{F}_q cuyo grado es un divisor de n.

Denotemos por \mathcal{P}_n el número de polinomios mónicos, de grado n y irreducibles sobre \mathbb{F}_q. Comparando los grados de X^{q^n}-X y su factorización en polinomios irreducibles se infiere que

\displaystyle q^n=\sum_{d|n} d\mathcal{P}_d.

Y una aplicación de la fórmula de inversión de Möbius nos permite concluir que

\displaystyle n \mathcal{P}_n=\sum_{d|n} \mu \left(\frac{n}{d}\right) q^d. \square

\ast \ast \ast

Otro argumento menos conocido

La prueba anterior es estándar y puede encontrarse en varios textos de álgebra. Sin embargo, existe otra demostración muy interesante que hace uso de argumentos combinatorios en lugar de la fórmula de inversión de Möbius. Nos basaremos en la excelente exposición de Chebolu y Mináč [2].

Sea \mathcal{R}_n el conjunto formado por todas las raíces de los polinomios pertenecientes a \mathcal{P}_n. Notemos que en realidad este es un subconjunto de \mathbb{F}_{q^n}, ya que el cuerpo de escisión de cualquier elemento de \mathcal{P}_n es una extensión de grado n de \mathbb{F}_{q}, y por tanto es isomorfo a \mathbb{F}_{q^n}. Más aún, puesto que cada elemento de \mathcal{P}_n no tiene raíces repetidas y dos elementos cualesquiera no tienen raíces en común (¿por qué?), resulta que \# \mathcal{R}_n=n\# \mathcal{P}_n. Luego el cálculo de \# \mathcal{P}_n se reduce al de \# \mathcal{R}_n.

Ahora echaremos mano de un resultado fundamental de la teoría de cuerpos finitos. (Cf. [2],  §4.13, Corollary 1.)

Proposición 3. Existe una correspondencia biunívoca

\mathbb{F}_{q^d} \longleftrightarrow d

entre las subextensiones de \mathbb{F}_{q^n}/\mathbb{F}_q y los divisores de n .

Nota. Una reformulación elegante de este hecho es que el retículo de subextensiones de \mathbb{F}_{q^n}/\mathbb{F}_q es isomorfo al retículo de divisores de n.

El subconjunto \mathcal{R}_n de \mathbb{F}_{q^n} puede ser caracterizado como la colección de todos los elementos  de \mathbb{F}_{q^n}  que no pertenecen a una subextensión propia de \mathbb{F}_{q^n}/\mathbb{F}_q. Claramente es suficiente considerar subextensiones propias maximales; descomponiendo n=p_1^{\alpha_1} \ldots p_k^{\alpha_s} en sus factores primos, dichas subextensiones corresponden por la proposición anterior a los divisores n/p_1, \ldots, n/p_s, que son los elementos maximales del retículo de divisores de n. Se sigue que

\displaystyle \mathcal{R}_n=\mathbb{F}_{q^n}\bigg\backslash \bigcup_{i=1}^s \mathbb{F}_{q^{n/p_i}}

y en consecuencia \#\mathcal{R}_n puede calcularse mediante el principio de inclusión-exclusión: teniendo en cuenta que \mathbb{F}_{q^a} \cap \mathbb{F}_{q^b}=\mathbb{F}_{q^{\mathrm{mcd}\,(a,b)}} para cualesquiera a y b, deducimos que

\displaystyle \#\mathcal{R}_n=q^n-\sum_i q^{n/p_i}+\sum_{i\neq j} q^{n/p_ip_j}-\cdots+(-1)^s q^{n/p_1\cdots p_s}.

Pero el miembro derecho de esta expresión es precisamente \sum_{d|n}\mu(n/d)q^d. (¡Verifíquelo!) Así que nuestro trabajo ha terminado. \blacksquare

Ejercicio 4. ¿Qué sucede en la demostración anterior si n=1?

Referencias

[F] Salvamate, Funciones aritméticas y un problema de Liouville, versión del 11/05/2015.

[1] Chebolu, S.K., Mináč, J., “Counting irreducible polynomials over finite fields using the inclusion-exclusion principle”, Math. Mag. 84 (2011), No. 5, 369-371.

[2] Jacobson, N., “Basic Algebra”, 2nd ed, W.H. Freeman, New York, 1985.

Publicado en Álgebra, Combinatoria, Matemática pura | Etiquetado , | 6 comentarios

Resultados salvadoreños en la XXIX Olimpiada Iberoamericana de Matemática 2014

El pase de diapositivas requiere JavaScript.

Clausurando la temporada de olimpiadas del presente año, deseo informar a mis lectores los resultados de la XXIX Olimpiada Iberoamericana de Matemática, que tuvo lugar en San Pedro Sula (Honduras) del 19 al 27 de septiembre de 2014. Enumero a continuación los nombres de los participantes salvadoreños junto a sus premios y demás resultados.

Dennis Joaquín Díaz Díaz: Mención honorífica
Gabriel Emiliano Carranza Menjívar: Mención honorífica
Andrés Fernando Rosa Aparicio
Salvador Alonso Figueroa Vásquez

Puntaje por equipo: 40 (máximo 168)

Ranking: 15 (22 países participantes)

El líder de la delegación fue el Mtr. Carlos Ernesto Gámez Rodríguez, profesor de la Escuela de Matemática de la Universidad de El Salvador, mientras que Mynor Ademar Melara Estrada tuvo el cargo de tutor.

El primer lugar de la olimpiada fue conquistado por México, seguido de Brasil, España, Perú y Portugal en el ranking de países. El líder de la región centroamericana fue nuevamente Costa Rica, que se posicionó en el octavo lugar, seguida por Nicaragua, que notablemente ha mantenido un buen nivel de participación.

Este año los resultados salvadoreños son de los más modestos entre nuestras participaciones recientes en esta competencia, lo cual fue un tanto inesperado para este servidor, quien tenía muchas expectativas de los estudiantes y sus entrenadores. Si bien es una pena no haber traído mas premios a casa en esta ocasion, confío en que contamos y seguiremos contando con muchos jóvenes talentosos engrosando nuestras filas en el Programa, y por ello estoy convencido de que nuestro sistema olimpico nos depara sorpresas más gratas en el futuro. \blacksquare

Adenda. Con motivo de la OIM 2014 se organizó un seminario de resolución de problemas del 18 al 20 de septiembre. Los anfitriones amablemente han puesto a disposición del público los materiales del mismo; adjunto el enlace correspondiente esperando que los lectores disfruten de los contenidos.

 Simposio OIM 2014

 

Publicado en Olimpiadas | Etiquetado , , | Deja un comentario

Sobre cierta recurrencia para la función partición

Deseo presentar a mis lectores una atractiva identidad que encontré casualmente en una edición moderna de los legendarios cuadernos de Ramanujan. Para un entero positivo n, sea \sigma(n) suma de los divisores de n, que ya fue introducida en una publicación anterior, y sea p(n) el número de particiones de n, es decir, el número de formas de escribir n como una suma no ordenada de enteros positivos. Entonces se cumple la identidad

\displaystyle np(n)=\sum_{k=1}^{n-1}\sigma(k)p(n-k).

A continuación discutiré dos pruebas: una algebraica, usando funciones generatrices, y una combinatoria, debida a Marc van Leeuwen (Université de Poitiers).

\nabla

Un poco de práctica con funciones generatrices

Un hecho curioso sobre la función partición es que, a pesar de tener una definición tan sencilla, es un tanto difícil de calcular: ¡no existe una fórmula para calcular p(n) en función de n! No obstante, tal y como los lectores familiarizados con combinatoria sabrán, los valores de p(n) están completamente determinados como los coeficientes en la expansión del producto infinito

\displaystyle \prod_{k=1}^\infty\frac{1}{1-x^k}.

Luego es de esperarse que nuestra identidad pueda ser abordada mediante funciones generatrices. En efecto, por definición tenemos la igualdad

\displaystyle \sum_{n=1}^\infty p(n)x^n=\displaystyle \prod_{k=1}^\infty\frac{1}{1-x^k}.

Derivando ambos lados respecto a x, es obvio que el miembro izquierdo se convierte en \sum_{n=1}^\infty np(n)x^{n-1}. En cambio, derivar el miembro derecho es ligeramente más difícil y necesitaremos de derivación logarítmica. Llamando P a la expresión en cuestión, tenemos que

\displaystyle \log P=\sum_{k=1}^\infty \log \frac{1}{1-x^k}

y derivando ambos lados queda

\displaystyle \frac{P'}{P}=\sum_{k=1}^\infty \frac{kx^{k-1}}{1-x^k}.

Despejando P' se sigue que

\displaystyle \sum_{n=1}^\infty np(n)x^{n-1}= \prod_{k=1}^\infty\frac{1}{1-x^k} \sum_{k=1}^\infty \frac{kx^{k-1}}{1-x^k}

o, lo que es lo mismo,

\displaystyle \sum_{n=1}^\infty np(n)x^{n}= \prod_{k=1}^\infty\frac{1}{1-x^k} \sum_{k=1}^\infty \frac{kx^{k}}{1-x^k}.

Luego, comparando los coeficientes de x^n a ambos lados de esta igualdad vemos que np(n) es igual al coeficiente de x^n en el producto de \prod_{k=1}^\infty1/(1-x^k) y \sum_{k=1}^\infty kx^{k}/(1-x^k), el cual puede ser calculado media vez conozcamos los coeficientes de las mismas.

Puesto que ya sabemos que \prod_{k=1}^\infty 1/(1-x^k) es la función generatriz de la sucesión \{p(n)\}, nada más resta averiguar cuál es la sucesión asociada a \sum_{k=1}^\infty kx^{k}/(1-x^k). Para ello expandamos 1/(1-x^k) usando la serie geométrica:

\displaystyle \sum_{k=1}^\infty \frac{kx^{k}}{1-x^k}=\sum_{k=1}^\infty kx^k\sum_{j=0}^\infty x^{kj}= \sum_{k=1}^\infty k\sum_{j=1}^\infty x^{kj}.

Luego, para cada valor de n, el término en x^n en la expresión anterior es  la suma de todos los términos kx^{kj} tales que kj=n. Pero esta última condición implica que k recorre los divisores (positivos) de n. En consecuencia, el coeficiente de x^n es exactamente la suma \sigma(n) de todos los divisores de n.

Finalmente, concluimos que el coeficiente de x^n en el producto de las funciones generatrices de las sucesiones \{p(n)\} y \{\sigma(n)\} es \sum_{k=1}^n \sigma(k)p(n-k), y por lo tanto

\displaystyle np(n)=\sum_{k=1}^n \sigma(k)p(n-k).

Nota. Una serie de la forma

\displaystyle \sum_{n=1}^\infty a_n \frac{x^n}{1-x^n}

es conocida como serie de Lambert, y tiene la propiedad de ser la función generatriz de la sucesión b_k=\sum_{n|k} a_n. (La prueba de este hecho es un ejercicio sencillo para el lector.) En nuestro caso, la serie de Lambert de la sucesión a_n=n tiene coeficientes b_k=\sum_{n|k} n = \sigma (k). \square

\nabla

La utilidad de los diagramas de Young

También es posible dar una interpretación combinatoria de esta identidad. Para ello es conveniente representar particiones de manera geométrica.  Si \lambda= (\lambda_1, \ldots, \lambda_m) es una partición del entero positivo n con \lambda_1 >\ldots >\lambda_m, el diagrama de Young asociado a \lambda es un arreglo rectangular construido de acuerdo a las siguientes reglas:

  • El arreglo consta de m filas, una por cada sumando de la partición.
  • Las filas del arreglo están justificadas a la izquierda.
  • La i-ésima fila del arreglo contiene \lambda_i casillas (1 \leq i \leq m).
ejemplo1

Diagramas de Young de las particiones de 3

Volvamos entonces a la segunda prueba. Fijemos n y consideremos el conjunto \mathcal{S} de diagramas de Young con una de sus casillas marcadas. Puesto que el número de diagramas de Young distintos es p(n) por definición, y en cada diagrama hay n casillas que pueden ser marcadas, se sigue que este conjunto tiene np(n) elementos, que es el miembro izquierdo de nuestra identidad.

Los elementos de \mathcal{S} pueden ser contados de otra forma. Dado un diagrama de Young con una casilla marcada, supongamos que la fila que contiene dicha casilla tiene tamaño s, y que además el diagrama tiene exactamente r filas de este tamaño. Fijemos 1 \leq k \leq n-1. Afirmamos entonces que hay \sigma(k) p(n-k) elementos de \mathcal{S} tales que rs=k. En efecto, dado un elemento de \mathcal{S} que cumpla con la condición anterior, removamos todas las filas de tamaño r para formar un rectángulo de r \times s (es decir de área k) con una casilla marcada en su primera fila, y con las filas restantes formemos un diagrama de Young de tamaño n-k. Recíprocamente, a partir de un rectángulo de área k con una casilla marcada en su primera fila y un diagrama de Young de tamaño n-k, podemos construir un elemento de \mathcal{S} insertando el rectángulo en una posición adecuada dentro del diagrama. Luego basta contar el número de posibles parejas de tales rectángulos y diagramas de Young. Pero el número de rectángulos de área k con una casilla marcada en su fila superior es \sigma(k) (¿por qué?), mientras que el número de diagramas de Young de tamaño n-k es p(n-k). Por tanto el número buscado es  \sigma(k) p(n-k), y sumando sobre k=1,\ldots, n-1 obtenemos el miembro derecho de nuestra idendidad. \square

ejemplo2

\nabla

Comentario histórico

Me he abstenido de afirmar que Ramanujan descubrió esta fórmula, pues sus cuadernos incluyen algunos resultados que no son originales. La referencia [2] que he consultado no hace comentario alguno sobre la fuente del problema, así que es probable que los autores del libro lo hayan atribuido a él. En todo caso, esta pequeña identidad palidece ante otros de sus espectaculares resultados sobre la función partición, como son las célebres congruencias de Ramanujan. Este y muchos otros temas relacionados con particiones son discutidos en el clásico [1]. \blacksquare

Referencias

[1] Andrews, G.E., The Theory of Partitions, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998.

[2] Berndt, B.C., Ramanujan’s Notebooks, Part IV, Springer-Verlag, New York, 1994.

 

Publicado en Combinatoria, Olimpiadas, Teoría de números | Deja un comentario

Resultados salvadoreños en la XVI Olimpiada Matemática de Centroamérica y el Caribe 2014

El pase de diapositivas requiere JavaScript.

Me enorgullece informar a mis lectores sobre los resultados de El Salvador en la  XVI Olimpiada Matemática de Centroamérica y el Caribe, que acaba de ser celebrada en San José (Costa Rica) del 6 al 14 de junio de 2014. Resumo a continuación los datos más importantes:

Carlos Rafael Gil Alvarado: Medalla de plata
Gabriel Emiliano Carranza Menjívar: Medalla de plata
Carlos Ariel Piche Cruz: Mención honorífica

Puntaje por equipo: 87 (máximo 126)

Ranking: 2 (empate con Colombia; 12 países participantes)

Las responsabilidades de líder y tutor recayeron respectivamente en el Lic. Mario Ruiz  y Byron Thonatiu Escobar Benítez, ambos pertenecientes a la Escuela de Matemática de la Universidad de El Salvador.

Prosigo con un breve análisis de los exámenes, que los lectores pueden consultar en los enlaces siguientes:

Día 1
Día 2

Las pruebas de este año tuvieron un carácter ligeramente diferente al habitual: faltó combinatoria casi siempre presente en esta olimpiada, mas hubo dos problemas de álgebra, área con frecuencia ausente. Por otro lado,  la elección de los problemas 1 y 4 se me hizo un tanto sorprendente, pues por su estilo y simplicidad estos se asemejan más a problemas de olimpiadas de menor categoría. El resto de problemas fueron ciertamente de un nivel y estilo apropiados para el concurso, aunque mi impresión general es que la dificultad de las pruebas ha venido disminuyendo en los últimos años.

Entre otras trivialidades sobre los exámenes, soy el feliz autor del problema 2, el cual es mi primer problema publicado en una olimpiada internacional. Otra noticia menos grata es que el problema 3, el más difícil de este año, no es nuevo; de hecho, apareció como el problema 2020 del volumen 21 (1995) de Crux Mathematicorum, una revista muy famosa de resolución de problemas. Por si fuera poco, tampoco el problema 6 es original, pues —tal y como Byron me comunicó amablemente— proviene de la edición 2013 de cierta competencia estadounidense llamada Online Math Open. Si bien esto no tiene que ver en absoluto con los logros de nuestros estudiantes, el plagio de problemas es una práctica deplorable que pone en entredicho la calidad y el prestigio de cualquier olimpiada de matemática. Espero que casos desafortunados como este disminuyan en el futuro.

Pero volvamos a nuestros resultados. Aparte de los excelentes premios cosechados, quisiera enfatizar que el histórico segundo lugar obtenido por nuestros estudiantes debe ser motivo de celebración y orgullo para el Programa Jóvenes Talento y la comunidad matemática del país. Vale la pena detenerse a pensar qué tanto hemos progresado en estos 17 años desde 1997, que es cuando el germen de las olimpiadas y del Programa nació bajo la forma de un pequeño grupo de preparación para la Olimpiada Iberoamericana de Matemática. En aquellas épocas de aspiraciones humildes, ni profesores ni estudiantes imaginaban cuánto íbamos a progresar con el paso del tiempo; un segundo lugar en una olimpiada era seguramente algo impensable. Nosotros, que ahora gozamos de un Programa con abundantes recursos y experiencia en materia olímpica, quizás no estemos en una situación tan diferente: gracias a estos privilegios, nos hemos acostumbrado a alcanzar —acaso sin esfuerzo— cierto estándar dentro y fuera del Programa, mas no imaginamos los nuevos logros que podríamos conquistar con un poco más de empeño y ambición. Extiendo mis más sinceras felicitaciones a Carlos, Gabriel, Ariel y a sus entrenadores, y espero que sigan apuntando al nivel más alto de excelencia posible. \blacksquare

Publicado en Olimpiadas | Etiquetado , , | 8 comentarios