5
$\begingroup$

Less of a question and more of an exercise, it has to do with something I found while doing some programming and being unable to find things.

Basically I wanted a formula for the perfect sharing algorithm as I call it,(ABBABAABBAABABBA...), I don't know the proper name of the sequence but it's used for truly fair sharing between 2 people.

I couldn't find a formula so I figured this out after a while.

  1. Start with AB
  2. Every A turns into an AB and every B turns into a BA.

AB -> ABBA -> ABBABAAB ...

This allowed me to get a computer to achieve the algorithm in many ways, but it also raised some questions.

Question 1: Can I repeat this forever and have it properly generate the algorithm?

The algorithm is normally created by taking AB, then inverting each 2-state 'digit' and sticking it on the end (ABBA). You then take this entire sequence and repeat the process (ABBABAAB). This is an infinite sequence.

Is what I'm doing going to generate the same sequence as the second method?

Question 2. 2 people decide they want to share a task, so they use this algorithm.

a) If they know how many turns have occurred but forget who's turn it is, can they generate an equation that tells them who's turn it is given the number of turns that have passed?

b) The 2 people forget where they are in the sequence, but they know who's turn it is right now. How many previous turns will they need to remember in order to find their place again under the worse possible scenario?

$\endgroup$
4
$\begingroup$

This sequence is the Thue-Morse sequence about which you can find quite a bit online; you can find a plethora of facts about it at the Online Encyclopedia of Integer Sequences as pointed out by Q the Platypus in the comments. (As a side note this is a really good website for finding sequences; you only need to type in the first 7 elements $0,1,1,0,1,0,0$ to it to get the Thue-Morse sequence). The Thue-Morse sequence has some interesting properties, including the fact that it describes a fair way to share as you noted.

The answer to your first question is yes, as Wolfram Mathworld confirms; specifically you can find here that:

[This sequence] is constructed by following a few simple steps:

(1) start with the two digit string, $01$

(2) replace every $0$ in the string by $01$, and replace every $1$ in the string by $10$.

(3) with the newly-created string from the previous step, go back to the beginning of step 2, and replace each $0$ and $1$ with the same values as before.

This (if you replace $0$ with $A$ and $1$ with $B$) is precisely your algorithm, which is an alternative way of generating the Thue-Morse sequence to the usual way which you mention (inverting the bits and adding the result on to the previous step - described here), so this substitution system does in fact generate the Thue-Morse sequence.

To answer part (a) of your second question, here you can find a mention of a way of calculating the $n^{th}$ term in the series:

To compute the nth element $t_{n}$, write the number n in binary. If the number of ones in this binary expansion is odd then $t_{n}=1$, if even then $t_{n}=0$.

This can be used to calculate who's turn it is if they know how many turns they have had, by simply taking the number $n$ of the turn they are up to, writing it in binary, and if there are an odd number of ones in the binary expansion then it is $B$'s turn and $A$'s turn if the number of ones is even. The same Mathworld page writes this in the simple form $t_n=s_{2}(n)\mod{2}$ where $s_{2}(n)$ is the binary digit sum.

As to part (b) of your second question, I do not know in general what information is required to be able to find your place in the series. However, simply knowing a past sequence of turns will not help if $A$ and $B$ do not know around how long they have been playing for, since if we let $S$ be the sequence of past turns that they do remember, and let $n$ be the actual position which they are at (which they want to find); then let $m=2^{\left\lceil\log_{2} n\right\rceil}$ be the next point at which the normal generating process will invert and add on the bits up to $m$.

However, the $m$ bits that follow bit $m$ are the inverse of the previous bits, and the $2m$ bits that follow bit $2m$ are the inverse of the first $2m$ bits. But this means that the sequence of bits from $3m$ to $4m$ are identical to the first $m$ bits, so the sequence $S$ occurs there also (since it occurs in the first $m$ bits). $S$ will also occur (as well as in many other places) between bits $15m$ and $16m$ and between bits $63m$ and $64m$ and so on. Thus $S$ actually occurs infinitely many times eventually in the Thue-Morse sequence, a property formally expressed here by noting that the Thue-Morse sequence is a uniformly recurrent word, i.e. for any past sequence $S$ they can remember, there is some length $l_S$ such that $S$ occurs in every block of length $l_S$ in the entire sequence (even though the Thue-Morse sequence is not periodic). The following image (where black dots are $1$s and white dots are $0$s) illustrates the recurrent nature of the sequence:

Thue-Morse

Thus if they know the last sequence of moves $S$, they would at the very least need to know around how many moves they have made already in order to be able to find where they are up to in the sequence, since the same sequence $S$ occurs infinitely many times throughout the game.

$\endgroup$
  • 1
    $\begingroup$ BTW the OEIS has this sequence at oeis.org/A010060 $\endgroup$ – Q the Platypus Oct 28 '16 at 5:45
  • $\begingroup$ Thanks for that, I often forget OEIS which has such a wealth of facts on so many sequences. I've included it in my answer. $\endgroup$ – Anon Oct 28 '16 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.