I think you can do much better than simply picking 20 without turning over. I calculate the probability of being freed with that strategy as 0.000136 i.e. a 0.0136% chance of survival. (calculation below).
On the other hand, while we know that if we turn over all 20 we are guaranteed to lose, we also know that:
- each coin chosen and turned over reduces the gaoler’s excess by one.
- each coin chosen and not turned over either reduces the excess by 2 or 0, if it is a head or not (respectively)
Thus a strategy of pick one without turning over and then pick 19 with turning over (in fact the order doesn’t matter) will result in success if the one not turned over was a head. I.e. if it was a head the deficit is now 19, so our remaining 19 draws can eliminate that using the turning over method.
The chance of picking a head on the first draw is 21/101, i.e. 20.79% - much better!
Looking at the other options (e.g. drawing 3 without turning and hoping for 2 or more heads in that set, and then following up with 17 turn-over draws), shows that 1 unturned and 19 turned gives the best chance.
So, the best strategy is to draw one without turning it over then draw and turn over 19, which gives a survival probability of 20.79%.
Analysis of drawing 20 coins at random and hoping for survival:
In general, the probability of drawing h heads from n draws in a particular way is:
((21!/(21-h)!)*(80!/(80+h-n)!))/(101!/(101-n)!)
And the number of ways of drawing h from n is:
n!/((n-h)!h!)
For example, the probability of drawing 3 in 5 draws in a particular way is:
(21*20*19)*(80*79)/(101*100*99*98*97)
The number of ways of drawing 3 from 5 is:
5!/3!2!
The overall probability of drawing h from n is the product of these two.
If we call this probability p(h,n), then we survive if we draw at least 11 (leaving him with 10).
I.e. The probability of survival is:
p(11,20)+p(12,20)+ ... + p(20,20)
Putting this in a spreadsheet shows that the probability of survival is 0.000136.