secuencia de Thue-Morse

Para calcular el n -ésimo elemento t _n , escriba el número n en binario . Si la cantidad de unos en esta expansión binaria es impar, entonces t _n = 1 ; si es par, entonces t _n = 0. [ ^{2 ] Es} decir, t _n es el bit de paridad par para n . John Conway et al . consideraron que los números n que satisfacen t _n = 1 son odiosos (destinados a ser similares a los números impares ), y los números para los cuales t _n = 0 son malvados (similares a los números pares ).

Este método conduce a un método rápido para calcular la secuencia de Thue-Morse: comience con t ₀ = 0 y luego, para cada n , encuentre el bit de orden más alto en la representación binaria de n que sea diferente del mismo bit en la representación de n − 1 . Si este bit está en un índice par, t _n difiere de t _{n −1} , y de lo contrario es igual a t _{n −1} .

En Python :

from typing import Iteratordef generate_sequence ( seq_length : int ) -> Iterator [ int ]: """Secuencia Thue-Morse.""" valor : int = 1 para n en rango ( seq_length ): # Nota: se asume que (-1).bit_length() da 1 x : int = ( n ^ ( n - 1 )) . bit_length () + 1 si x & 1 == 0 : # El índice de bits es par, así que cambia el valor valor = 1 - valor da como resultado valor

El algoritmo resultante tarda un tiempo constante en generar cada elemento de la secuencia, utilizando solo un número logarítmico de bits (número constante de palabras) de memoria. ^{[ 3 ]}

La secuencia de Thue-Morse es la secuencia t _n que satisface la relación de recurrencia.

${\displaystyle {\begin{aligned}t_{0}&=0,\\t_{2n}&=t_{n},\\t_{2n+1}&=1-t_{n},\end{aligned}}}$

para todos los enteros no negativos n . ^{[ 2 ]}

La secuencia Thue-Morse es una palabra morfológica : ^{[ 4 ]} es la salida del siguiente sistema Lindenmayer :

^{La secuencia Thue-Morse ,} en la forma dada anteriormente, como una secuencia de bits , se puede definir recursivamente mediante la operación de negación bit a bit . El primer elemento es 0. Una vez que se han especificado los primeros 2n elementos, formando una cadena s , los siguientes 2n elementos deben formar la negación bit a bit de s . Ahora que hemos definido los primeros 2n ⁺¹ elementos, procedemos a la ^{recursión .}

Explicando detalladamente los primeros pasos:

• Comenzamos con 0 .
• La negación bit a bit de 0 es 1 .
• Combinando estos, los dos primeros elementos son 01 .
• La negación bit a bit de 01 es 10 .
• Combinando estos, los primeros 4 elementos son 0110 .
• La negación bit a bit de 0110 es 1001 .
• Combinando estos, los primeros 8 elementos son 01101001 .
• Etcétera.

Entonces

• T ₀ = 0 .
• T ₁ = 01 .
• T ₂ = 0110 .
• T ₃ = 01101001 .
• T ₄ = 0110100110010110 .
• T ₅ = 01101001100101101001011001101001 .
• T ₆ = 0110100110010110100101100110100110010110011010010110100110010110 .
• Etcétera.

En Python :

def thue_morse_bits ( n : int ) -> int : """Devuelve un entero que contiene los primeros 2**n bits de la secuencia Thue-Morse, con el bit de menor orden en primer lugar.""" bits = 0 for i in range ( n ): bits |= (( 1 << ( 1 << i )) - 1 - bits ) << ( 1 << i ) return bits

Que luego se puede convertir en una cadena (invertida) de la siguiente manera:

n = 7 print ( f " { thue_morse_bits ( n ) : 0 { 1 << n } b } " )

Una función generadora para la secuencia se puede definir mediante:

${\displaystyle \prod _{i=0}^{\infty }\left(1-x^{2^{i}}\right)=\sum _{j=0}^{\infty }(-1)^{t_{j}}x^{j},}$

donde t _j es el j -ésimo elemento si comenzamos en j = 0 .

El conjunto de números malvados (números n tales que t _n = 0 ) forma un subespacio de los enteros no negativos bajo la suma nim ( OR exclusivo bit a bit ). En el juego de Kayles , los valores nim malvados aparecen en unas pocas (un número finito de) posiciones del juego, mientras que todas las posiciones restantes tienen valores nim odiosos.

El problema de Prouhet-Tarry-Escott se puede definir como: dado un entero positivo N y un entero no negativo k , particione el conjunto S = { 0, 1, ..., N − 1 } en dos subconjuntos disjuntos S ₀ y S ₁ que tengan sumas iguales de potencias hasta k , es decir:

${\displaystyle \sum _{x\in S_{0}}x^{i}=\sum _{x\in S_{1}}x^{i}}$para todos los enteros i desde 1 hasta k .

Esto tiene una solución si N es un múltiplo de 2k ^{+ 1 ,} dada por:

• S ₀ consta de los enteros n en S para los cuales t _n = 0 ,
• S ₁ consta de los enteros n en S para los cuales t _n = 1 .

Por ejemplo, para N = 8 y k = 2 ,

0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,

0² ⁺ 3² + ^5² + ^6² = ^1² + ^2² + ^4² + ^7² .^​

La condición de que N sea múltiplo de 2k ^{+ 1} no es estrictamente necesaria: existen otros casos para los que hay solución. Sin embargo, garantiza una propiedad más fuerte: si se cumple la condición, el conjunto de potencias k -ésimas de cualquier conjunto de N números en progresión aritmética se puede dividir en dos conjuntos con sumas iguales. Esto se deduce directamente del desarrollo del teorema del binomio aplicado al binomio que representa el n -ésimo elemento de una progresión aritmética.

Para generalizaciones de la secuencia de Thue-Morse y del problema de Prouhet-Tarry-Escott a particiones en más de dos partes, véase Bolker, Offner, Richman y Zara, "El problema de Prouhet-Tarry-Escott y las secuencias generalizadas de Thue-Morse". ^{[ 14 ]}

Utilizando gráficos de tortuga , se puede generar una curva si se programa un autómata con una secuencia. Utilizando la secuencia Thue-Morse, las reglas

• Si t ( n ) = 0 , avanza una unidad,
• Si t ( n ) = 1 , gira un ángulo de π /3 radianes (60°).

generar una curva que converge a la curva de Koch , una curva fractal de longitud infinita que contiene un área finita. Esto ilustra la naturaleza fractal de la secuencia de Thue-Morse. ^{[ 15 ]}

También es posible dibujar la curva con precisión utilizando las siguientes instrucciones: ^{[ 16 ]}

• Si t ( n ) = 0 , gire un ángulo de π radianes (180°),
• Si t ( n ) = 1 , avanza una unidad y luego gira un ángulo de π /3 radianes.

En su libro sobre el problema de la división justa , Steven Brams y Alan Taylor invocaron la secuencia de Thue-Morse, pero no la identificaron como tal. Al asignar un conjunto de artículos en disputa entre dos partes que coinciden en el valor relativo de los artículos, Brams y Taylor sugirieron un método que denominaron alternancia equilibrada , o tomar turnos, tomar turnos, tomar turnos... , como una forma de evitar el favoritismo inherente cuando una parte elige antes que la otra. Un ejemplo mostró cómo una pareja que se está divorciando podría llegar a un acuerdo justo en la distribución de artículos de propiedad conjunta. Las partes se turnarían para ser la primera en elegir en diferentes momentos del proceso de selección: Ann elige un artículo, luego Ben, luego Ben elige un artículo, luego Ann. ^{[ 17 ]}

Lionel Levine y Katherine E. Stange , en su análisis sobre cómo repartir equitativamente una comida compartida, como una cena etíope , propusieron la secuencia Thue-Morse como una forma de reducir la ventaja de moverse primero. Sugirieron que «sería interesante cuantificar la intuición de que el orden Thue-Morse tiende a producir un resultado justo». ^{[ 18 ]}

Robert Richman abordó este problema, pero tampoco identificó la secuencia de Thue-Morse como tal en el momento de la publicación. ^{[ 19 ]} Presentó las secuencias T _n como funciones escalonadas en el intervalo [0, 1] y describió su relación con las funciones de Walsh y Rademacher . Demostró que la n -ésima derivada puede expresarse en términos de T _n . Como consecuencia, la función escalonada que surge de T _n es ortogonal a polinomios de orden n − 1 . Una consecuencia de este resultado es que un recurso cuyo valor se expresa como una función continua monótonamente decreciente se asigna de manera más justa utilizando una secuencia que converge a Thue-Morse a medida que la función se vuelve más plana . Un ejemplo mostró cómo servir tazas de café de igual intensidad desde una jarra con un gradiente de concentración no lineal , lo que dio lugar a un artículo ingenioso en la prensa popular. ^{[ 20 ]}

Joshua Cooper y Aaron Dutle demostraron por qué el orden Thue-Morse proporciona un resultado justo para eventos discretos. ^{[ 21 ]} Consideraron la forma más justa de organizar un duelo de Galois , en el que cada uno de los tiradores tiene habilidades de tiro igualmente deficientes. Cooper y Dutle postularon que cada duelista exigiría una oportunidad de disparar tan pronto como la probabilidad a priori de que el otro ganara superara la suya. Demostraron que, a medida que la probabilidad de acierto de los duelistas se acerca a cero, la secuencia de disparos converge a la secuencia Thue-Morse. Al hacerlo, demostraron que el orden Thue-Morse produce un resultado justo no solo para secuencias T _n de longitud 2 ⁿ , sino para secuencias de cualquier longitud.

Por lo tanto, las matemáticas respaldan el uso de la secuencia Thue-Morse en lugar de turnos alternos cuando el objetivo es la equidad, pero los turnos anteriores difieren monótonamente de los turnos posteriores en alguna cualidad significativa, ya sea que esa cualidad varíe de forma continua ^{[ 19 ]} o discreta. ^{[ 21 ]}

Las competiciones deportivas constituyen una clase importante de problemas de secuenciación equitativa, ya que la alternancia estricta suele dar una ventaja injusta a un equipo. Ignacio Palacios-Huerta propuso cambiar el orden secuencial a Thue-Morse para mejorar la equidad ex post de diversas competiciones de torneos, como la secuencia de lanzamiento de una tanda de penaltis en fútbol. ^{[ 22 ]} Realizó una serie de experimentos de campo con jugadores profesionales y descubrió que el equipo que lanzaba primero ganaba el 60% de los partidos usando ABAB (o T ₁ ), el 54% usando ABBA (o T ₂ ) y el 51% usando Thue-Morse completo (o T _n ). Como resultado, ABBA está siendo sometido a extensas pruebas en la FIFA (Campeonatos Europeos y Mundiales) y en el fútbol profesional de la Federación Inglesa ( Copa EFL ). ^{[ 23 ]} También se ha descubierto que un patrón de saque ABBA mejora la equidad de los tie-breaks de tenis . ^{[ 24 ]} En remo competitivo , T ₂ es la única disposición de remeros de babor y estribor que elimina las fuerzas transversales (y por lo tanto el balanceo lateral) en una embarcación de carreras de cuatro miembros sin timonel, mientras que T ₃ es uno de los cuatro únicos aparejos que evitan el balanceo en una embarcación de ocho miembros. ^{[ 25 ]}

La equidad es especialmente importante en los drafts de jugadores . Muchas ligas deportivas profesionales intentan lograr la paridad competitiva dando selecciones tempranas en cada ronda a los equipos más débiles. Por el contrario, las ligas de fútbol fantasy no tienen un desequilibrio preexistente que corregir, por lo que a menudo usan un draft "serpiente" (hacia adelante, hacia atrás, etc.; o T ₁ ). ^{[ 26 ]} Ian Allan argumentó que una "inversión de tercera ronda" (hacia adelante, hacia atrás, hacia atrás, hacia adelante, etc.; o T ₂ ) sería aún más justa. ^{[ 27 ]} Richman sugirió que la forma más justa para que el "capitán A" y el "capitán B" elijan equipos para un partido informal de baloncesto refleja T ₃ : el capitán A tiene las primeras, cuartas, sextas y séptimas opciones, mientras que el capitán B tiene las segundas, terceras, quintas y octavas opciones. ^{[ 19 ]}

Los 2k bits iniciales de la secuencia Thue-Morse se asignan a 0 mediante una amplia clase de funciones hash polinómicas módulo una potencia de dos , lo que puede provocar colisiones de ^hash . ^{[ 28 ]}

Ciertas combinaciones lineales de series de Dirichlet cuyos coeficientes son términos de la sucesión de Thue-Morse dan lugar a identidades que involucran la función zeta de Riemann (Tóth, 2022 ^{[ 29 ]} ). Por ejemplo:

${\displaystyle {\begin{aligned}\sum _{n\geq 1}{\frac {5t_{n-1}+3t_{n}}{n^{2}}}&=4\zeta (2)={\frac {2\pi ^{2}}{3}},\\\sum _{n\geq 1}{\frac {9t_{n-1}+7t_{n}}{n^{3}}}&=8\zeta (3),\end{aligned}}}$

donde ( t _n ) _{n ≥0} es el n -ésimo término de la secuencia de Thue-Morse. De hecho, para todo s con parte real mayor que 1 , tenemos

${\displaystyle (2^{s}+1)\sum _{n\geq 1}{\frac {t_{n-1}}{n^{s}}}+(2^{s}-1)\sum _{n\geq 1}{\frac {t_{n}}{n^{s}}}=2^{s}\zeta (s).}$