Sequência de Thue-Morse

Visualização gráfica da sequência de Thue-Morse.

Em matemática e suas aplicações, a sequência de Thue-Morse, ou sequência de Prouhet-Thue-Morse, é a sequência infinita binária (formada apenas por 0s e 1s), em que o primeiro dígito é igual a 0 e os demais, calculados em blocos de 2ⁿ dígitos, são sempre o complemento booleano da sequência obtida até então.

Sendo 1 o complemento binário de 0, os primeiros 2 dígitos da sequência de Thue-Morse são 01, os primeiros 4 dígitos são 0110, os primeiros 8 dígitos são 01101001, os primeiros 16 dígitos são 0110100110010110, e assim por diante.

Histórico

A sequência de Thue-Morse foi estudada pela primeira vez em 1851, pelo matemático francês Eugène Prouhet, que a aplicou à teoria dos números, mas sem mencioná-la explicitamente. A primeira referência explícita foi feita em 1906 pelo norueguês Axel Thue, que a usou para fundar o estudo combinatório de palavras. Mas a sequência só se tornou mundialmente conhecida em 1921, quando o trabalho do estadunidense Marston Morse aplicou-a à geometria diferencial.

Sequenciamemento equitativo

Em seu livro sobre o problema da divisão justa (1995), os matemáticos estadunidenses Steven Brams e Alan Taylor utilizaram o conceito da sequência Thue-Morse, mas não a identificaram como tal. Ao dividir uma série de itens entre duas partes que concordam com os valores relativos dos itens, Brams e Taylor sugeriram um método que eles chamaram de "alternância equilibrada" ("balanced alternation", ou "taking turns taking turns taking turns"), como uma forma de evitar a vantagem inerente da parte que escolhe primeiro. Um dos exemplos de Brams e Taylor mostrou como um casal divorciado, Ann e Ben, pode chegar a uma solução justa na distribuição de itens de propriedade conjunta. As partes se revezariam para que cada uma fosse a primeira a escolher em diferentes pontos do processo de seleção: primeiro Ann escolhe um item, em seguida Ben o faz, então Ben escolhe de novo e só então Ann volta a escolher.

Lionel Levine e Katherine Stange, em sua discussão de como repartir razoavelmente uma refeição compartilhada, propuseram a sequência de Thue-Morse como uma maneira de reduzir a vantagem de quem se serve primeiro. Eles sugeriram que "seria interessante quantificar a intuição de que a ordem Thue-Morse tende a produzir um resultado justo".

Joshua Cooper e Aaron Dutle mostraram por que a sequência Thue-Morse fornece um resultado justo para eventos discretos. Consideraram a maneira a mais justa de encenar um "duelo de Galois", em que ambos os duelistas são maus atiradores. Cooper e Dutle postularam que cada duelista deveria ter a oportunidade de disparar assim que a probabilidade de vitória a priori de seu oponente excedesse a sua própria. Eles provaram que, à medida que a hahbilidade de tiro dos duelistas se aproxima de zero, a sequência de disparos converge para a sequência de Thue-Morse. Ao fazê-lo, eles demonstraram que a ordem Thue-Morse produz um resultado justo não apenas para as sequências de comprimento 2ⁿ, mas para sequências de qualquer comprimento.

Competições esportivas formam uma classe importante de problemas de sequenciamento equitativo, porque a alternância estrita muitas vezes dá uma vantagem injusta a uma das equipes. Richman sugeriu que, no "basquetebol de rua", a maneira mais justa para a formação de duas equipes seria quando o "capitão A" tivesse a primeira, quarta, sexta e sétima escolhas, enquanto o "capitão B" tivesse a segunda, terceira, quinta e oitava escolhas. Ignacio Palacios-Huerta propôs mudar para Thue-Morse e com isso tornar mais justas várias séries de competições, como a sequência de chutes de uma disputa de pênaltis no futebol, a rotação de cor de peças em um jogo de xadrez e a ordem de serviço em um tie-break de tênis.