We will use the following strategy, parametrized by two constants X and Y. First, we will make the bet X times, guessing randomly each time. If all X coin flips were NOT the same, we stop. If they were, we keep going for Y more flips, each time guessing the same outcome that happened for the first X coin flips.
We lose $X in expectation for the first X flips, no matter what. Our expected winnings on the longer sequence of Y flips, in terms of the unknown probability p, are p^X . (4p − 3) .Y plus a similar term for (1-p). Integrated from 0 to 1, these give 2Y(4/(X+2) − 3/(X+1)), which is positive for X>2, so we just have to choose Y to make this bigger than X.
The total number of flips is X + Y, which is minimized (over the integers) when X = 3 and Y = 30, for a total of 33 coin flips. This just lets us break even, so we bump Y up to 31, for N=34 and an expected profit of ten cents.
Obviously this can be improved—we should be using our partial information about the coin at each step, instead of making just one decision 3 coin flips in.
Actually it seems like the optimal strategy is to cynl hagvy guvegrra pbva syvcf be hagvy gur engvb bs urnqf gb gnvyf frra fb sne vf orgjrra guerr gb bar naq bar gb guerr (which, apart from the value of N, seems intuitive enough). I checked this by brute force and computer, but maybe there is a cleaner solution.
Here’s a sketch of a (possibly bad) upper bound.
We will use the following strategy, parametrized by two constants X and Y. First, we will make the bet X times, guessing randomly each time. If all X coin flips were NOT the same, we stop. If they were, we keep going for Y more flips, each time guessing the same outcome that happened for the first X coin flips.
We lose $X in expectation for the first X flips, no matter what. Our expected winnings on the longer sequence of Y flips, in terms of the unknown probability p, are p^X . (4p − 3) .Y plus a similar term for (1-p). Integrated from 0 to 1, these give 2Y(4/(X+2) − 3/(X+1)), which is positive for X>2, so we just have to choose Y to make this bigger than X.
The total number of flips is X + Y, which is minimized (over the integers) when X = 3 and Y = 30, for a total of 33 coin flips. This just lets us break even, so we bump Y up to 31, for N=34 and an expected profit of ten cents.
Obviously this can be improved—we should be using our partial information about the coin at each step, instead of making just one decision 3 coin flips in.
Actually it seems like the optimal strategy is to cynl hagvy guvegrra pbva syvcf be hagvy gur engvb bs urnqf gb gnvyf frra fb sne vf orgjrra guerr gb bar naq bar gb guerr (which, apart from the value of N, seems intuitive enough). I checked this by brute force and computer, but maybe there is a cleaner solution.
That N is correct, or at least it’s what I calculated. Nice work.