Sunday, April 24, 2005

A math puzzle for the weekend.



The last couple of puzzles have clearly been too easy, so let's crank it up a notch. You and a friend agree to play the following game. You have a fair coin, and each of you is going to pick a sequence of length three of some combination of heads and tails. Once each of you has picked your sequence, you'll start flipping the coin and whoever's (consecutive) sequence comes up first wins.

In a gesture of generosity, you allow your buddy to choose and announce his sequence first. Once he's done that, you'll pick yours, at which point the flipping starts.

This leads to two questions:
  • (Easy) Once your friend has selected his sequence, what strategy should you use to pick yours?
  • (Not so easy) Based on the fact that you get to choose second and you choose wisely, what's the average probability that you can win this game?

13 comments:

M@ said...

I think I have the answer. Although I won't post my solution yet in accordance with your request, I'll say that the probability of winning is slightly less than 50% with my strategy -- or 50% assuming that the other person does not win on the first three flips of the coin.

Which is far better than a random choice of three flips -- 1/2 probability of winning rather than 1/8. I can't see how your chances in any coin flip game can be better than 50%, in fact.

aweb said...

I have a strategy that gets you much better than 1/2, but I'm not saying yet.

CC, have you studied game theory? The last two puzzles seem like those kind of puzzles.

CC said...

Game theory, number theory, combinatorics. I've dabbled in all of them. Mostly, I'm a fan of math puzzles that are easy to explain but have non-intuitive solutions.

M@ said...

So when do we get to propose our solutions? I guess I'm probably wrong but I'm itching to know what's right...

CC said...

Let's say, lunch time Monday (which means I'd better get cracking and figure out the answer -- it's been a while).

The first part, of course, is pretty easy. It's the second part that's tricky.

And what with Jonathan bragging about being off at his computational science conference, I'll be expecting some real cleverness from him.

aweb said...

Pick the first two values of your opponents' sequence for your last two. For your first one, I don't think it matters. In this way, for a lot of the sequences of heads and tails that lead to your opponent winning.

I have this figured at 2/3 chance of winning.

I could be wrong though...can anyone do better?

aweb said...

whoops, writing it as you posted..feel free to remove my answer if want. Or if it's wrong, mock away..

CC said...

Nah, might as well go with it. Like I said, the first part's easy. I want to see the second part.

aweb said...

my chances of winning after each flip (starting with the third one) : 1/8+ 2/16 +4/32 +6/64 +9/128 +12/256 +16/512 +20/1024 +25/2048 +30/4096+....etc the denominator doubles each time, the numerator adds 1,1,2,3,3,4,4,5,5, and so on.
This breaks into breaks into two infinite sums, which can be evaluated using some calculus. They sum to 2/3.

How did I get the numbers above? Tree diagram and pattern recognition. Brute force method, basically. Not the most mathematically rigorous method, I admit...I'm all for seeing a better proof of the solution.

Declan said...

aweb - I took the same route and came up with the same solution. But I'm thinking, if your opponent had a sequence that ended with the same letter twice (say THH or TTT), wouldn't you want to choose as your first letter the one which doesn't make a HHH or TTT sequence (i.e. THH or HTT)? Since if you have HHH or TTT as your sequence you're cutting off your own options like you are doing to your opponents by taking their first two letters as your last two.

Could be wrong, that's just what I vaguely remember from drawing the tree yesterday...

Harlequin said...

As said, you use the first two of his as last two of yours; pick the first one of yours as you like, 'cept you might need to pick the one he didn't, in the case of an HHH/TTT pick.

I see the odds of a win with this strategy as 58.33%. Put it this way. Right off the bat, your opponent has a one in eight chance of winning on the first three tosses. Accept that risk and move on. The other seven-eighths of the time, the fact that there's a "first throw" is irrelevant and we can talk about general sequences where there's a coin toss before it as well as one after it.

Of those general sequences, we throw away all subsequences which don't center on his first two/your last two calls. Nobody wins, the subsequence is irrelvant (except to the odds of how long such a game would take to finish). Call that sequence XY; let's say you win on HXY, he wins on XYH. Doesn't matter what XY are.

There are four possible runs of the form _XY_. In one of them, TXYT here, nobody wins. In two of them, HXYT and HXYH, you win. In one of them, TXYH, your opponent wins. You win 2/3ds of the time.

So you have 7/8ths odds of making it past the risk of an XYH opening, to where those general sequences (of the form _XY_) can happen. Then 2/3ds of those are in your favour. 2/3 * 7/8 = 58.3% odds of a win.

Nice puzzle, though.

CC said...

I'll have to dig through my puzzle archive to find my solution. It may or may not be any simpler than this one, though.

The key lesson for games of chance, though, is to be very leery any time someone charitably says, "And, hey, I'll even let you pick first."

Chances are, they're not doing you any favours.

Declan said...

good point harlequin - I was forgetting about the start conditions.

CC - "be very leery any time someone charitably says, "And, hey, I'll even let you pick first."

Brings back memories of the old game where you and your opponent take turns choosing either the number one or two (with each successive pick adding to the running total) with the person who makes the total = 21 being the winner.

(it was painful watching the cnotestants butcher that game on Survivor by the way)