

A286676


Numerators of the Nash equilibrium of guesses for the number guessing game for n numbers.


1



1, 3, 9, 2, 20, 12, 23, 27, 31, 35, 187, 1461, 485, 105, 64, 69
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Consider two players: one player picks a number between 1N, and another player guesses numbers, receiving feedback "too high" or "too low". The number picker is trying to maximize the expected number of guesses, whereas the number guesser is trying to minimize the expected number of guesses. While a binary search would in expectation be the optimal strategy if the number was chosen randomly, it is not the case if the number is chosen adversarially.


LINKS

Table of n, a(n) for n=1..16.
Michal Forisek, Candy for each guess, p. 1519, IPSC 2011 booklet.
Michal Forisek, Candy for each guess


EXAMPLE

For n=3, the Nash equilibrium of guesses is 9/5. This is attained when the number picker chooses 1 with 2/5 probability, 2 with 1/5 probability, and 3 with 2/5 probability. The number guesser guesses the numbers 0,2,1 in order with 1/5 probability, 2,0,1 in order with 1/5 probability, and 1,0,2 (i.e. binary search) with 3/5 probability.


CROSSREFS

For denominators see A286677.
Sequence in context: A263559 A262343 A140985 * A246379 A303941 A176885
Adjacent sequences: A286673 A286674 A286675 * A286677 A286678 A286679


KEYWORD

nonn,frac,more


AUTHOR

Lewis Chen, May 12 2017


STATUS

approved



