Tossing and turning

I don't know the answer to this, but I am sure some of you can tell me.

You want to select at random one person from a group of 13. Your only randomising device is a single coin (a fair one). What is the minimum number of times you must toss the coin to ensure that each person has exactly one chance in 13 of being selected? What method should you employ?

David Burn London, England

) I don't know the answer to this, but I am sure some of you can tell ) me. ) ) You want to select at random one person from a group of 13. Your only ) randomising device is a single coin (a fair one). What is the minimum ) number of times you must toss the coin to ensure that each person has ) exactly one chance in 13 of being selected? What method should you ) employ?

infinity.

Now ask for a solution that minimizes the expected number of tosses, and you've got a real puzzle.

SaSW, Willem (at stack dot nl)

That's a bit of a blow. I can see dimly that if you had 16 people, you could do it with five tosses; if you applied that method, you would have a 3 in 16 chance of not picking anyone, so you would have to start again with another five tosses. But by the time you had tossed the coin, say, thirty times, your chance of not picking anyone would be (3/16)^6, or about 0.00028%. I suppose, though, that with probability 0 you could end up tossing the coin forever...

But if you had to choose between two alternatives, and wanted to weight your choice so that you picked the first one with probability (say) 4/7, you could do that easily enough. I just wondered whether a similar method might be applicable in this case...

Well, any help I can get would be appreciated.

David Burn London, England

Hi,

Each person takes a turn at guessing the next coin toss (done by any other member of group) Every one who guessed correctly stays in and repeats. If all go out, then those who were in that round stay in.

No idea about probabilities but I'd reckon everyone had a 1/13 chance of winning.

We do this for real...and we've never had to toss the coin an infinite number of times!

Kev

) Hi, ) ) Each person takes a turn at guessing the next coin toss (done by any other ) member of group) ) Every one who guessed correctly stays in and repeats. If all go out, then ) those who were in that round stay in. ) ) No idea about probabilities but I'd reckon everyone had a 1/13 chance of ) winning. ) ) We do this for real...and we've never had to toss the coin an infinite ) number of times!

Obviously not. But if I pick a finite number N, there's a nonzero chance that you end up doing more than N tosses.

ObPuzzle: What is the expected number of tosses using the method proposed by Kevin above ?

SaSW, Willem (at stack dot nl)

and Willem replied:

I get 2, but that doesn't match my intuition.

Bob H

Surely you mean four, not five.

You asked for 'the minimum number of times you must toss the coin to *ensure* that each person has exactly one chance in 13'. It's the word 'ensure' that makes you have to be allow for any number of tosses.

I'd like to see how you do that with a fair coin, without having to allow any number of tosses.

Willem posed:

and I replied:

OK, I've got a better answer now. How 'bout

182904281166869692 / 25804920098540835

Which is just a little over 7.

ObPuzzle: Can someone present a strategy that gets the expected flips lower than 4.8?

Bob H

and I challenged:

to which he replied:

ObPuzzle: Using a deck of 52 cards, and drawing as few cards as possible, how can we make a 4-in-7 choice?

Bob H

You can do it by drawing just four cards.

Discard three Spades. Shuffle pack thoroughly. Draw one card. There is a 4 in 7 chance that it's a Heart, a Club, or the Ace or King of Diamonds.

Damn.

[...]

Ah, a little honour salvaged. Thanks for the correction, Mark.