The Fairest Sharing Sequence Ever
Why Stack Overflow recommends it
Stack Overflow users link it when answering how to pick fair teams or generate the Thue-Morse sequence, as an accessible explanation of why the pattern minimises first-turn advantage.
Recommended by 2 people across 2 different months, 2017 to 2020.
What it is
A Stand-up Maths video by Matt Parker explaining the Thue-Morse sequence, a binary sequence that gives the fairest turn order when two people share something. It also covers other surprising properties of the sequence and answers the puzzle from his previous video.
Cited in 1 Wikipedia article, including Thue–Morse sequence.
What people said
Recommends Ryan Leach · 2017-07 · Stack Overflow · on “Best algorithm to generate even strong teams”
As seen on [this video] the Thue-Morse Sequence [LINK] is probably your best bet for minimising first turn advantage. Wikipedia: In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. The first few steps of this procedure yield the strings 0 then 01, 0110, 01101001, 0110100110010110, and so on, which are prefixes of the Thue–Morse sequence. ... Intro Computer Science - Princeton [LINK] //Copyright © 2000–2016, Robert Sedgewick and Kevin Wayne. public class ThueMorse { public static void main(String[] args) { i
Recommends Bob Munds · 2020-12 · Stack Overflow · on “Picking fair teams - and the math to prove it”
The pattern from above. Team A: 1, 4, 5, 8, 9, 12, 13, 16 Team B: 2, 3, 6, 7, 10, 11, 14, 15 Snakes through the list using the pattern A-B-B-A; A-B-B-A; etc. This selection is pretty easy to code. Place all the ordered list of players into pairs. Reverse every odd # pair (assumes 1st pair is 0th group). However, there is a "better" way to make teams using the Thue-Morse algorithm. For a more in-depth description of of this algorithm see: [this video]
Cites Zoey Hewll · 2017-02 · Stack Overflow · on “List definition by repeated entry/iteration”
I want to define the Thue-Morse Sequence [LINK] (or the fair-sharing sequence [this video] ) in terms of an initial element, 0 , and the rule defining the next section of the list in terms of the entire list up until this point. i.e. fair 0 = [0] --fair 1 = [0,1] --fair 2 = [0,1,1,0] --fair 3 = [0,1,1,0,1,0,0,1] fair n = fair (n - 1) ++ map (1-) (fair (n - 1)) This works fine to generate the list up to any predefined length, but it seems ineffective to not just define the entire list at once, and use take if I need a predefined amount. My first attempt at defining the entire list was fair = 0 : map (1-) fair but of course, this populates the list as it goes, so it doesn't ever (need to) reenter t