OFFSET
0,1
COMMENTS
You play the following game: you start out with n coins that all have probability p to land heads. You toss all of them and you then need to set aside at least one of them, which will not be tossed again. Now you repeat the process with the remaining coins. This continues (for at most n rounds) until all coins have been set aside. Your goal is to maximize the total number of heads you end up with. As it turns out, there exists a constant p_0 ~ 0.5495021777642 such that for p_0 < p < 1 it is (for large enough n) optimal to set aside exactly one coin every round, unless all coins landed heads. On the other hand, in the case that all but one of the coins show heads, then for p smaller than or equal to p_0 it is optimal (regardless of the value of n) to set aside all n-1 heads and toss the remaining coin again.
LINKS
Wouter van Doorn, On maximizing the number of heads when you need to set aside at least one coin every round, arXiv:2406.14700 [math.CO], 2024.
EXAMPLE
0.54950217776420154314445654687638494652137186502900172367251682613752030651977...
PROG
(PARI) \p 125
q = 0.5; r = 0.5; m = 2;
{for(a = 1, 120,
for(k = 0, 10,
p = q + k/10^m;
L = 10*m;
v = vector(L);
v[1] = p;
v[2] = -p^3 + 3*p;
n = 2;
while(v[n] < v[1] + (n-1) && n < L, n=n+1;
v[n] = v[n-1] + 1 + p^n*(n-1-v[n-1]) + n*p^(n-1)*(1-p)*max(0, n-2+p-v[n-1]) - (1-p)^n);
if(n==L, r = p));
q = r;
m = m + 1)}
print(p);
CROSSREFS
KEYWORD
nonn,cons
AUTHOR
Wouter van Doorn, Sep 17 2024
STATUS
approved