|
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 2n dígitos, são sempre o complemento booleano da sequência obtida até então. [1] 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óricoA 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. [2] Sequenciamemento equitativoEm 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. [3] 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". [4] 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 2n, mas para sequências de qualquer comprimento. [5] 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. [6] 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. [7] Referências
|
