94. (Mayo 2012) Sucesiones De Bruijn
Imprimir
Escrito por Pedro Alegría (Universidad del País Vasco)   
Miércoles 02 de Mayo de 2012

El brujo en sociedadEl pasado 17 de febrero ha fallecido el matemático holandés Nicolaas de Bruijn (1918-2012). A lo largo de su dilatada carrera ha cosechado logros importantes. De hecho, su nombre está asociado a conceptos y resultados como la constante de De Bruijn-Newman (relacionada con la hipótesis de Riemann), los teoremas de De Bruijn-Erdösfunción de Dickman-De Bruijnsucesión de De Bruijn, definida por primera vez en un artículo de 1946, la cual tiene aplicaciones en la magia matemática. Por ese motivo, aprovechamos este rincón para rendir homenaje a este notable matemático.


Nicolaas de Bruijn

Antes de definir las sucesiones de De Bruijn, nos familiarizaremos con ellas por medio de un juego de cartas. El primero que utiliza esta sucesión, antes de haberse descubierto, es el titulado COLURIA, que aparece en el libro “Thirty card mysteries” de Charles Jordan, publicado en 1919.

Charles Jordan
Charles Jordan

El efecto es el siguiente:

El mago entrega una baraja de piquet (32 cartas, del 7 al as de cada palo) a un espectador y se aleja a cierta distancia. Le pide al espectador que corte por cualquier lugar y que reparta sobre la mesa seis manos de cinco cartas. Las dos cartas restantes, sin verlas, las guarda en su bolsillo. A continuación, nombra en voz alta únicamente los colores de las cartas superiores de cada montón. Inmediatamente, el mago nombra los valores de las cinco cartas inferiores de cada montón, así como los de las cartas ocultas en el bolsillo del espectador.

¿Cómo es posible?
El propio Charles Jordan afirma que la sutil ordenación empleada para este juego será nueva para la mayoría de los magos ya que sólo la distribución de los colores da información suficiente para determinar los valores de las cartas. Esto es debido a que la baraja puede ordenarse de modo que cada secuencia de seis colores sea única y aparezca sólo una vez en la baraja. Dicho esquema se conoce como ciclo binario de De Bruijn. La ordenación propuesta por Jordan es la siguiente:

AP-KT-QT-10P-7T-JP-7C-QP-9P-AT-8T-
10C-AR-JT-8P-9T-9C-8R-KC-10T-KP-QC-
9R-AC-JR-7P-QR-JC-7R- 10R-8C-
KR

(donde los símbolos R, C, T y P representan rombos, corazones, tréboles y picas, respectivamente).

Una vez que el espectador ha seguido las instrucciones del mago, vuelve cara arriba las cartas superiores de cada montón, que son las últimas repartidas, y nombra únicamente los colores. Como dicha secuencia de colores aparece sólo una vez en el conjunto de las 32 cartas, el mago sólo tiene que buscar disimuladamente en una hoja donde está anotada la lista anterior, en una distribución circular, y encontrar dicha secuencia. Las dos cartas siguientes al conjunto de las seis cartas correspondientes a la secuencia de colores son las que tiene el espectador en su bolsillo y las seis siguientes a ellas son las cartas inferiores de cada montón repartido sobre la mesa.

Por ejemplo, si el espectador indica que los colores de las cartas son

roja-roja-roja- roja-negra-negra,

el mago sabe que se trata de las cartas 7R- 10R-8C-KR-AP-KT, de modo que las cartas del bolsillo son QT y 10P y las cartas inferiores de cada montón son 7T-JP-7C-QP-9P-AT.

La idea que subyace de esta situación nos conduce a la siguiente definición:

Dado un alfabeto (o conjunto ordenado) A de tamaño k, una sucesión cíclica B(k,n) de elementos de A se llama sucesión de De Bruijn cuando toda subsucesión de n elementos de A aparece como máximo una vez en B(k,n) de forma consecutiva. La sucesión será maximal cuando todas las subsucesiones de longitud n aparezcan exactamente una vez en B(k,n).

Para el caso k = 2, Camille Flye Sainte-Marie probó en 1894 la existencia de estas sucesiones para cualquier n, y el caso general de la existencia de sucesiones para cualquier k y cualquier n fue probada por Tanja van Ardenne-Ehrenfest y el propio De Bruijn. Es fácil ver que la longitud de tal sucesión maximal es kn y se ha demostrado, mediante técnicas de teoría de grafos, que hay fórmula distintas sucesiones B(k,n) maximales. Pero el origen de estas sucesiones es mucho más antiguo (como se cuenta en la Wikipedia) y los 64 hexagramas místicos el libro del oráculo chino I Ching forman una sucesión B(2,6) (una de sus representaciones corresponde a la imagen que encabeza esta entrega, cuyo original está en abrahadabra.com). También son destacables sus aplicaciones en teoría de códigos y otros campos.

Los primeros ejemplos pueden obtenerse fácilmente. Si consideramos el conjunto A = {R,N} de los colores rojo y negro, para n = 2, la única sucesión B(2,2) es


R
N
R

N

Para n = 3, existen dos sucesiones B(2,3), que son


R R
N

R
R

N

N N

y

N N
R

N
N

R

R R

(cada una recíproca de la otra y donde se supone la sucesión recorrida en sentido antihorario).

Para comprobar que RRRNNNRN es una sucesión maximal de De Bruijn, basta describir todas las subsucesiones de 3 elementos consecutivos, las cuales son:

RRR, RRN, RNN, NNN, NNR, NRN, RNR, NRR

obteniéndose las ocho permutaciones de longitud tres con los elementos de A.

Utilizando grafos eulerianos se pueden construir secuencias de orden mayor, como se muestra en el siguiente diagrama. Basta encontrar un recorrido por el grafo que recorra todas las aristas exactamente una vez.


Grafo de construcción de B(2,4)

En el juego de Jordan se utiliza la siguiente sucesión B(2,6), no maximal:

NNNNNNRNNNNRRNNNRRRNNRRRRNRRRRRR

y puede ser un entretenimiento apasionante descubrir cuáles de las 26 = 64 diferentes subsucesiones de 6 elementos consecutivos están contenidas en esta sucesión.

Diversas variantes de este juego se han ideado con posterioridad al publicado por Charles Jordan. En el número de diciembre de 2008 de la columna “CardColm” de la Mathematical Association of America, conducida por Colm Mulcahy, aparecen dos versiones.


Colm Mulcahy junto a Martin Gardner

La primera de ellas, más sencilla de recordar, utiliza la sucesión B(2,3) RRRNNNRN con las cartas 8R, 5C, 4R, AT, 7P, 6T, 3C, 2P. Para facilitar su memorización, basta observar que están todos los valores, del as al ocho, y los palos están alternados dentro de su mismo color.

Para realizar el juego, se colocan previamente dichas cartas en la parte superior de la baraja, en el orden indicado, y se procede como sigue:

El mago mezcla la baraja (pero sin desordenar las ocho primeras cartas) y reparte sobre la mesa, formando un círculo, las ocho primeras cartas. Se vuelve de espaldas y pide a tres espectadores que retiren y guarden tres cartas consecutivas del círculo, una carta cada uno, que aparten las otras cinco y las pierdan en la baraja. A continuación el mago se vuelve cara hacia los espectadores y pregunta quién o quiénes de ellos tienen una carta roja. Con esta información, adivina inmediatamente las cartas que guardan cada uno de ellos.

Para saber cuáles son dichas cartas, basta reconocer la secuencia de colores en la sucesión original.

Otra posibilidad es pedir a los espectadores que sumen los valores de las tres cartas elegidas y anuncien dicha suma. Como los posibles valores de la suma de tres cartas consecutivas de la secuencia son 17, 10, 12, 14, 16, 11, 13 y 15, el mago puede determinar cuáles son las cartas elegidas por los espectadores.

El segundo juego descrito por Mulcahy es el siguiente.

El mago entrega una baraja a varios espectadores para que, sucesivamente, corten y completen el corte. A continuación, el primer espectador retira y se guarda la carta superior, entrega la baraja al segundo espectador, quien a su vez retira y se guarda la nueva carta superior. Esta operación se repite con otros dos espectadores. El mago anuncia que adivinará los valores de las cartas en dos fases: primero las posibles cartas rojas y luego las cartas negras. Pide entonces que se levanten los espectadores que han elegido una carta roja. Si hay alguien que se levanta, casi inmediatamente desvela los valores de sus cartas y, por último, adivina también los valores de las cartas del resto de espectadores, en el orden que ellos le indiquen.

Como se puede adivinar, el mismo principio anterior se aplica en esta ocasión. Las cartas están ordenadas de modo que la secuencia circular de colores no tenga ninguna subsucesión de longitud cuatro que se repita más de una vez. Como la longitud de una sucesión maximal del tipo B(2,4) es igual a 16, el juego descrito sólo puede realizarse con 16 cartas, cuyos colores estarán ordenados según la secuencia

RRRRNNNNRNNRRNRN.

Para solventar esta dificultad, Mulcahy propone elegir las mismas 16 cartas de tres barajas iguales y formar tres secuencias iguales de longitud 16 formadas por dichas cartas. De este modo, la baraja tendrá 48 cartas y no importa el lugar donde se corte pues las cuatro primeras cartas de la baraja formarán una única permutación de los colores rojo-negro. Además, es conveniente elegir 16 cartas cuyo orden sea fácil de recordar pero que no sea demasiado obvio para el público.

Otra opción posible sería utilizar un alfabeto diferente –también de dos elementos– para formar la sucesión como, por ejemplo, A={P,R} donde P representa un palo concreto y R el resto de los palos. Así, la primera parte de la adivinación consiste en preguntar quiénes tienen una carta del palo concreto: sabiendo la posición de dichas cartas en la secuencia, es posible adivinar todas ellas. Este enfoque permite adaptar el juego a la baraja española ya que, precisamente, esta baraja tiene 48 cartas si se utilizan los ochos y los nueves y no existe la distinción entre los colores de los diferentes palos.

Una versión más ambiciosa sería considerar una baraja completa de 52 cartas. Como la potencia de dos más próxima es 64, hace falta considerar una sucesión de De Bruijn B(2,6) y eliminar de alguna forma doce elementos de la sucesión. Esto permitiría adivinar las cartas de seis espectadores. En el libro de reciente publicación Magical Mathematics (una reseña muy completa es de Alex Stone para el periódico The Wall Street Journal), escrito por Persi Diaconis (matemático y mago) y Ronald Graham (matemático y malabarista), se puede encontrar esta original versión, con algunos ingredientes adicionales para recordar sin demasiada dificultad las cartas de la secuencia.


Ronald Graham (izquierda), Persi Diaconis (derecha) y su libro (centro)

Pero vamos a posponer para otra ocasión las aportaciones de estos dos polifacéticos matemáticos.

Observaciones:

  • En la comunidad mágica, los juegos basados en las sucesiones de De Bruijn se conocen como basados en los códigos de Gray. Un código de Gray es un sistema de numeración binaria en el que dos valores consecutivos se diferencian únicamente en un bit. La ventaja de este sistema es su mayor facilidad en detectar y corregir errores (basta observar que, en el sistema binario posicional, hay números consecutivos que se diferencian en todas sus cifras, como son 2n-1 y 2n). Su uso más común es el de corrección de errores en comunicaciones digitales como el de la televisión por cable. Aunque los conceptos no son equivalentes, generalmente se construyen las sucesiones de De Bruijn de modo que dos términos consecutivos se diferencian sólo en un término, con lo que queda determinado un código de Gray. También se puede construir una sucesión B(2,k) escribiendo de forma consecutiva los 2knúmeros del código de Gray con k cifras y eliminando adecuadamente las cifras que hacen que las subsucesiones de orden k se repitan en la sucesión.

  • Después de Charles Jordan, muchos magos han estudiado estos códigos y han inventado sus propias versiones y variaciones del juego. Podemos destacar, entre ellos, a Alex Elmsley, Leo Boudreau, Reinhard Muller, Denis Behr, Doug Dyment, etc.

  • También pueden usarse las sucesiones de De Bruijn como rompecabezas, como explica Alex Bogomolny en "From Lewis Carroll to Archimedes" de la página Interactive Mathematics Miscellany and Puzzles.


Esta dirección electrónica esta protegida contra spambots. Es necesario activar Javascript para visualizarla Esta dirección electrónica esta protegida contra spambots. Es necesario activar Javascript para visualizarla

 
Volver