Matt Parker on “the fairest sharing sequence”, the Thue-Morse sequence. The sequence is
0110 1001 1001 0110 1001 0110 0110 1001…
which is generated as follows:
- at the first step, start with 0
- invert the sequence, replacing all 0s with 1s and vice versa, and concatenate this to the original sequence
So this gives, in sequential steps: 0, 01, 0110, 01101001, …
It’s an interesting sequence, but why the title?
This is a follow-up to a video in which he proposes a puzzle: partition the numbers 0 through into two groups such that the sum of the 1st, 2nd, …, kth powers of each group are the same. For example, for we have and .
The solution, as you may have guessed, is that the numbers on one side of the equality should be the positions of 0s among the first elements of the Thue-Morse sequence, and the numbers on the other side should be the positions of the 1s, where indexing starts at 0. This fact is proven in Allouche and Shallit’s paper “The ubiquitous Prouhet-Thue-Morse sequence” – see section 5.1.
So why is this about fair sharing? Let’s consider the case again. We have for . That means, then, that we have
for any quadratic polynomial . So say that we’re divvying up some goods and I get the 0th, 3rd, 5th, and 6th most valuable item while you get the 1st, 2nd, 4th, and 7th. (We are computer scientists so we start counting from zero.) Then if we can write the value of the th item as a quadratic in , then we end up with the same value.
(How does this generalize to the case where is not polynomial? That seems relevant – for example what if or ? In a paper which independently rediscovered the Thue-Morse sequence, Robert Richman did some experiments which suggests that this still holds as long as isn’t “too far” from polynomial. This got written up in the Guardian as how to pour the perfect cup of coffee. Thue was Norwegian, and I hear Norwegians like coffee, so I think he’d approve.