Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarte el uso de la web mediante el análisis de tus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúas navegando, consideramos que aceptas nuestra Política de cookies .

Sucesiones sin regularidades

La dificultad matemática de medir el tamaño de un conjunto carente de pautas.

BIG MOUTH/QUANTA MAGAZINE

He aquí un juego muy sencillo para entretenerse en un día lluvioso: usted y su oponente escriben en un papel los números del 1 al 9 y se turnan para tacharlos; el vencedor será el último que elimine un número sin que eso suponga haber tachado tres seguidos. ¡Juguemos! Puede empezar usted.

Supongamos que, tras cuatro turnos, la situación es la siguiente:

 

1  2  3  4  5  6  7  8  9

 

Ahora vuelve a tocarle a usted. Si tacha el 4 perderá, ya que eso eliminará tres cifras seguidas (3, 4 y 5). Y lo mismo ocurre si tacha el 7. Así que sus únicas posibilidades son eliminar el 1, el 2 o el 6. Pero, elija el que elija, yo siempre podré tachar después uno de los otros dos, tras lo cual usted se quedará sin opciones válidas.

Acabamos de presentar un juego muy simple tras el que se esconden algunas matemáticas interesantes. ¿Qué estrategias podemos seguir para ganar? Una posibilidad es ir creando huecos para que el oponente no tenga otra opción que completar una fila de tres números tachando el del centro; por ejemplo:

 

1  2  3  4  5  6  7  8  9

 

Otra técnica consiste en tachar los números contiguos a los que haya eliminado nuestro contrincante, para así forzarlo a completar una fila de tres por la derecha o por la izquierda, como aquí:

 

2  3  4  5  6  7  8  9

 

Sin embargo, con independencia de cómo juguemos, hay algo seguro: después de seis turnos, alguien tendrá que haber ganado. Esto se debe a que es imposible tachar siete de los nueve números sin eliminar tres seguidos (si no me cree, haga pruebas en un papel hasta convencerse). En este caso, decimos que seis es la «cota superior» al número de turnos totales que admite el juego.

Por tanto, y aunque en una situación dada no sepamos cuál es nuestra mejor opción, sí podemos asegurar que la partida nunca durará más de seis rondas. Esta idea puede generalizarse. Si jugamos con los números del 1 al 15, la partida no podrá alargarse más allá de los diez turnos. Y en general, si el número total de cifras es un múltiplo de 3, solo podremos tachar un máximo de 2/3 de ellos.

Encontrar una cota superior al número de turnos constituye un paso importante para entender las propiedades matemáticas de nuestro juego. Por ejemplo, tal vez esa cota nos permita encontrar una estrategia ganadora. O puede que nos sirva como punto de partida para entender lo que sucede cuando la cantidad total de cifras no es un múltiplo de 3. Y aunque conocer esa cota superior tal vez no parezca gran cosa, es mucho más de lo que podemos decir sobre otros juegos muy similares.

 

Progresiones aritméticas

Por ejemplo, cambiemos las reglas del juego para que ahora el perdedor sea el primero que tache tres números equidistantes, sea cual sea el tamaño del intervalo que medie entre dos de ellos. Eso quiere decir que perderemos si tachamos los números 2-3-4, al igual que antes, pero también si eliminamos 1-3-5 (ya que la distancia entre dos números consecutivos es siempre dos) o 1-4-7 (distancia igual a tres). Tales listas son progresiones aritméticas: sucesiones de números donde la diferencia entre dos elementos consecutivos se mantiene constante.

Volvamos a nuestra tabla inicial del 1 al 9 y juguemos con las nuevas reglas. Supongamos que la situación es la siguiente y que le toca a usted:

 

1  2  3  4  5  6  7  8  9

 

Debe saber que ya ha perdido. Si tacha el 1, obtendrá la progresión aritmética 1-3-5; si se decide por el 2, tendrá 2-5-8; el 4 crea la sucesión 3-4-5; el 6, 3-6-9; y el 7, 7-8-9. Haga lo que haga, es imposible no completar una progresión aritmética. Las nuevas reglas nos obligan a tener en cuenta muchas más situaciones. Y como consecuencia, el juego se complica de manera considerable y resulta mucho más difícil hallar una cota superior al número de turnos que durará una partida.

Para los matemáticos, la diversión está en convertir un simple juego con números en un juego contra las matemáticas mismas. El objetivo es averiguar cuánto puede durar una partida cuando comenzamos con una lista de cualquier tamaño. En otras palabras: dada una lista de números de longitud arbitraria, ¿cuántos podemos tachar antes de que entre los eliminados aparezca una progresión aritmética? Las reglas parecen simples, pero hoy por hoy nadie conoce la respuesta. Y sabemos aún menos sobre otras variantes. Juguemos un poco más y veamos a dónde nos llevan las matemáticas.

 

Conjuntos de Salem-Spencer

En el juego que acabamos de describir, una serie de turnos válidos constituye esencialmente un «conjunto de Salem-Spencer»: un subconjunto de {1, 2, 3, 4, 5, 6, 7, 8, 9} que no contiene progresiones aritméticas (el nombre de estos conjuntos se debe a los matemáticos Raphaël Salem y Donald Spencer, quienes los estudiaron en los años cuarenta del pasado siglo). Así pues, la cota superior que buscábamos no es más que el tamaño del mayor subconjunto de Salem-Spencer que podemos encontrar en nuestra lista de números. Sin embargo, hallar las jugadas que nos permiten llegar hasta él puede resultar muy difícil. Veamos por qué.

Comencemos de nuevo. Tras los dos primeros turnos, nadie puede haber perdido, así que supongamos que los números que hemos tachado son el 3 y el 5:

 

1  2  3  4  5  6  7  8  9

Ahora hemos de elegir un tercer número; es aquí donde tenemos que empezar a prestar atención. Al igual que en la primera versión del juego, hemos de impedir que se forme una progresión aritmética tanto entre los dos primeros números como a cada uno de sus lados. Por ejemplo, no podemos tachar el 4, ya que esto nos daría la progresión 3-4-5. Y tampoco podemos eliminar el 1, pues obtendríamos 1-3-5; ni el 7, pues eso nos daría 3-5-7. Dado que el 8 sí es una posibilidad, supongamos que ese es nuestro próximo movimiento:

 

1  2  3  4  5  6  7  8  9

 

Las cosas están a punto de complicarse. Nuestro objetivo sigue siendo el mismo: impedir que aparezca una progresión aritmética entre dos de los números ya seleccionados o a cualquiera de sus lados. Pero ahora hay muchas más posibilidades que debemos tener en cuenta, ya que hemos de considerar tres parejas de números.

Por un lado, sabemos qué podemos esperar. Para cada pareja posible de números hemos de evitar generar una progresión entre ellos o a sus lados. Pero las cosas ya no son tan predecibles como querríamos. El 3 y el 5 eliminan tres opciones: 1, 4 y 7. Pero el 3 y el 8 no suprimen ninguna, ya que los números que deberíamos evitar (–2, 5,5 y 13) ni siquiera están la lista. Y el 5 y el 8 solo eliminan el 2, ya que ni el 6,5 ni el 13 son posibles.

Por tanto, cada elección que tomemos eliminará algunas opciones, pero cuántas sean estas dependerá de lo que elijamos. Esa irregularidad hace que resulte muy difícil contar todas las posibilidades y hallar una cota superior al número de turnos de nuestra partida.

Sigamos jugando. Una opción legítima es el 6, así que procedamos a tacharlo:

 

1  2  3  4  5  6  7  8  9

 

Aquí termina nuestra partida. Ya sabemos que 1, 2, 4 y 7 pierden. Y tachar el 9 genera la progresión aritmética 3-6-9, por lo que no caben más opciones: hemos llegado tan lejos como podíamos.

Lo anterior demuestra que la colección de números {3, 5, 6, 8} es un conjunto de Salem-Spencer. Pero ¿es el mayor de todos los posibles? Sabemos que este conjunto concreto no puede agrandarse. Pero ¿tal vez una estrategia distinta nos hubiera permitido encontrar uno mayor? En otras palabras: ¿contiene el conjunto {1, 2, 3, 4, 5, 6, 7, 8, 9} algún subconjunto de más de cuatro elementos que no incluya progresiones aritméticas de tres términos?

La respuesta es afirmativa: {1, 2, 6, 8, 9}. Este subconjunto corresponde a cinco turnos válidos de nuestro juego y, por tanto, es un conjunto de Salem-Spencer. Y sabemos también que es máximo, ya que, para la lista inicial {1, 2, 3, 4, 5, 6, 7, 8, 9}, es posible demostrar que el mayor conjunto posible de Salem-Spencer tiene cinco elementos. No obstante, si partimos de la lista de los n primeros números naturales, {1, 2, 3, ..., n}, la respuesta no siempre estará tan clara. De hecho, hoy por hoy solo sabemos qué ocurre para n ≤ 209.

 

Secuencias polinómicas

A los matemáticos les encantaría saber el tamaño exacto del mayor subconjunto posible de Salem-Spencer para la lista {1, 2, ..., n}. Pero, en general, lo máximo que han conseguido es establecer algunas cotas. Pero incluso esto resulta considerablemente difícil, debido en parte a las irregularidades de las que hablábamos antes: tachar un número puede eliminar de golpe muchas opciones, pero otras veces solo suprimirá unas pocas.

Tales irregularidades quedan patentes en la tabla adjunta, donde se muestra el tamaño del mayor subconjunto de Salem-Spencer para varios valores de n. En nuestro juego, donde n = 9, el máximo subconjunto de Salem-Spencer tiene tamaño 5. Pero si añadimos el 10 a la lista, eso no aumenta el tamaño del subconjunto correspondiente de Salem-Spencer, que sigue siendo 5. En cambio, al pasar de 12 a 13 y de 13 a 14, el tamaño máximo cambia de 6 a 7 y de 7 a 8, respectivamente. Y después, tendremos que añadir otros seis números para que el tamaño del máximo subconjunto de Salem-Spencer aumente en una unidad.

Dos resultados clásicos en este campo, conocidos como teorema de Roth y teorema de Szemerédi, permiten establecer cotas al tamaño de tales conjuntos, a menudo mediante el empleo de técnicas matemáticas avanzadas como la teoría ergódica y las transformadas de Fourier. Y hace unos años, el medallista Fields Timothy Gowers reanalizó el teorema de Szemerédi y encontró una importante cota superior al tamaño de los conjuntos que no contienen progresiones aritméticas de longitud k. Pero, si queremos calcular la cota superior para nuestro juego, donde n = 9 (el tamaño de nuestra lista de números) y k = 3 (la longitud de las progresiones aritméticas que intentamos evitar), una parte de nuestro cálculo implicaría evaluar 24096, ¡un número de más de 1200 dígitos!

Aunque nada de lo anterior resulta tremendamente útil para la vida cotidiana, este tipo de cotas proporcionan un cierto control matemático sobre algunos conjuntos que aún no se entienden bien. Por ejemplo, hasta hace poco no existían cotas similares para las secuencias polinómicas: generalizaciones de las progresiones aritméticas con sumas y potencias, como por ejemplo:

2+3,  2+32,  2+33, ...

Tales secuencias son más complejas que las progresiones aritméticas, lo que hace que el juego consistente en elegir subconjuntos libres de ellas resulte mucho más difícil de analizar. Con todo, establecer una cota superior al tamaño máximo de dichos conjuntos nos deja un paso más cerca de entenderlos, que es el objetivo que persiguen los matemáticos cada vez que se enfrentan a un juego de números.

 

Este artículo apareció originalmente en QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión pública de la ciencia.

Puedes obtener el artículo en...

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.