There are 25 horses and the race track only allows 5 horses to race at a given time. Given that there is no stop watch available your task is to determine the fastest 3 horses. Assume that each horses speed is constant in different races, what is the minimum number of races to determine the fastest 3?
Answer=7
The key here is to keep the search space to only those horses which can be the top 3 horses.
Initially all 25 can be the required horses. So divide among groups of 5 and perform the race. Let the result be:
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 perform the race for winners of each group to reduce the search space. Let the result be:
A1 B1 C1 D1 E1
This implies A1 is the best. Also, the search space for top 3 horses reduces to:
A1 A2 A3 B1 B2 C1
Now conduct the last race for A2 A3 B1 B2 C1. Select top 2 from this race which will be overall runner-up and second runner-up.
Total race count = 7.
http://dailybrainteaser.blogspot.com/2011/03/28march.html
Answer=7
The key here is to keep the search space to only those horses which can be the top 3 horses.
Initially all 25 can be the required horses. So divide among groups of 5 and perform the race. Let the result be:
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 perform the race for winners of each group to reduce the search space. Let the result be:
A1 B1 C1 D1 E1
This implies A1 is the best. Also, the search space for top 3 horses reduces to:
A1 A2 A3 B1 B2 C1
Now conduct the last race for A2 A3 B1 B2 C1. Select top 2 from this race which will be overall runner-up and second runner-up.
Total race count = 7.
http://dailybrainteaser.blogspot.com/2011/03/28march.html
No comments:
Post a Comment