Thue–Morse sequence
To compute the nth element tn, write the number n in binary.
Spelling out the first few steps in detail: So In Python: Which can then be converted to a (reversed) string as follows: The sequence can also be defined by: where tj is the jth element if we start at j = 0.
[11] The sequence T2n is a palindrome for any n. Furthermore, let qn be a word obtained by counting the ones between consecutive zeros in T2n .
) forms a subspace of the nonnegative integers under nim-addition (bitwise exclusive or).
The Prouhet–Tarry–Escott problem can be defined as: given a positive integer N and a non-negative integer k, partition the set S = { 0, 1, ..., N-1 } into two disjoint subsets S0 and S1 that have equal sums of powers up to k, that is: This has a solution if N is a multiple of 2k+1, given by: For example, for N = 8 and k = 2, The condition requiring that N be a multiple of 2k+1 is not strictly necessary: there are some further cases for which a solution exists.
[14] Using turtle graphics, a curve can be generated if an automaton is programmed with a sequence.
[15] It is also possible to draw the curve precisely using the following instructions:[16] In their book on the problem of fair division, Steven Brams and Alan Taylor invoked the Thue–Morse sequence but did not identify it as such.
An example showed how a divorcing couple might reach a fair settlement in the distribution of jointly-owned items.
The parties would take turns to be the first chooser at different points in the selection process: Ann chooses one item, then Ben does, then Ben chooses one item, then Ann does.
[17] Lionel Levine and Katherine E. Stange, in their discussion of how to fairly apportion a shared meal such as an Ethiopian dinner, proposed the Thue–Morse sequence as a way to reduce the advantage of moving first.
They suggested that “it would be interesting to quantify the intuition that the Thue–Morse order tends to produce a fair outcome.”[18] Robert Richman addressed this problem, but he too did not identify the Thue–Morse sequence as such at the time of publication.
As a consequence, the step function arising from Tn is orthogonal to polynomials of order n − 1.
An example showed how to pour cups of coffee of equal strength from a carafe with a nonlinear concentration gradient, prompting a whimsical article in the popular press.
[20] Joshua Cooper and Aaron Dutle showed why the Thue–Morse order provides a fair outcome for discrete events.
[21] They considered the fairest way to stage a Galois duel, in which each of the shooters has equally poor shooting skills.
Cooper and Dutle postulated that each dueler would demand a chance to fire as soon as the other's a priori probability of winning exceeded their own.
[21] Sports competitions form an important class of equitable sequencing problems, because strict alternation often gives an unfair advantage to one team.
Ignacio Palacios-Huerta proposed changing the sequential order to Thue–Morse to improve the ex post fairness of various tournament competitions, such as the kicking sequence of a penalty shoot-out in soccer.
[22] He did a set of field experiments with pro players and found that the team kicking first won 60% of games using ABAB (or T1), 54% using ABBA (or T2), and 51% using full Thue–Morse (or Tn).
As a result, ABBA is undergoing extensive trials in FIFA (European and World Championships) and English Federation professional soccer (EFL Cup).
[23] An ABBA serving pattern has also been found to improve the fairness of tennis tie-breaks.
[24] In competitive rowing, T2 is the only arrangement of port- and starboard-rowing crew members that eliminates transverse forces (and hence sideways wiggle) on a four-membered coxless racing boat, while T3 is one of only four rigs to avoid wiggle on an eight-membered boat.
Many professional sports leagues attempt to achieve competitive parity by giving earlier selections in each round to weaker teams.
By contrast, fantasy football leagues have no pre-existing imbalance to correct, so they often use a “snake” draft (forward, backward, etc.
[28] Certain linear combinations of Dirichlet series whose coefficients are terms of the Thue–Morse sequence give rise to identities involving the Riemann Zeta function (Tóth, 2022 [29]).
, we have The Thue–Morse sequence was first studied by Eugène Prouhet [fr] in 1851,[30] who applied it to number theory.
However, Prouhet did not mention the sequence explicitly; this was left to Axel Thue in 1906, who used it to found the study of combinatorics on words.
The sequence was only brought to worldwide attention with the work of Marston Morse in 1921, when he applied it to differential geometry.
The sequence has been discovered independently many times, not always by professional research mathematicians; for example, Max Euwe, a chess grandmaster and mathematics teacher, discovered it in 1929 in an application to chess: by using its cube-free property (see above), he showed how to circumvent the threefold repetition rule aimed at preventing infinitely protracted games by declaring repetition of moves a draw.
At the time, consecutive identical board states were required to trigger the rule; the rule was later amended to the same board position reoccurring three times at any point, as the sequence shows that the consecutive criterion can be evaded forever.
