Skip to content

Solution to find top 5 from 25 horses by racing 5 at a time

May 17, 2011

There are 25 horses. First 5 races can be done with random groups of 5 horses and we will get 5 Ordered Sets of Horses and then have a sixth race of all the Toppers got from above 5 races. This will give us our Topper. Let’s say, below are the five ordered sets we received and A1, B1, C1, D1, E1 is the ordered result from 6th race. We will have following matrix.

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

Now, A1 is the topper, we need to find next 4 and for that we can erase the candidates like E2,E3,E4,E5, because we already know B1,C2,D1,E1 are ahead of them, similarly D3,D4,D5,C4,C5,B5 can be erased from the eligible candidates.

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

Now, the candidates for second position are A2, B1. We have 2 use cases here.

If position 2 =A2 If No.2 =B1
Candidates for position 3 = B1,A3 Candidates for position 3 = A2,B2,C1

So, possible candidates for 7th race will be A2, B1, A3, B2, and C1. This race will provide top 3 horses. First position in 7th race will be 2nd top horse and second will be 3rd top horse. Now, we need to get 4th and 5th positions. For that, it needs 8th race with following candidates.

Topper 1 = A1

Topper2

A2

B1
Topper3

B1

A3

A2

B2

C1

Topper4 B2 A3 C1 B1 A4 A3 B2 C1 B3 C1 A2 A2 B2 C2 D1
Topper5 A3,B3,C1 A4,B2,C1 A3,B2,C2,

D1

A4,B2,C1 A5,B1 A4,B2,C1 A3,B3,C1 A2,B3,C2,

D1

A2,B4,C1 A2,B3,C2,

D1

A3,B3,C1 A3,B2,C2,

D1

B3,A2,C2,

D1

A2,B2,C3,

D1

A2,B2,C2,

D2,

E1

Now we need to see if in each of the above usecase, one race is sufficient, which is 8th race. Also, in 8th race, third position from 7th race will take part and so we can remove the candidates used in 7th race in each usecase, as we already know their ordering amongst themselves.

So let’s take each use case and find eligible candidates for 8th race, if there are more than 5, then 9th race is needed else not. Let’s traverse each path in the matrix for the possible candidates, with 7th race results to get 4th and 5th topper. Recap: 7th race was between A2, B1, A3, B2, and C1.

1. If 7th race 1st,2nd positions are: A2,B1 respectively

Eligible Candidates for 4th are: B2, A3, and C1.  This means 3rd position in 7th race will give 4th topper.

8th race is needed for 5th position and candidates for 8th race will be: 4th position in 7th race, B3, A4, C2 and D1.

2.  If 7th race 1st,2nd positions are: A2,A3 respectively

Eligible Candidates for 4th topper are: B1 and A4. Here 3rd position in 7th race is B1.

8th race is needed for 4th and 5th positions and candidates for 8th race will be: B1, A4, A5 and 4th position from 7th race.

3. If 7th race 1st,2nd positions are: B1,A2 respectively

Eligible Candidates for 4th are: B2, A3, and C1.  This means 3rd position in 7th race will give 4th topper.

8th race is needed for 5th position and candidates for 8th race will be: 4th position in 7th race, B3, A4, C2 and D1.

4.  If 7th race 1st,2nd positions are: B1,B2 respectively

Eligible Candidates for 4th topper are: B3, C1, and A2. 3rd position in 7th race can give either C1 or A2. So candidates who will take part in 8th race will be 3rd position in 7th race, B3.

8th race is needed for 4th and 5th positions and candidates for 8th race will be:  3rd position from 7th race, 4th position from 7th race, B4, C2, D1

5.  If 7th race 1st,2nd positions are: B1,C1 respectively

Eligible Candidates for 4th topper are: A2, B2, C2, and D1. 3rd position in 7th race can give either A2 or B2. So candidates who will take part in 8th race will be 3rd position in 7th race, C2 and D1.

8th race is needed for 4th and 5th positions and candidates for 8th race will be:  3rd position from 7th race (either A2 or B2 or A3), 4th position from 7th race (either A2 or B2 or A3), B3, C2, D1, C3, D2, E1. This scenario will need a 9th race.

So, Answer to this puzzle is atmost 9 races are needed to get first 5 toppers.

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: