A maior rede de estudos do Brasil

Grátis
179 pág.
Análise combinatória matemática

Pré-visualização | Página 22 de 30

guerras y persecuciones antisemi-
tas. No obstante las restricciones imperantes sobre los jud́ıos acerca
del ingreso en las universidades en Hungŕıa, Erdös fue autorizado a in-
gresar en 1930, en virtud de haber ganado los exámenes nacionales de
matemáticas. Estudió su doctorado en la Universidad Pázmány Péter,
en Budapest. Habiéndose graduado en 1934 (siendo su tutor Leopold
Fejér), obtuvo una beca para realizar estudios post-doctorales en Manch-
ester, Inglaterra, siendo prácticamente forzado a dejar Hungŕıa debido
a su condición de jud́ıo.
En 1938 obtuvo una beca corta para realizar estudios post-doctorales
en Princeton, Estados Unidos, páıs donde se estableció hasta 1954, año
en que le cancelaron su visa de residencia en circunstancias aún poco
claras, relacionadas con sospechas infundadas de que simpatizaba con la
ideoloǵıa comunista, en aquellas oscuras épocas de la guerra fŕıa. Nueve
años más tarde, en 1963, retornó a Estados Unidos luego de la presión
114 Caṕıtulo 8. Otros tópicos de la teoŕıa de combinatoria
pienso que el problema es muy dif́ıcil; tal vez me equiv-
oque)”.
Por ejemplo, para n = 4 nuestros conjuntos podŕıan
ser:
A1 = {a, b, c, d}, A2 = {a, e, f, g},
A3 = {b, f, h, i}, A4 = {c, g, h, j}.
En este ejemplo los conjuntos fueron seleccionados de
tal manera que siempre dos ellos tienen intersección no
vaćıa aunque unitaria: se trata de un caso extremo.
Aqúı podemos colorear los elementos de la unión
4⋃
k=1
Ak = {a, b, c, d, e, f, g, h, i, j}
con los cuatro colores rojo, azul, verde y blanco, de la
siguiente manera: (a=rojo), (b=azul), (c=verde), (d=blan-
que ejercieron varias prestigiosas universidades norteamericanas para
que le restablecieran la visa de residencia.
Las contribuciones que Erdös hizo a las matemáticas fueron tan nu-
merosas como extensas. Los tópicos de su predilección eran los de com-
binatoria, la teoŕıa de grafos y la teoŕıa de números. No obstante, hizo
aportes en prácticamente todos los campos de la matemática, siendo
uno de los matemáticos más versátiles que se recuerde. Le apasionaba
resolver problemas matemáticos de la manera más elegante y elemen-
tal posible. Para Erdös, una demostración deb́ıa proporcionar discern-
imiento sobre porqué el resultado que se estaba probando era verdadero,
y no solamente constituir una complicada sucesión de etapas formales
desprovistas de inteligencia.
Algunos resultados con los cuales Erdös es asociado fueron demostra-
dos antes de su nacimiento. Por ejemplo, en 1845 Bertrand conjeturó que
hab́ıa al menos un número primo entre n y 2n, para cualquier número
natural n mayor o igual que 2. Chebyshev demostró esta conjetura en
1850. Erdös, a los 18 años, encontró una elegante demostración elemen-
tal de este hecho. Otro resultado asociado con Erdös es el teorema de
los números primos, que establece que la cantidad de primos menores o
iguales a n tiende a infinito asintóticamente con n
ln n
. Este resultado fue
conjeturado en el siglo XVIII y demostrado hasta en 1896 por Hadamard
y de la Vallée Poussin. En 1949 Erdös y Atle Selberg hallaron una el-
8.6. Algunos problemas abiertos en combinatoria 115
co), (e=azul), (f=verde), (g=blanco), (h=rojo), (i=blanco),
(j=azul). De esta forma, todo conjunto Ak tendrá el-
ementos de los n = 4 diferentes colores. ¡Obsérvese
que el resultado en general parece obvio, aunque desde
luego no lo es!
2. Una vieja conjetura en teoŕıa de números, aún sin re-
solver, consiste en probar que para cada entero posi-
tivo k existen k números primos que siguen una pro-
gresión aritmética. Hasta el momento, la más larga pro-
gresión aritmética de números primos conocida tiene 17
términos y es debida a Weintraub.
En relación con este problema, Erdös conjeturó lo sigu-
iente: si (ak)k≥1 es una sucesión de enteros positivos
estrictamente creciente y la serie
∑∞
n=1 1/an = ∞, en-
tonces para todo k ≥ 1 existen k términos consecutivos
de los an’s que forman una progresión aritmética.
egante demostración elemental. Originalmente Selberg y Erdös hab́ıan
convenido en publicar su trabajo en una serie de varios art́ıculos, com-
partiendo los créditos. Sin embargo, Selberg cambió de parecer y se
adelantó, publicándola de primero. ¡Erdös se enteró de ello hasta el año
siguiente, cuando Selberg ganó la Medalla Fields por este trabajo!
Recibió el premio Cole de la Asociación Matemática Americana en
1951 por sus variados art́ıculos sobre la teoŕıa de números, y en par-
ticular por su trabajo “Sobre un nuevo método en teoŕıa de números
elemental que lleva a una prueba elemental del teorema de los números
primos”, publicado en el Proccedings of the National Academy of Sci-
ences en 1949. También ganó el premio Wolf (con $50.000) en 1983.
Como matemático trashumante que era, sin par en la historia, Erdös
asist́ıa a decenas de coloquios y congresos al año, extendiendo y re-
forzando continuamente sus contactos y sirviendo de catalizador de ideas
matemáticas, formando disćıpulos. Teńıa un estilo de vida muy sen-
cillo que requeŕıa de pocos recursos personales. Donaba la mayoŕıa del
dinero que ganaba por concepto de sus conferencias dictadas por todo
el mundo para ayudar a los estudiantes, ofreciendo además premios en
efectivo para la resolución de algunos problemas matemáticos que él
mismo planteaba. Trabajó en numerosas universidades, aunque sin es-
tablecerse fijamente en ninguna de ellas por peŕıodos largos. Entre ellas
116 Caṕıtulo 8. Otros tópicos de la teoŕıa de combinatoria
Como Euler demostró que la suma de los rećıprocos
de los números primos es divergente, entonces la de-
mostración de la conjetura de Erdös demostraŕıa también
la vieja conjetura de las progresiones aritméticas de los
primos.
Ofrezco 3000 dólares por una prueba o un contraejem-
plo de esta conjetura, señala Erdös.
8.6.2 El “Football Pool Problem”
Uno de los problemas abiertos de combinatoria de más sen-
cillo enunciado es el “Football Pool Problem”, cuya versión
más sencilla es la siguiente.
Supóngase que se desea vaticinar el resultado de n juegos
de fútbol, cada uno de ellos con tres posibles resultados: i)
victoria del equipo casa (codificado con un 2); ii) empate
(codificado con un 1); iii) derrota del equipo casa (codificado
con un 0). Una boleta de apuestas consiste en indicar el
resultado de cada uno de los n juegos en disputa. ¿Cuál es
el mı́nimo número σn de boletas que se deben llenar para
garantizar que acertaremos al menos n− 1 de los juegos?
Parece que se trata de un problema sencillo. Por ejemplo:
1. Para n = 1 la solución es obvia, σ1 = 1 (no importa
como llenemos la boleta, siempre acertaremos al menos
0 juegos).
2. Para n = 2 también es obvio: σ2 = 3. Por ejemplo,
podemos llenar las siguientes 3 boletas: (0, 0), (1, 2),
(2, 0) (la boleta “(1, 2)” indica por ejemplo que se pro-
dujo empate en el primer juego y victoria del equipo
casa en el segundo juego), garantizando de esta manera
destacan la Universidad Purdue (1943), la Universidad de Notre Dame
(1952) y la Universidad de Israel (1954).
A Erdös se le considera el fundador de las matemáticas discretas, uno
de los fundamentos teóricos de las ciencias de la computación.
8.6. Algunos problemas abiertos en combinatoria 117
que siempre obtendremos al menos 1 resultado correcto.
Puede demostrarse por enumeración que 3 boletas son
necesarias en este caso.
3. Para n = 3 todav́ıa podemos analizar el problema man-
ualmente, enumerando todas las posibilidades, para obtener
σ3 = 5. El lector puede comprobar que las siguientes
5 boletas bastan para garantizar que obtendremos al
menos 2 resultados correctos: (0,1,2), (0,2,0), (1,1,0),
(1,2,2), (2,0,1). La solución no es única.
4. Para n = 4 el problema no es tan obvio como para
resolverlo manualmente, pues la cantidad de configu-
raciones a analizar es muy elevada. Sin embargo, con
paciencia y ayuda de una computadora obtenemos que
σ4 = 9. Por ejemplo,

Crie agora seu perfil grátis para visualizar sem restrições.