Queen's Heads Puzzle

[pdurrant]

Originally Posted by happy_terd

I live on the edge.

No, there's no trickery in this puzzle concerning standing coins on their edge.

[jbjb]

Originally Posted by obs20

I agree with jbjb his explanation is much better than anything I could come up with.

Thanks!

As it happens, I prefer omk3's explanation to mine. Mathematically they both reduce to the same thing, but omk3's is much more concise and elegant than mine.

/JB

[LazyScot]

Originally Posted by pdurrant

No, there's no trickery in this puzzle concerning standing coins on their edge.

Bang goes my first idea.....

Spoiler:

When I pick 21 coins, I'll end up with x heads and 21 - x arms. Since there are 21 heads in total, the gaoler will have 21 - x heads.

I want to maximise the chance that I don't get executed, i.e. I want to have the same number, or more, heads than the gaoler. Mathematically I want to optimise the chances of "my heads" >= "gaoler's heads".

From a simple selection, this is the chances of "x" >= "21 - x".

Observation

The coins are identical, and so can be turned over with the result that a head becomes an arms and an arms becomes a head.

So I have a choice of either x heads or 21 - x heads, if I turn them all over.

Turning then changes my chances of freedom to the cases where

21 - x >= 21 - x

This is clearly always true, so I'll always go free.

Unfortunately for, and unbeknownst to, me my greatest enemy was also sitting blindfolded in the room. He reached over to the gaoler's coins, and turned them all over, meaning that the goaler now had 59 + x heads, and so I was executed regardless of what I did with my coins.

[pdurrant]

Originally Posted by LazyScot

Bang goes my first idea.....

Spoiler:

When I pick 21 coins, I'll end up with x heads and 21 - x arms. Since there are 21 heads in total, the gaoler will have 21 - x heads.

I want to maximise the chance that I don't get executed, i.e. I want to have the same number, or more, heads than the gaoler. Mathematically I want to optimise the chances of "my heads" >= "gaoler's heads".

From a simple selection, this is the chances of "x" >= "21 - x".

Observation

The coins are identical, and so can be turned over with the result that a head becomes an arms and an arms becomes a head.

So I have a choice of either x heads or 21 - x heads, if I turn them all over.

Turning then changes my chances of freedom to the cases where

21 - x >= 21 - x

This is clearly always true, so I'll always go free.

Unfortunately for, and unbeknownst to, me my greatest enemy was also sitting blindfolded in the room. He reached over to the gaoler's coins, and turned them all over, meaning that the goaler now had 59 + x heads, and so I was executed regardless of what I did with my coins.

Spot on. Well done. I'm not sure I like your extension to the game.

[pdurrant]

Originally Posted by pdurrant

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

Here are the answers to the questions:

Spoiler:

1. Pick 21 coins at random, but as you place them flat on the table in front of you, be sure to turn them over.
2. You are certain to be freed.

But I suspect that those who are still puzzled by the puzzle won't be happy with just bare answers, and would like to know why.

Spoiler:

In the 21 coins you pick at random (before you turn them over), there will be X heads, where X is any number from 0 to 21 inclusive.
In the 80 coins the Gaoler has, he will have the remaining (21-X) heads.

After you turn your 21 coins over, you will also have (21-X) heads.

So no matter how many heads are in the 21 coins that you pick, after you turn them all over you will have exactly the same number of heads in your 21 coins as the gaoler has in his 80 coins. You go free.

[LazyScot]

Originally Posted by pdurrant

Here are the answers to the questions:

Spoiler:

1. Pick 21 coins at random, but as you place them flat on the table in front of you, be sure to turn them over.
2. You are certain to be freed.

But I suspect that those who are still puzzled by the puzzle won't be happy with just bare answers, and would like to know why.

Spoiler:

In the 21 coins you pick at random (before you turn them over), there will be X heads, where X is any number from 0 to 21 inclusive.
In the 80 coins the Gaoler has, he will have the remaining (21-X) heads.

After you turn your 21 coins over, you will also have (21-X) heads.

So no matter how many heads are in the 21 coins that you pick, after you turn them all over you will have exactly the same number of heads in your 21 coins as the gaoler has in his 80 coins. You go free.

Spoiler:

My understanding is that this works because the number of coins you draw exactly matches the number of coins that were originally laid out with heads.

How would the answers be altered if the number of coins you drew where not the same as the number of heads? Could you still influence the probability of your being freed?

[jbjb]

Originally Posted by LazyScot

Spoiler:

My understanding is that this works because the number of coins you draw exactly matches the number of coins that were originally laid out with heads.

How would the answers be altered if the number of coins you drew where not the same as the number of heads? Could you still influence the probability of your being freed?

Spoiler:

Say Y(n) is the excess of heads that the jailer has over you after n draws. So, the jailer starts with an excess of Y(0) (which is 21 in the original puzzle). The strategy of drawing a coin and turning it over means that the excess reduces by 1 each time (either it was a head, so you've reduced the jailer's count, or it was a tail, so you've turned it over and increased your count).

i.e., (for all n >= 0):

Y(n+1) =Y(n) - 1
or:
Y(n) = Y(0)-n

Let's say that N is the number of draws you make, then the jailer's excess at the end is Y(N), and

if Y(N) > 0: you die
if Y(N) <= 0: you are freed

This means that if (as in the original puzzle) the number drawn is the same as the initial count (i.e. N = Y(0)), then the two counts end up equal and you are freed. If the number drawn is more than the initial count (i.e. N > Y(0)) then you will end up with more than the jailer and be freed. If the number drawn is less than the the initial count of heads (i.e N < Y(0)), then you die.

/JB

[pdurrant]

Originally Posted by LazyScot

Spoiler:

My understanding is that this works because the number of coins you draw exactly matches the number of coins that were originally laid out with heads.

How would the answers be altered if the number of coins you drew where not the same as the number of heads? Could you still influence the probability of your being freed?

Spoiler:

jbjb's analysis is right as far as it goes (although perhaps overly mathematical).

And he is right - following the strategy, if you draw more coins than the number of heads originally showing, you win. If you draw fewer, you lose.

So if (say) you could only draw 20 coins, it is the wrong strategy to take.

I don't know off-hand what the correct strategy would be. It sounds like a good follow-on puzzle.

[pdurrant]

Originally Posted by LazyScot

How would the answers be altered if the number of coins you drew where not the same as the number of heads?

What a good question! That seems interesting enough to have a thread of its own. Please have a go at Queen's Heads Puzzle 2

[jbjb]

Originally Posted by pdurrant

Spoiler:

jbjb's analysis is right as far as it goes (although perhaps overly mathematical).

Spoiler:

Guilty as charged. Many would assert that "overly mathematical" applies just as much to me as my analysis.

/JB