Skip to Content

Visor

Volver al listado

Para cenar...palíndromos.

Esta es la historia de uno de los problemas que me acabó atrayendo tanto como para comenzar una tesis doctoral...y también de cómo acabé convirtiéndome en @palindromiano.

Empecemos por el principio: vamos a cenar.

Sentándose alrededor de la mesa

Queremos sentar a cenar a mm personas en una mesa circular. En la mesa tenemos un total de m+n sillas, dispuestas a igual distancia unas de otras. Pero esos tiempos que corren son chungos. La amenaza del COVID impone mantener una distancia social. ¿De qué forma se tienen que sentar los mm comensales de manera que estén lo más alejados posible? 

En la siguiente simulación de GeoGebra tienes varias posibilidades para colocar a 5 personas en 14 sillas. Prueba con esas y con algunas otras que se te ocurran.

Quizá veas la respuesta a alguna de las siguientes preguntas.

  • ¿Cuál es la estrategia óptima para separar al máximo a los comensales?
  • ¿Funcionará siempre para cualquier número de personas y de sillas?
  • ¿Cómo es el patrón resultante personas - sillas? 

Para resolver este problema bien, bien, bien, necesitamos una noción llamada palabra de Christoffel. Vamos con ella:

Palabras de Christoffel

Imagina que tenemos una recta de pendiente racional y=pqxy=\frac{p}{q}x (podemos suponer que la fracción es irreducible). Los puntos de coordenadas naturales que están más cerca de la recta, pero por debajo de ella, tienen por coordenadas k,pqk\left( k,\left\lfloor \frac{p}{q} k \right\rfloor\right) , donde x\left\lfloor x \right\rfloor representa la parte entera de xx. Si unes esta serie de puntos obtienes un zig-zag formado por segmentos horizontales o diagonales, según sea  cero o 1 la diferencia:

k+1,pq(k+1)-k,pqk\left( k+1,\left\lfloor \frac{p}{q} (k+1) \right\rfloor\right)-\left( k,\left\lfloor \frac{p}{q} k \right\rfloor\right)

A esta secuencia de 0 y 1 de longitud $q$ se la conoce como palabra de Christoffel.

Hemos obtenido así una secuencia de 0 y 1 que es una "discretización" de nuestra recta y=pqxy=\frac{p}{q}x, convirtiendo el plano inclinado en una escalera. Mucho más cómoda, donde va a parar. 

Parte entera, zig-zags, patrones de ceros y unos...aunque pueda parecerlo, todo esto no es nada difícil. Qué mejor que un applet de GeoGebra para cacharrear con esta noción y entenderla bien antes de seguir leyendo. Prueba a mover la pendiente y a ver como afecta ésta al zig-zag y a la palabra de Christoffel generada. 

Por supuesto, la fracción debe ser irreducible y la longitud de la palabra debe coincidir con el denominador. Si no, lo que se produce es una "potencia" de una palabra de Christoffel.
Por ejemplo, en la figura se muestra la palabra de Christoffel de pendiente 712, que es 010101101011. Esta palabra tiene 7 unos y 5 ceros:

Palabra de Christoffel de pendiente 7/12

Las palabra de Christoffel w de pendiente 0<pq<1 verifica unas propiedades sorprendentes:

  • Son siempre de la forma w=0u1 siendo u una palíndromo (observa la simetría de la figura). 
  • La palabra ww descompone de modo único como concatenación de dos palabras de Christoffel w=w1·w2. En nuestro ejemplo, 010101101011=0101011 · 01011. Y como esto lo podemos hacer recursivamente...dentro de cada palabra de Christoffel hay muuuuchos palíndromos. Locurón. 
  • La descomposición de ww como pareja de Christoffel w1·w2w_1\cdot w_2 se produce justo por el punto del Zig-zag más próximo a la recta . En el caso de nuestro ejemplo, el punto de ruptura es el séptimo (punto marcado de azul en la figura  anterior). 

Esta descomposición da pie a construir de forma recursiva TOOODAS las palabras de Christoffel. Partimos de la pareja (0,1). Con las dos transformaciones:

Generadores del árbol de Christoffel

generamos el árbol que organiza todas las palabras de Christoffel junto con su descomposición como pareja de Chrisforrel:

Árbol de ChristoffelBueno, habría que demostrar que cada palabra aparece exactamente una vez, habría que ver cómo calcular el camino que conduce a cada palabra...si tenéis interés de todo esto y mucho más, podéis consultar este fantástico paper

Ahora, sigamos. Porque una construcción tan sencilla como el zig - zag de las palabras de Christoffel conecta con ideas fundamentales en la teoría de la aritmética:

  • Si w=w1·w2w=w_1\cdot w_2 es factorización en palabras de Christoffel de wwpq,p1q1,p2q2 son las pendientes de w,w1,w2respectivamente, entonces se verifica la siguiente relación entre estas fracciones:

pq=p1+p2q1+q2\frac{p}{q}=\frac{p_1+p_2}{q_1+q_2}

Por ejemplo, nuestra palabra de Christoffel 010101101011 de pendiente 712\frac{7}{12} descompone en dos palabras 0101011 y 01011 de pendientes respectivas 47\frac{4}{7}35\frac{3}{5}. Fíjate que

712=4+37+5\frac{7}{12}=\frac{4+3}{7+5}

Y es aquí donde conectamos con una idea muy muy tocha de la aritmética. ¿Conoces el árbol de Stern-Brocot? Es este:

En este árbol se organizan TOOOOOODOS los números racionales y permite escribir cada irracional como sucesión de unas fracciones muy particulares: los convergentes. La mejor forma de aproximar irracionales mediante racionales. Probablemente ;)

Justo la mitad izquierda (recuadrada) coincide con las pendientes de las palabras de Christoffel según se sitúan en el árbol de parejas de Christoffel. Son los mismos árboles, vaya.

Bueno, ya está bien de palabras de Christoffel. Volvamos a nuestro problema de las personas y las sillas. Que empieza la cena y no les hemos ni sentado. 

A cenaaaaaar

Vamos a sentar a las 5 personas (representadas por 1s) colocando entre ellos las 8 sillas vacías (representadas mediante ceros).  Para ello podemos empezar con la siguiente distribución:

[11111 · 00000000]

La notación [w] hace referencia a que no estamos describiendo una palabra como tal, sino una palabra circular, esto es una clase de equivalencia módulo rotaciones. Ahora vamos a separar a las cinco personas, ¡que no están guardando la distancia! Intercalamos 5 sillas entre persona y persona:

[01·01·01·01·01· 000]

Sobran tres sillas, que podemos colocar Colocamos ahora las tres sillas que podemos aprovechar para separar aún más a tres de las cinco personas:

[001·001·001·01·01]

Y ahora los grupos 01 (silla vacía - persona) los intercalamos en dos de los tres grupos  001:

[001·00101·00101]

Y ahora sólo queda un grupo de 001 que no podemos repartir. Con lo que la solución COVID sería

[0010010100101]

que es la clase de equivalencia módulo rotaciones de la palabra de Christoffel de pendiente 513\frac{5}{13}:

A cenaaar

Fíjate que en el fondo estamos utilizando un algoritmo recursivo MUUUUY famoso:

13-8=5

8-5=3

5-3=2

3-2=1

Nuestro querido algoritmo de Euclides :)

Claro, si el número de personas y el número de sillas no son primos entre sí, por ejemplo 6 personas y 14 sillas (8 sillas libres), la cosa cambia, aunque sólo ligeramente:

[111111·00000000]

[01·01·01·01·01·01·00]

[001·001·01·01·01·01]

[00101·00101·01·01]

[0010101·0010101]

En esta ocasión, la distribución de sillas vacías y personas no son rotaciones de una palabra de Christoffer, sino de dos de pendiente 37\frac{3}{7} 0010101·0010101. Y es que 614=2·32·7\frac{6}{14}=\frac{2\cdot 3}{2\cdot 7}.

En resumen, si mm y nn son dos enteros que verifican que mn=p·kq·k\frac{m}{n}=\frac{p\cdot k}{q\cdot k}, siendo pq<1\frac{p}{q}<1 una fracción irreducible, la distribución de asientos vacíos y ocupados al sentar las mm personas alrededor de una mesa circular con un total de nn sillas es una rotación de la palabra wkw^k, donde ww es la palabra de Christoffel de pendiente pq<1\frac{p}{q}<1

Los lugares donde se sientan los 5 invitados pueden verse como el subconjunto de {2,5,7,10,12}\{2,5,7,10,12\}

Hay muchas situaciones de todo tipo en las que aparecen de forma natural los conjuntos con una distribución máxima como los de las personas y los sillas vacías:

Escalas musicales: conjuntos de regularidad máxima (Maximally even sets)

La escala diatónica distribuye los tonos y los semitonos según una secuencia de Christoffel: [Tono - Tono - Tono - Semitono - Tono - Tono - Semitono]. También la distribución de las teclas negras y blancas del piano obedece a este tipo de distribución:

Escala diatónica

Esto llevó a J. Douthett y J. Claugh a formaliar las escalas con esta propiedad, introduciendo una noción que ha tenido muchísima repercusión en la teoría musical de escalas actual: Maximally Even Sets.

Ritmos euclidianos

Sin salirnos de la música: otro ejemplo con gran repercusión científica: los ritmos euclidianos. Un ritmo puede entenderse de la siguiente manera: en una unidad de tiempo que se repite cíclicamente (nuestro círculo)  distribuimos una serie de silencios (sillas vacías) y sonidos (personas). Pues bien en el extraordinario artículo "The Distance Geometry of Music" (Erik D. Demaine et al.) analizan más de 30 ritmos clásicos que se distribuyen de forma que los sonidos y los silencios se distribuyen cíclicamente de una forma parecida a nuestras personas alrededor de la mesa. Por ejemplo, el ritmo de Bossa-nova:

El ritmo de Bossa-nova es un ejemplo de ritmo euclideano
Ritmo de Bossa-Nova

Dibujando rectas en el ordenador

Cuando dibujamos una línea recta oblicua en el ordenador no estamos dibujando una línea recta oblicua con el ordenador. Fíjate que la pantalla no es sino un rectángulo enorme formado por píxeles. Y los píxeles quedarán pintados o no con una forma parecida a la siguiente:

A cellular-straight line
A cellular-straight line

La noción de segmento rectilíneo digital fue introducida en los años 70 y desde entonces ha suscitado mucho interés (ver el artículo de A. Rosenfield y R. Klette). 

Diseño de calendarios: los años bisiestos

Como sabes, la duración de un año no es exactamente 365. La razón entre lo que tarda la Tierra en dar una vuelta alrededor del Sol (año) y lo que tarda ésta en dar una vuelta sobre sí misma (día) es aproximadamente 365.242199... Este desfase (0.24219...) impone la necesidad de añadir un día de tanto en tanto. La distribución de años bisiestos frente años no bisiestos en el Calendario Gregoriano queda fijada como una vez de cada cuatro años, salvo que el año sea divisible por 100 pero no por 400. Esta regla determina la siguiente aproximación de la duración del año:

365+14-1100+1400=365.2425365 + \frac{1}{4}-\frac{1}{100}+\frac{1}{400}=365.2425

La palabra de Christoffel de pendiente 0.24250.2425 nos proporciona, por tanto, la secuencia de años bisiestos en el Calendario Gregoriano.

Coda

En este blog ya he descrito otro problema a mitad de camino entre la geometría, la aritmética, la Combinatoria Algebraica de palabras y la teoría de la música: escalas musicales y el Teorema de los tres pasos.

En fin, como véis las secuencias de Christoffel y los palíndromos que contienen aparecen por doquier, en este mundo en el que se entrelaza tanto lo digital y lo analógico; lo discreto y lo continuo. Durante un tiempo estuve verdaderamente obsesionado por este tipo de patrones. No en vano llegué a escribir una tesis sobre escalas bien formadas (cuyos patrones son palabras de Christoffel) y la Combinatoria Algebraica de Palabras. 

Cuando en 2014 decidí crearme una cuenta de Twitter, pedí ayuda a mi mujer para buscar un nombre, Ella, entre el hartazgo y el cariño me bautizó: PALINDROMIANO.

Esta entrada participa en la Edición 12.2: Carl Friedrich Gauss del Carnaval de Matemáticas, que en esta ocasión organiza Gaussianos.