Brain teasers from Work

[quem98]

1. There are 25 horses. Each horse runs at a unique constant speed. You would like to determine which are the three fastest horses. You are allowed to race 5 at a time. You cannot time the races; you can only observe relative order of finish. What is the minimum number of races necessary to identify the top 3 with certainty? How

Comments

[omgimsuchadork]

I have no idea on the first one, since making random groups of five and then taking the fastest of those five won't necessarily give you the three fastest. (Thanks, baseball. You've taught me well.)

But the second one sounds awesome, since you didn't say it cost anything to play the first round. :D I'd like to have a 50% chance of making train fare on a coin flip, please!

[bluegargantua]

I think you need a minimum of 14 races. 6 to find the fastest and 4 each to find the 2nd and 3rd place guys.

I dunno about the gambling example.

later
Tom

[pierceheart]

see my response below.

[rosefox]

Race horses 1-5. The fastest three get raced against another two. Repeat until all horses have raced; the top three of the final race are the top three horses, in order. Eleven races total. This assumes magic horses whose speed does not vary with local conditions or numbers of races run, of course.

The EV of the game is undefined, as you have no initial risk.

[oldsilenus]

Out of those posted so far, yours is the only answer to the first question which is correct.

I've come up with a different correct way to do it, and, oddly enough, it also takes eleven rounds

[spwebdesign]

I reached the same conclusion, but my third round differed from yours. No need to punish the top 3 horses by making them race more! Instead, in the third round, race horses 1-5, and then 6-9 plus the third place finisher of the 1-5 race. It's conceivable you may not need the 11th race, for if the third place finisher of race 9 finishes race 10 second or higher, you know which the top 3 horses are with certainty.

[shaggy_man]

In the coin flip game, there's a probability of 1/2 of winning nothing, 1/4 of $2, 1/8 of $4, 1/16 of $8, and so on.

The expected value of this is undefined. It doesn't converge. To maximize expected value, no amount of money would be too great to pay for a chance at this game.

I wouldn't play to maximize expected value. There are quantities of money greater than I'm willing to pay, and (very large) quantities that are of decreasing incremental value for me to win.

For that matter, there are sums that are beyond the ability of anybody who might propose the game to pay. Since it would only take about 30 flips to exceed the largest sum ever paid out by any lottery, I probably ought to be willing to pay about fifteen bucks.

[pseydtonne]

The value doesn't converge if played infinitely. However, you can't play infinitely -- the odds of sustaining heads with a real coin for that long mean the house would run out of money.

I would pay $1, if I didn't walk away. There'd have to be cleavage in my face or the promise that the buck went to charity. I'm not into gambling, only in being the house because the house always wins.

Why? Each event has a one in two chance that I get nothing. Since that first event is just as likely as the last, I can only see the limits.

[lightcastle]

Yes, this is what my now donut-inspired brain came up with. I was wrong below, the EV *is* infinite. But that is because it is based on infinite plays. I do not have infinite money (or time) so to play the game ONCE I would be willing to pay only as much as I was willing to lose/found amusing to risk.

[inthatoneway]

For question 2.
1/2 the time you win 0, 1/4 you win 2, 1/8 you win 4, 1/16 you win 8, etc etc. And the EV is the sum of the odds of making it to each step times the reward at that step, right? So EV = 0 + .5 + .5 + .5 ... or infinity. In theory you'd be a sucker NOT to play the game, at any price, as long as you could play it enough times. That said, how much would I pay to play just once? 5 bucks or so. I know the reward is potentially infinite, but I also "know" that the coin just won't come up heads more than a few times in a row.