You are given five race tracks and twenty five horses.Find the minimum number of races you need to organize to find the fastest three horses. Here five race tracks means that only five horses can run at a time.
Solution
The trick to approach these type of problem is to consider the corner cases, most of the times what seems obvious is not what is true.
Lets name the five tracks as
T1 , T2, T3 , T4 , T5
and we organize five races in the beginning Let us say that we have the horses named from A ? Y.
Lets organize the below races on the respective tracks:
T1 ? A , B , C , D , E -- Race1
T2 ? F , G , H , I , J -- Race2
T3 ? K , L , M , N , O -- Race3
T4 ? P , Q , R , S , T -- Race4
T5 ? U , V , W , X , Y -- Race5
We can safely assumed that the horses
A , B , C , D , E are rank 1 , 2 , 3 , 4 , 5 on track T1 ,
F , G , H , I , J are rank 1 , 2 , 3 , 4 , 5 on track T2 ,
K , L , M , N , O are rank 1 , 2 , 3 , 4 , 5 on track T3 ,
P , Q , R , S , T are rank 1 , 2 , 3 , 4 , 5 on track T4 ,
U , V , W , X , Y are rank 1 , 2 , 3 , 4 , 5 on track T5 ,
A , F , K , P , U are the fastest horses on their respective tracks T1 , T2 , T3 , T4 , T5.
At this point of time we can be sure of just one thing, that the fastest horse among the twenty five horses is one among A , F , K , P , U.
Hence we organize one more race on any of the track lets say T1 to find the fastest horse.
T1 -- A , F , K , P , U ? Race6
We can safely assume that A got rank 1, F got rank 2, K got rank 3 , P got rank 4 and U got rank 5. So the fastest horse among the twenty five horses is A.
At this point most of us make a mistake, we blindly say that F is second and K is third among the 25 horses,
but the reality is that F is slower than A and K is slower than F. We do not know if F is also slower than B , C , D , E and also we do not know if K is slower than G , H , I , J .
So we need to choose horses among B , C , D , E , F , G , H , I , K to get the second and third horses. We have a condition to test
1) B and C migth be faster than F, so we need to test them with F, hence the next race must include B , C , F for sure
2) B and C might be slower than F, so in that case F is the second fastest horse and we need to choose the third horse from G and K.
Hence the next race will have the horses B , C , F , G and K ? Race7 running, lets say that C got rank 1 and F got rank 2, then C is the second fastest and F is the third fastest horse in the 25 horses.
Answer
Hence the answer is 7 races
Solution
The trick to approach these type of problem is to consider the corner cases, most of the times what seems obvious is not what is true.
Lets name the five tracks as
T1 , T2, T3 , T4 , T5
and we organize five races in the beginning Let us say that we have the horses named from A ? Y.
Lets organize the below races on the respective tracks:
T1 ? A , B , C , D , E -- Race1
T2 ? F , G , H , I , J -- Race2
T3 ? K , L , M , N , O -- Race3
T4 ? P , Q , R , S , T -- Race4
T5 ? U , V , W , X , Y -- Race5
We can safely assumed that the horses
A , B , C , D , E are rank 1 , 2 , 3 , 4 , 5 on track T1 ,
F , G , H , I , J are rank 1 , 2 , 3 , 4 , 5 on track T2 ,
K , L , M , N , O are rank 1 , 2 , 3 , 4 , 5 on track T3 ,
P , Q , R , S , T are rank 1 , 2 , 3 , 4 , 5 on track T4 ,
U , V , W , X , Y are rank 1 , 2 , 3 , 4 , 5 on track T5 ,
A , F , K , P , U are the fastest horses on their respective tracks T1 , T2 , T3 , T4 , T5.
At this point of time we can be sure of just one thing, that the fastest horse among the twenty five horses is one among A , F , K , P , U.
Hence we organize one more race on any of the track lets say T1 to find the fastest horse.
T1 -- A , F , K , P , U ? Race6
We can safely assume that A got rank 1, F got rank 2, K got rank 3 , P got rank 4 and U got rank 5. So the fastest horse among the twenty five horses is A.
At this point most of us make a mistake, we blindly say that F is second and K is third among the 25 horses,
but the reality is that F is slower than A and K is slower than F. We do not know if F is also slower than B , C , D , E and also we do not know if K is slower than G , H , I , J .
So we need to choose horses among B , C , D , E , F , G , H , I , K to get the second and third horses. We have a condition to test
1) B and C migth be faster than F, so we need to test them with F, hence the next race must include B , C , F for sure
2) B and C might be slower than F, so in that case F is the second fastest horse and we need to choose the third horse from G and K.
Hence the next race will have the horses B , C , F , G and K ? Race7 running, lets say that C got rank 1 and F got rank 2, then C is the second fastest and F is the third fastest horse in the 25 horses.
Answer
Hence the answer is 7 races
No comments:
Post a Comment