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

[pierceheart]

Seven races. Divvy the horses into alphabetized heats: a1-a5 ... -e5.
First five races (first round):
A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
C1 C2 C3 C4 C5
D1 D2 D3 D4 D5
E1 E2 E3 E4 E5

eliminate anyone who came in 4th or fifth.
race the first place winners:
A1 B1 C1 D1 E1
eliminate 4th and 5th, AND anyone who ran slower than them, AND anyone who ran slower than C1, and whomever came in third against B1, AND the fastest horse (everyone else has lost once)
A2 A3 B1 B2 C1

[oldsilenus]

But you can't time the horse races, so you can't compare speeds across rounds.

[pierceheart]

you don't need to: the eliminated ones have already run slower than ones you are keeping.

Maybe that's not very clear: C1 came in third in the winners' runoff, which determined A1 to be the fastest.

C1 has already beaten the rest of the C's, so they need to be eliminated.

B1, in second place in the winners' runoff, so there's only one place after him, so drop the one two spots behind him (B3).

D1 ran fourth in the winners' runoff, so, if they couldn't beat him, they couldn't beat anyone who DID beat him.

Same for E1.

[oldsilenus]

Oh, huh: I think I misunderstood the "them" in "eliminate 4th and 5th, AND anyone who ran slower than them" the first time I read this through.

Also, as I'd been looking at this page for a few minutes, and as I commented at 4:01pm (theoretically), and you edited your comment at 4:00pm (theoretically), it's possible that I was responding to an unfinished version of your comment.

[inthatoneway]

For the first problem.
Break the horses into 5 groups of five and race them. Eliminate the horses that come in 4th and 5th. So 5 races eliminates 10 horses. Now take all the horses that came in third and race those. The bottom 4 will have been beaten by 4 different horses at that point and so can be eliminated. Then race the horses that came in 2nd in the first five races, and by similar logic you can eliminate the bottom 3. Then race the 1st place winners and eliminate the bottom 2. You've now run 8 races and are down to 6 horses. The horse that came in 1st of the 1st place winners is the only one that has never failed to win at this point, so he's the fastest; no need to race him any more. Race the remaining 5. The bottom three are slower than the two winners, and slower than the one you know is fastest, so they're out, and you're down to 3 horses. So you can do it in 9 races.

[pierceheart]

you can do it in 7.

[jaspamaster]

Hmmm none of these involve choices!!!

[inthatoneway]

Bah! Humans are impossible to predict, choices are tricky; fie on them! Give me nice solid math any day. :)

[jaspamaster]

Chukle mmmmmmmm Maybe ;-)

[quem98]

Well, you can have choices in your game. This is mine.

So there.

[lightcastle]

I had tried to answer earlier. I had a not-well-thought out version that sort of worked like one of the real solutions, but wasn't quite as efficient

[lightcastle]

See above. I don't have infinite money, so what I am willing to pay is not related to infinite EV.