A287150 Fairest turn sequence for 3 players where the probability of a win for a player on his turn approaches 0.

0, 1, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 2, 0, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 0, 1, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 2, 0, 1, 1, 0, 2, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 2, 0, 1, 2, 0, 0, 2, 1

Offset: 0

Author

Daniel Hug, May 20 2017

Keywords

• nonn

Comments

0, 1, and 2 are three archers of equal skill, but which have infinitesimally low chances of hitting a target. Still, they try: taking turns until one of them hits: 0 goes first, if 0 misses then 1 will try (these are the first two terms). Subsequent terms are found by giving a turn to the player who has the lowest probability of winning so far.

Joshua Cooper and Aaron Dutle showed that for two players this is the Thue-Morse sequence (A010060).

The following observations are made and verified to be true for the first 5000 terms:

- Every 3 terms completes a new round with each player going once per round.

- Every other round is the same as the last but in reverse order.

- The 48th-101st terms form a block of 54 terms which are repeated from then on.

Links

• Joshua Cooper and Aaron Dutle, Greedy Galois Games, Amer. Math. Monthly, 120 (2013), 441-451, arXiv:1110.1137 [math.CO].
• Daniel Hug, Generate fairest turn sequence for n players (web app written in JavaScript)

Crossrefs

Cf. A010060.

Programs

Mathematica

n=3; a=Range[n]; pw=(1-p)^(Range[n]-1)*p;
Do[
next = First[Select[Range[n], And@@NonNegative/@Limit[Sign[pw-pw[[#]]], p->0]&, 1]];
AppendTo[a, next]; pw[[next]]+=p*(1-p)^k
, {k, n, 50}];
a-1
(* Andrey Zabolotskiy, Jun 05 2017 *)