El número de Erdős

El problema de la semana pasada fue abordado de forma muy ingeniosa por una lectora que, lamentablemente, luego borró su comentario. Veamos cómo lo abordaron en su día los matemáticos húngaros Paul Erdős y Georges Szekeres, colaboradores habituales y coautores del teorema Erdős-Szekeres. Partieron del principio del palomar y pensaron en dividir el conjunto de los 2n primeros números {1, 2, …, 2n} en n subconjuntos tales que —tomando n + 1 números del conjunto inicial— al menos dos de ellos estuvieran en un mismo subconjunto. De ese modo, si dichos subconjuntos fueran tales que para cualquier par de números de un mismo subconjunto uno fuera múltiplo del otro, quedaría demostrada la afirmación de partida.

Para ello, los n subconjuntos se definen como las intersecciones del conjunto {1, 2, …, 2n} con los siguientes conjuntos: {1, 2, 2², 2³…}, {3, 3 x 2, 3 x 2², 3 x 2³…}, {5, 5 x 2, 5 x 2², 5 x 2³,…}, …, {n-1, (n-1) x 2, (n-1) x 2², n-1) x 2³…}, en los que cada elemento divide al siguiente de su subconjunto, y además cada número del conjunto inicial {1, 2, …, 2n} puede escribirse de forma única como (2m-1) x 2ᴷ, luego pertenece a uno de esos conjuntos. Una explicación un tanto compleja que Bretos Bursó resume así:

“Todo número natural es el producto de una parte par y una parte impar (el producto de sus factores primos iguales a 2 y el de los factores primos impares). Si dos números distintos tienen la misma parte impar entonces uno de ellos divide al otro (el más veces divisible por 2 es múltiplo del otro). Los n + 1 números que tomamos tienen n posibles partes impares (1, 3, 5..., 2n-1), luego al menos hay dos con la misma parte impar”.

Y hablando de Erdős y de colaboraciones entre matemáticos, no se puede dejar de mencionar el número de Erdős. El prolífico matemático húngaro tuvo nada menos que 509 colaboradores directos, cuyo número de Erdös (nE) es 1; quienes colaboraron con cualquiera de estos 509, pero no directamente con Erdös, tiene un nE 2 (son más de seis mil), y así sucesivamente.

¿Cuál crees, haciendo una estimación fermiana, que puede ser tu número de Erdős? Me conformo con una aproximación razonable. (Pista: si lees asiduamente esta sección, lo tienes mucho más fácil).

La conjetura de Erdős-Szekeres

No hay que confundir el antes mencionado teorema de Erdős-Szekeres con la conjetura del mismo nombre.

El teorema establece que para cualquier par de números naturales (enteros y positivos) r y s, cualquier sucesión de longitud igual o mayor que (r-1)(s-1) + 1 contiene una subsucesión monótonamente creciente de longitud s o una subsucesión monótonamente decreciente de longitud r.

Suena complicado, pero un sencillo ejemplo aclarará el concepto: para r = 3 y s = 2, con lo que (r-1)(s-1) + 1 = 3, cualquier permutación de tres números tiene una subsucesión creciente de longitud tres o una subsucesión decreciente de longitud dos. Tomando las seis posibles permutaciones de los números 1, 2 y 3 (y escribiendo las sucesiones de forma simplificada):

• 123 tiene una subsucesión creciente de longitud tres en sí misma: 123
• 132 tiene una subsucesión decreciente de longitud dos: 32
• 213 tiene una subsucesión decreciente de longitud dos: 21
• 231 tiene dos subsucesiones decrecientes de longitud dos: 21 y 31
• 312 tiene dos subsucesiones decrecientes de longitud dos: 31 y 32
• 321 tiene tres subsucesiones decrecientes de longitud dos: 32, 31 y 21

¿Cómo abordarías la demostración de este teorema desde el principio del palomar? (No pido una demostración rigurosa, sino solo un plan de ataque).

En cuanto a la conjetura de Erdős-Szekeres, es una generalización del “problema del final feliz”, denominado así por Erdős porque propició el matrimonio de su amigo y colaborador Georges Szekeres con la matemática australiana Esther Klein. Pero ese es otro artículo.