Wednesday, October 20, 2010
Car Race Puzzle (Google)
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