Completely non-Poker related

[mmbt0ne]

Not really probability either, but you guys seem to be the best at this stuff so I figured I'd throw it out there. We're doing counting right now in Linear+Discrete and they gave us this problem(no it's not hw). I thought it was interesting and figured maybe I could give you something to do:
You have 25 horses, and want to figure out which 3 are the fastest, but have no stopwatch. You have one racetrack to do this with, which can race 5 horses at a time. What is the minimum number of races to find the fastest 3 horses?<font color="white">I got 9</font>

[TomCollins]

First do 5 races of 5 horses. We can get rid of 2 horses from each race and send them to the glue factory. For Race A, we have A.1, A.2, A.3, and so forth.

Whenever we determine that 3 horses are faster than any given horse, we can throw it out.

Now Race A.1, B.1, ... , E.1 in a race. For the 4th and 5th place finishers, get rid of the entire group. Since each horse in group E and D are slower than A.1,B.1,and C.1, they are not the three fastest.

For the 3rd place finisher, get rid of the rest of the group, but keep that horse. Since it is faster than any horse in its group, but has two horses faster than it, none of the other horses can make the top 3.

For the 2nd place finisher, get rid of the 3rd place horse in that group. There are only 2 horses faster than it, so it may be the 3rd fastest horse. The rest become dog food.

For group A, we still have the top 3 horses, since we don't know much else about them.

So we now have 3 Horses from Group A, 2 from Group B, and 1 from Group C.

We know A.1 is the fasest horse of all. So race the remaning 5 horses, and the fastest two are the 2nd and 3rd fastest horses.

This takes 7 races.

I don't think it can be done faster, since 6 is the only reasonable solution less, and I don't think it provides enough ordering. I'll try to prove it cannot be 6 next.

[mmbt0ne]

Jeez, that blows my 9 right outta the water. I figured out the racing 3rd place finishers to eliminate all but one, but I didn't even think to race the winners to eliminate entire groups.

[fnord_too]

Assuming that there is no variablility (i.e. if x is faster than y, x will always beat y regardless of how many horses are in the race or any other factor).

I know you can do it in trivially in six:

1 heat of 5, take fastest three, add two untested, rinse and repeat. (six races total)

Here's a way to do it in 5:

Run 3 races with 5 each (so each of the 15 is in exactly one of these races).

Lets lable 1-2-3 in each of these A1, A2, A3, B1, B2, B3, C1, C2, C3 (A, B, and C labling the initial heats).

If we run A2, B2, C2, A3, B3, then if C2 does not win outright, you can take the top two and run them with A1, B1, C1 to find the fastest 3. If C2 wins, you take C1, C2, C3 with A1 and B1 to see who the fastest 3 are.

That get you to 5 races.

There may be a way to get it to 4, but that is the lowest you can go. (With three races, you cannot get enough information. Every horse has to race at least once, which means you have three races of 5, but then there is no way of knowing which of the top three from each heat is a top three overall.)

[Officer Farva]

Reread the post. Theres 25 horses, ford. Im writing a proof that shows 7 races is the minimum possible. Nice work though.

[fnord_too]

[ QUOTE ]
Reread the post. Theres 25 horses, ford. Im writing a proof that shows 7 races is the minimum possible. Nice work though.

[/ QUOTE ]

DOH! well, if it WERE 15, I like my answer. I'd have to think about 25. Intuitively, I don't think you can get less than 7.

Oh, I wrote mine up about an hour before I could post it (damn work expecting me to ... well .... work) or I probably would have been clued in by the responses above me.

[Officer Farva]

7 is the best. A proof using Graph Theory is deicidably easier, but heres the plain english reasoning. Proof by contradiction:

Assume there is a way find the three fastest in 6 (or less) races. We know that each horse must be raced once, otherwise it cannot be ordered versus the others. Since we have 6 races, 30 racing slots are available. Since there are 25 horses, there are only 5 slots available for running any particular horse a 2nd time. We can infer that at least one horse from a particular race must also have raced in an other race, otherwise the five horses cannot be compared against the others, and the race is meaningless. We can also show that there can be no more than one multiply raced horse in a particular race, otherwise 2 racing slots will have been used, leaving only three to the other four races, implying one of the races did not have a multiply raced horse , which we have already shown cannot occur. Thus, there must be exactly one multiply raced horse per race. There must then be an assignable ordering to our races (1-6)such that a horse in race 1 raced in race 2, a horse in 2 raced in 3, and so on, since every race has a horse that raced in an other race (this is not directly observable, but is trivial to prove). We proceed to show that regardless of which horse is raced again in the following race for each in the series of 6, there is no strategy that will lead to obtaining the three fastest. To do this, we observe the pathological case for any strategy (notice this is rigorous, since we are looking for a stategy that guarantees the outcome, regardless of the case). So we watch race one and observe the outcome. Our strategy consists of picking a horse from a given race to run in the next such that we are able to determine the best three by the end of the 6th race. If we use any horse but the first place horse from race 1 in race 2, and this horse places fourth or worse in the next race, we will have to race the winner of race one at least one more time in order to determine its relation to the other horses since it may, at this point, be the fastest of the two races or at worst the 4th fastest. But this contradicts with the fact that there can only be one multiply raced horse per race, and there was already a multiply raced horse in race one (the one we initially picked). Thus our strategy must be to use the winner of each race to run in the next one to avoid this situation. But if, in the pathological case, the race one winner goes on to win all 6 races, we have no way of determining the other two fastest, since they could have placed 2nd or 3rd in any of the 6 races. We conlcude that there is no strategy for finding the three fastest in our 6 race scenario, contradicting our premise. QED Thus 7 is the best we can do.

Mike

Please respond with questions or if you feel I am wrong.

[pzhon]

[ QUOTE ]

Assume there is a way find the three fastest in 6 (or less) races. We know that each horse must be raced once, otherwise it cannot be ordered versus the others. Since we have 6 races, 30 racing slots are available. Since there are 25 horses, there are only 5 slots available for running any particular horse a 2nd time. We can infer that at least one horse from a particular race must also have raced in an other race, otherwise the five horses cannot be compared against the others, and the race is meaningless.

[/ QUOTE ]
Ok.

[ QUOTE ]
We can also show that there can be no more than one multiply raced horse in a particular race, otherwise 2 racing slots will have been used, leaving only three to the other four races, implying one of the races did not have a multiply raced horse , which we have already shown cannot occur.

[/ QUOTE ]
This step is flawed. If 5 horses race twice, that means there are 10 slots filled by horses that race multiple times. 10 such slots can be divided among the 6 races so that some races get more than one slot. Indeed, if 5 horses raced twice, it is unavoidable.

You assumed that there are 6 races, but you seem to be talking about 5 races. Did you mean to include some argument that no horse could race for the first time in the last race? That would fix the problem. If you establish this, the rest is easy.

[ QUOTE ]
Thus, there must be exactly one multiply raced horse per race. There must then be an assignable ordering to our races (1-6)such that a horse in race 1 raced in race 2, a horse in 2 raced in 3, and so on, since every race has a horse that raced in an other race (this is not directly observable, but is trivial to prove).

[/ QUOTE ]
A priori, one horse from each of the first 5 races could race in the last race, which violates your assertion.

Shuffling the races (assigning a new ordering) does not make sense because you can use the results of earlier races to determine which horses are in the next race.

[slavic]

Considering what I know of horses and their aptitudes. (I grew up on a quarter horse ranch were we raised cutters and racers) This is a near impossible thing to figure.

You might as well be racing obstinant 1000 pound two year olds, oh wait you are.

[Leo99]

Nice job.

[mmbt0ne]

I'm not actually trying to race my horses. It's just a theoretical problem man. We get to assume that no horse changes speed, gets tired, etc.
Side note: Where did you raise horses? I have some family from Kentucky, but they never got into the horse biz, too busy farming tobacco. My neighbor's son does though. He's President of the Florida Bar and has a track and stable down there where he breeds and trains.