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

%I #30 Jun 05 2017 23:42:21

%S 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,

%T 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,

%U 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

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

%C 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.

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

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

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

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

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

%H Joshua Cooper and Aaron Dutle, <a href="https://doi.org/10.4169/amer.math.monthly.120.05.441">Greedy Galois Games</a>, Amer. Math. Monthly, 120 (2013), 441-451, <a href="https://arxiv.org/abs/1110.1137">arXiv:1110.1137 [math.CO]</a>.

%H Daniel Hug, <a href="http://output.jsbin.com/kilebod/">Generate fairest turn sequence for n players</a> (web app written in JavaScript)

%t n=3; a=Range[n]; pw=(1-p)^(Range[n]-1)*p;

%t Do[

%t next = First[Select[Range[n], And@@NonNegative/@Limit[Sign[pw-pw[[#]]], p->0]&, 1]];

%t AppendTo[a, next]; pw[[next]]+=p*(1-p)^k

%t , {k, n, 50}];

%t a-1

%t (* _Andrey Zabolotskiy_, Jun 05 2017 *)

%Y Cf. A010060.

%K nonn

%O 0,3

%A _Daniel Hug_, May 20 2017