Queen's Heads Puzzle 2

[pdurrant]

Follow-on to this puzzle (as suggested by LazyScot). If you haven't tried that puzzle yet, do so now.

Having gained your freedom, by luck or judgement, after a few months you succumbed to temptation, were caught, and have ended up in the gaol again.

The same chance to win your freedom is given to you (see the above link to the original puzzle), with one important difference. As a second-time offender, you may only choose 20 coins.

1. What strategy maximises your chance of gaining your freedom?
2. Using this strategy, how likely are you to gain your freedom?

As usual, answers in

Spoiler:

spoiler tags

please, so everyone can have a go.

I haven't thought about this puzzle myself yet, so I don't know what the correct answers are! Hopefully I'll have answers to post in a few days.

[obs20]

Spoiler:

I'd have to plan on a stay in prison. At best I'd have 20 to heads to 21 which are already on the table. If I took only those which are already heads I'd still be down by one.

[pdurrant]

Originally Posted by obs20

Spoiler:

I'd have to plan on a stay in prison. At best I'd have 20 to heads to 21 which are already on the table. If I took only those which are already heads I'd still be down by one.

The question is not "What are the odds of freedom following the strategy used in the previous puzzle answer?", as that is certainly not the best strategy in this instance.

[obs20]

Originally Posted by pdurrant

The question is not "What are the odds of freedom following the strategy used in the previous puzzle answer?", as that is certainly not the best strategy in this instance.

Spoiler:

While It's possible to pick off 11 of the existing 21 heads(without turning them over) on the table it doesn't seem probable; but it is the only strategy that I can think of at the moment.

[LCF]

Spoiler:

I wouldn't flip anything. The chances that I take 11 or more from the right ones are not so great, but flipping them all is 100% lose and I can't think of a strategy, where random flipping helps. There is probably one though.
I know, this is not a complete answer, but that's as far away as I came for 2 minutes with the pencil

[pdurrant]

Not an answer, just my thoughts so far

Spoiler:

It seems to me that the best strategy might just be to take simply choose 20 coins at random. It's a poor chance, but I don't see a way to improve it yet. Perhaps there isn't a way.

[jbjb]

Spoiler:

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.

/JB

[pdurrant]

Originally Posted by jbjb

Spoiler:

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.

/JB

Oh, excellent analysis. It seems sound to me, but I'll think about it for a bit. Increasing your chance of survival by over a thousand-fold is a very significant improvement!

[obs20]

Originally Posted by jbjb

Spoiler:

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.

/JB

I think you've got something:

Spoiler:

Say you do pick off a head on the first draw now he has 20 heads and you have 19 more picks. The situation has gone from bleak to grim.

[jbjb]

Originally Posted by obs20

I think you've got something:

Spoiler:

Say you do pick off a head on the first draw now he has 20 heads and you have 19 more picks. The situation has gone from bleak to grim.

Spoiler:

If you pick off a head in the first draw, and don't turn it over, you're now safe. He now has 20 heads and you've got 1. By picking and turning over the next 19, you can be sure to match his number.

/JB

[pdurrant]

Originally Posted by jbjb

Spoiler:

If you pick off a head in the first draw, and don't turn it over, you're now safe. He now has 20 heads and you've got 1. By picking and turning over the next 19, you can be sure to match his number.

/JB

Yes, I agree. Another way to look at it:

Spoiler:

You pick a coin and it's a head.

There are now 20 heads and 80 tails left. Pick 19 coins than have X heads in them. The gaoler is left with 20-X heads. You turn your coins over and now have 19-X heads. Add in the one head you first picked, and you have 20-X heads, matching the Gaoler and you go free.

Of course, if you picked a tail with that first coin, the gaoler has 21-X while you only have 19-X.

But yes, a definite 21/100 chance of freedom

So — we have a strategy that gives just over a 20% chance of freedom. Can anyone do any better?

[obs20]

Originally Posted by jbjb

Spoiler:

If you pick off a head in the first draw, and don't turn it over, you're now safe. He now has 20 heads and you've got 1. By picking and turning over the next 19, you can be sure to match his number.

/JB

Like I said a 20% chance of freedom is grim.

[pdurrant]

The next puzzle is up.

https://www.mobileread.com/forums/showthread.php?t=92200