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.

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=\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 $\left( k,\left\lfloor \frac{p}{q} k \right\rfloor\right)$ , donde $\left\lfloor x \right\rfloor$ representa la parte entera de $x$. Si unes esta serie de puntos obtienes un zig-zag formado por segmentos horizontales o diagonales, según sea  cero o 1 la diferencia:

$\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=\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. 

Las palabra de Christoffel $w$ de pendiente $0<\frac{p}{q}<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 $w$ descompone de modo único como concatenación de dos palabras de Christoffel $w=w_1·w_2$. 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 $w$ como pareja de Christoffel $w_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:

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

Bueno, 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=w_1\cdot w_2$ es factorización en palabras de Christoffel de $w$ y  $\frac{p}{q},\frac{p_1}{q_1},\frac{p_2}{q_2}$ son las pendientes de $w,w_1,w_2$respectivamente, entonces se verifica la siguiente relación entre estas fracciones:

$\frac{p}{q}=\frac{p_1+p_2}{q_1+q_2}$

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

$\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. 

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:

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:

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:

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 + \frac{1}{4}-\frac{1}{100}+\frac{1}{400}=365.2425$

La palabra de Christoffel de pendiente $0.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.