1.33
Answer: Seven races.
First 5 races: Divide 25 horses into 5 groups and that gives you 5 winners.
Sixth race: Now race 5 of them that will give you winner and which two are the bottom-most group. Reject the bottom two group
Now consider the first 3 groups, G1, G2 and G3
G3 Group (the horse that came 3rd in 6th race) - can only bid for 3rd place so we take him for next level i.e. G31
G2 Group (the horse that came 2nd in 6th race) - can bid for 2& 3rd spots we take top two from this group for next level i.e G21, G22
G1 Group (the horse that came 1st in 6th race) - can bid for 1,2,3rd place, but we have already got our first; so we need only to take 2 from this group for next level i.e. G11, G12, G13
Seventh Race:: G12, G13, G21, G22, G31 Race them to get 2nd and 3rd winner G11 is already won as 1st winner.
--Max 07:06, 16 June 2010 (EDT)
I get the same answer but want to clarify the notation and solution approach.
Answer: Seven races.
First five races: First 5 exclusive groups of 5 horses.
Sixth race: Between all the first-place winners in first five races (leaders). Letter the groups by the order the leaders in the sixth race (e.g. a1 is the fastest of the leaders while e1 is the slowest leader).
Let's list the constraints implied by these results (where >> means faster).
X(n) >> X(n+1), a1 >> b1, b1 >> c1, c1 >> d1, d1 >> e1
These constraints allow us to sketch a tree of continuations for the possible ordering:
a1 | \ a2 b1--c1--d1--e1 | | | | | a3 b2 c2 d2 e2
Now, we need to devise the next race to give us an answer. Reasoning by constraints and seeking three fastest we can knock out anyone lower than c1 since that would imply that c2 >> b1 >> c1 which is a contradiction.
That leaves us with one more race between a2, a3, b1, b2, c1 to determine the second and third fastest horses.
Argument:
In the above solution, we are assuming that the winners of each of the groups are better than all the remaining horses in every group. But that might not be true. For example, let us denote the speed (20) of a horse A as A(20). Now let us consider a collection of 9 horses:
Group I A(10) B(20) C(30) winner: C(30)
Group II D(40) E(50) F(60) winner: F(60)
Group III G(70) H(80) I(90) winner: I(90)
We clearly see that if we continue with ONLY the winner of the groups, we get an incorrect answer. We need to pick the top 3 of each group to get the correct answer.
--Luckylovelace (talk) 17:52, 19 September 2014 (UTC)
Possible solution to proposed argument: I was thinking the same thing as the person who proposed the argument above. However, I think I've reconciled my differences with the first 2 solutions.
I'll explain.
Initially, my solution was to setup the contest (since it is not specified how this can be done) by racing all 5 groups of horses and then only racing the fastest 5 (not necessarily the winner of each group). If the problem is setup in this way then it would only require 6 races. Even better yet you could just race all 5 groups and take the fastest 3 horses, which would only take 5 races. This was my lazyman, practical approach.
After this, I began to think about how you would go about creating a solution if no times were given, meaning you wouldn't know the ordering of the groups. You only know which horse is faster than the other horses in its group. And of course, we'll have to still have at least 5 races so that every horse gets their chance. This will result in 5 groups. So let me clarify my setup of the problem:
The 1st place horse must be faster than 24 other horses The 2nd place horse must be faster than 23 other horses (all horses except #1) The 3rd place horse must be faster than 22 other horses (all horses except #2 and #1)
After the first race we know this:
Group A (X < Y means x is faster than y):
A1 < A2 < A3 < A4 < A5 (So we know A1 is faster than 4 other horses)
...
Group E:
E1 < E2 < E3 < E4 < E5 (So we know E1 is faster than 4 other horses)
So we now have A1, B1, C1, D1, E1 as winners of their group, which are all faster than at least 4 other horses.
So now in the 6th race, we determine the first place horse because, we know that they must be faster than all 24 other horses since, they are faster than the fastest horses of all the other groups. To clarify:
(Assuming they placed in lexical order) A1 < B1 < C1 < D1 < E1 => A1 < (B1...B5...C1...C5...D1...D5...E1...E5)
However, we cannot determine 2nd or 3rd place, because other horses in the first group may be faster than horses in 2nd or 3rd place, and other horses in the 2nd group, may be faster than horses in 3rd place.
But, what we do know, is that the horses in 4th and 5th place are slower than all the remaining horses ( B1 < C1 < D1..E5). So we can remove them from the next race.
This opens up 3 new slots (since 1st place has already been determined). Now, as stated previously, we know that 2nd and 3rd could both come from the first group, therefore we must take the next two fastest horses from group 1 (A2, A3). We then know that 3rd place could also come from another horse in the 2nd group, therefore we must take 1 horse from that group (B2).
This leaves us with the last and final race between A2, A3, B1, B2, C1.
Q: Why not take all 3 slots from the first group?
This would not make sense since there are only 2 places (2nd and 3rd) left to give. If we did do this, we could potentially be left with this ordering: A1 < B1 < C1 < A2 < A3, which never gives B2 a chance to claim the third place spot should he be faster than C1.
Another way to look at it is as two separate races - one for 2nd, and another for 3rd. In the first race you have A2 and B1 vying for 2nd place, and in the second race, you have A3, B2, and C1 racing for 3rd. Since we are trying to minimize the number of races, we can just combine the two into one race of 5 to determine the final outcome.
I'm guessing this is why it's an interview question. It's vague enough such that there are multiple solutions, which would allow the interviewers to glean a bit of your thought process.
We need Seven races
1. Divide equally 25 horses into 5 groups: A, B, C, D, E and run 5 races, we will get the following result:
A: A1 > A2 > A3 >.. B: B1 > B2 > B3 >.. C: C1 > C2 > C3 >.. D: D1 > D2 > D3 >.. E: E1 > E2 > E3 >..
Other horses were eliminated because they have no chance to belong to TOP 3 fastest horses.
2. Run 6th race with (A1, B1, C1, D1, E1), suppose the result is:
A: A1 > A2 > A3 > .. V B: B1 > B2 > B3 > .. V C: C1 > C2 > C3 > .. V D: D1 > D2 > D3 > .. V E: E1 > E2 > E3 > ..
For now, A1 is the fastest horse.
After finding out A1:
- D(x), E(x), C2 and C3 can be eliminated because [B1, C1] is always the better solution.
- B3 can also be eliminated because of [B1, B2].
A: A2 > A3 B: B1 > B2 V C: C1
3. Run 7th race with remaining horses, we will find out the second fastest and third fastest horse.
--Sandyvu (talk) 11:58, 2 April 2017 (UTC)
Consider the following case, where A is a group name and the numbers are the hypothetical speeds of the horses:
A = {91, 92, 93, 94, 95}
B = {81, 82, 83, 84, 85}
C = {71, 72, 73, 74, 75}
D = {61, 62, 63, 64, 65}
E = {51, 52, 53, 54, 55}
In this scenario, we need 8 races to determine first, second and third fastest horses.
Are we over-thinking this? Nothing is stated about presence or absence of stopwatches. Assuming that all races are run over the same distance, run 5 races, with 5 stopwatches timing the 5 competitors. That gives you 25 timings from which you can easily select the top three.
Back to Chapter 1.
