20th, October, 2010
Given 49 cars and 7 tracks of equal length. No two have the same speed. How to find the 25th fastest car? At least how many races are needed? The puzzle posted here.
I am providing my initial thought on the puzzle. We are given 49 cars and 7 tracks. We can arrange them into 7 groups. Conduct first race among these 7 groups, we will have seven ordered sets.
For easy reference, let us name them from group A through group G. Further, in group A, let us name the best car as A1 and last car as A7. Similarly other groups. Now conduct one more race among the winners of all groups. At this point we needed 8 races to figure out groups order along with order in each group. We can represent them in the following matrix form.
For simplicity, assume that the result of 8th race is A1 through G1. We can arrange them as shown in the above diagram.
By careful observation, we can avoid those cars in red border, since they can’t fall in the first 25 places. We can also avoid A1, since it occupies first place.
Now we have 24 cars, some preprocessed information and 7 tracks. How best can we group them with the preprocessed information in hand, and having 7 tracks. Obviously, we need to group them in 3 groups, leaving 3 remaining.
[ If we observe, we have a matrix in which all rows sorted and only the first column sorted. Can we think of sorting the 2D matrix both vertically and horizontally? Locating 25th element in that matrix is our target. ]
From now I have fun, since I am not sure how to proceed.
Either A2 or B1 can occupy 2nd place. If B1 wins second place, we will end up in more races. Best possible case will arrive when A2 wins for second place.
Yet to fill
5 comments:
You have to find the 25th which means you want to find the slowest one of the 25 card left out. You can have the final race between A5 B5 C5 D5 E5 and whichever one comes 5th is the 25th once in the race
Your elimination strategy if the ones in red border is wrong.
Your solution is not correct.
After 7 races you know the order with in groups but dont know the order between groups. In the 8th race you know the 1st from each group but this case may also exist when 7th car of a group is faster than 1st car of b group.
For example :-
a1 a2 a3 a4 a5 a6 b1 b2 b3 b4 b5 b6 b7 c1 c2 c3 c4 c5 c6 c7 d1 d2 d3 d4 a7 ......
in this case a7 is the 25th car.
This sequence will hold your all conditions.
Please rethink about what i am trying to say.
were you able to solve this??
we can use Algo to find median of the median to find the ans. and ans is 8 race .
Post a Comment