The Thue-Morse Sequence that shows over infinite tries the “fairest” way for two people to take turns when choosing things from a pool (i.e. drafting players for a kick-ball team). Matt Parker has a very entertaining YouTube video on the subject and John D. Cook has a clear example as well.
Between two players the Thue-Morse Sequence suggests “taking turns taking turns”, so the start of an infinite turn sequence (over the first 5 recursions) between players a and b would look like this: abbabaabbaababbabaababbaabbabaab. Each recursion splits the entire sequence into two parts. The first part shifts into second position and the second position moves into first position. The new sequence is then added to the end of the original. Each time the length of the sequence doubles so, for two players the length of the sequence will be 2r where r represents the number of recursions.
This is neat, but what if we wanted to generalize fair sharing across n players? Let’s first look at 3 players.
We’ll start the first round with abc. The first recursion is the original sequence. With two players the sequence was split into two pieces, so with three players the sequence is split into three pieces. We want our players to “take turns taking turns”, so each player is shifted backward one spot then that resulted is added to the original sequence (note that a player in the first spot shifts to the last spot). This gives us abc bca. This isn’t “fair” yet, since each player has yet to play in each spot, so let’s do it again, but this time we’ll shift the original sequence backwards two spots: (abc) (bca) (cab). Now each player has taken turns taking turns. Note that the first recursion is 3 characters long and the second is 9 characters long. To continue with this pattern, we slice the new sequence into three units and add shifted versions of the slices to the tail: (abc bca cab) (bca cab abc) (cab abc bca). This third recursion is 27 characters long or 3r.
The graphs below show the data points and average data points for the fourth recursion. Each first pick is worth 15 points, each second pick is worth 10 points, and each third pick is worth 5 points. It is clear that there is a fair distribution of points among each player and that over several turns the average fairness converges.
A proposed generalization for this sequence follows the following pattern: take a set of unique players {a,b,…,n}, identify all unique combinations by shifting each player 1 position. Including the original order this can be done n times, resulting in {a, b, …, n}, {b, c, …, n, a}, … {n, a, b,…, n -1}. Counting the original set as the first recursion, we can see that the second recursion will have n2 characters. Further each recursion can be sliced into n even parts, so the number of characters at any given recursion will be nr.
A C# method of this generalization is shown below:
static List ThueMorseMorseThue(string sequence, int numberOfRecursions)
{
if (!AllUniqueCharacters(sequence)) return null;
var playersLists = new List();
playersLists.Add(sequence);
var initialCount = sequence.Length;
int index = 0;
do
{
var thisSequence = playersLists[index];
var thisCount = thisSequence.Length;
var segmentLength = thisCount / initialCount;
var newSequence = "";
for (int n = 0; n < initialCount; ++n)
{
for (int i = n * segmentLength; i < thisCount + n * segmentLength; ++i)
{
int j = i % thisCount;
newSequence += thisSequence[j];
}
}
playersLists.Add(newSequence);
index++;
} while (playersLists.Count < numberOfRecursions);
return playersLists;
}
While writing this post I found myself caught up considering the possible implications of this sequence when taking turns for a game where not only is turn order valued, but the relative position to other players is considered: ie with players abc, b always follows a. With a consideration of relative positioning a and b would take turns following each other.