puzzle problem - Page 2

[BigPaw]

Nitin1, is there a definitive answer to this problem? I'm not asking for the answer. :)

[scudzilla]

I'm guessing 7, provided that each horse run at constant speed for every race, and no timers are used.

[scudzilla]

Posted too soon. Now I'm guessing 6, by virtue of elimination.

[BigPaw]

Posted too soon. Now I'm guessing 6, by virtue of elimination.

Eliminating the horses is cheating. . . :D

[stultuske]

Eliminating the horses is cheating. . . :D

either that, or a brilliant scene from the Godfather.

[Sahil89]

Ok as we can race 3 horses at a time lets make 3 groups. After considering the all conditions that where can be the fastest 3 and assuming that we dont have timer :D lets do following

Let each group run and it will give us fastest horse in each group, Now make the race between these 3 winners. We got fastest horse. Now repeat this twice and we will get fastest 3.

So answer is 12. We will need 12 races to find out fastst 3.

[VernonDozier]

I think I've found a way to do in at most six races. I have not totally convinced myself that it cannot be done with fewer, but I think the logic below proves all possible cases can be done in at most 6 races.

Horses will be names H1 through H9. It is assumed that the transitive property applies (If Horse A beats Horse B and Horse B beats Horse C, then Horse A beats Horse C) and that winners are consistent (if a horse beats another horse in a race, it will ALWAYS beat that other horse). Third assumption is no ties in races. Without loss of generality(WLOG), I'll assume the following winners in the initial races

Race 1 -- H1 beats H2 beats H3
Race 2 -- H4 beats H5 beats H6
Race 3 -- H7 beats H8 beats H9

Race 4 will have the three middle horses race. WLOG, assume H2 beats H5 beats H8.

That means H5 and H8 are both eliminated (H1, H2, H4 beat H5, and H1, H2, H7 beat H8). Since H5 and H8 are not in the top 3 , H6 and H9 cannot be either since they are slower than H5 and H8, respectively. So the first three races, with the four horses eliminated, boil down to this...

Race 1 -- H1 beats H2 beats H3
Race 2 -- H4 unopposed
Race 3 -- H7 unopposed

We have five horses left. H1 is faster than at least two of them, so it is in the top three, so it gets a bye to the final round.

Race 5 will be H2 versus H4 versus H7.

Scenario 1: H2 comes in first place. In this case, H1 is fastest, H2 is second fastest, and H3, H4, H7 can race for third place in the sixth race.
Scenario 2: H2 comes in second place. In this case, H2 is at best the third fastest horse, so H3 and whichever horse H2 beat here(WLOG, let's assume it beat H7) are eliminated. H1, H2, and H4 will race in the sixth race.
Scenario 3: H2 comes in last place. H2 and H3 are therefore eliminated. The three fastest horses are H1, H4, H7. They will race in the sixth race.

As far as I can tell, that's six races to determine the fastest, second fastest, and third fastest horses, in order, and there are even a few cases where there will be redundancies and the final race will actually be between two, not three horses.

Anyone see an error and is anyone still thinking it can be done in 5?

[Sahil89]

Anyone see an error and is anyone still thinking it can be done in 5?

No there is no error. In previous post I said 12 and then I realised it can be done in only 6 races. I was going to answer the same but you already posted it.

[BigPaw]

I think I've found a way to do in at most six races. I have not totally convinced myself that it cannot be done with fewer, but I think the logic below proves all possible cases can be done in at most 6 races.

I think I've found a way to do in at most six races. I have not totally convinced myself that it cannot be done with fewer, but I think the logic below proves all possible cases can be done in at most 6 races.

Hey Vernon, that makes perfect sense, and your explanation is very clear and comprehensive. :)

[Reverend Jim]

I think he's got it!

[Agilemind]

A solution in six races:

As a start, divide the horses into three groups (A,B,C) and race them giving

1)A1 A2 A3
2)B1 B2 B3
3)C1 C2 C3

Then

4)A2 B2 C2,

Take the winner from that (lets say C2) and race against the other two first place winners (A1, B1)

5) C2 A1 B1
The winner and C1 are the two fastest horses, If C2 comes in last you know the three fastest horse (A1, B1, C1), if C2 comes in second you know the three fastest horses (C1, winner of this race, C2), however if C2 comes in first you have to race C3 against A1 and B1 to determine the third fastest horse.

6) C3 A1 B1 (only necessary in one case)

I still feel like there ought to be a way that doesn't require the 6th race in any situation but I haven't found one yet.

[Sahil89]

I still feel like there ought to be a way that doesn't require the 6th race in any situation but I haven't found one yet.

No 5 races will not give the fastest 3.

[Reverend Jim]

OK. Now I'm at this point

[Mike Askew]

So Jim, your at the point where you've turned into an ant :D

[Reverend Jim]

I admit the problem had me bugged (ugh) but I am definitely gnat giving up (sorry).

[chris.stout]

I can solve the riddle with zero races, and it turns out to be quite simple. Shoot six of the horses. The remaining three horses are the fastest three, assuming that the riddle doesn't include any form of equestrian zombieism outbreaks.