3.7 Problem 7: The Horse Race Puzzle

This problem is sometimes asked in a technical interview question at companies like Google (better be prepared!) (Youtube Video). The problem can be solved by a systematical ordering of the facts and a clear grouping and regrouping of objects, no more is needed – these are other important tasks in modeling in general. Order, sort, collect, and name the components before doing more creative things in modeling. Often, the elements “fall into the right place” just by naming them systematically. In mathematical modeling the key element is often to identify the right variables.

Let’s analyze the horse problem: Only 5 horses can race at the same time, so:

  1. Group the 25 horses into 5 groups of 5 horses. The groups are named a, b, c, d, e. Mark each horse with its group name. Hence, 5 horses are marked with an “a”, 5 with a “b”, and so on.

  2. Let each group race, that is, the five horses in group a do the first race, then the five horses in group b, etc. This gives 5 races.

  3. Mark each horse with its rang. Hence, the fastest horse in each group is marked with the number 1, the second fastest with number 2, etc. Each horse is now marked with its group name an its rank after the first five races.

  4. Let the 5 horses with number 1 do another race (race number 6).

  5. Order the 5 groups according to the fastest horses in that last race. So, for instance, suppose c1 is the fastest horse, second is b1, third is a1, fourth is d1, and the slowest is e1 in this 6th race, then order the groups from top to bottom accordingly as shown in Figure 7 (first row contains all horses named c; second row all horses named b, etc.).


    PIC
    Figure 7: Ordering of the Groups

  6. Clearly, the horse c1 is the fastest overall. Why? It is faster than any a horse (from the first race), and it is faster than any other 1 horse, and any 1 horse was faster than any 2 horse etc.

  7. Who is second and third? In the group of the 1 horses only b1 and c1 can be second or third (but not d1 or e1). In group a only a1 could be third (all others in group a were slower). In group c and b the two fastest (beside c1) can be second or third. So let race the horses c2, c3, b1, b2, and a1 a final time (race number 7). The two fastest horses in that last race are second and third.


    PIC
    Figure 8: Ordering of the Groups

Another important concept in modeling appears here: We simplify by leaving out the unessential, but we simplify also by implicitly assuming certain conditions. In our example of the horse racing, we suppose that the horses perform in the same way in each race, that is, the fastest in the first race is also the fastest in the 6th race, for instance. In all real problems, this is an idealized assumption. We know that this is not true. So, is the model then useless? Well, it depends on the context. In our horse-race example we may define the horse to be the fastest if it is the fastest in the 6th race, but it might have been slower than any other 1 horse in the 5 first races (when measured by a watch). In any case, it is important to be aware of all hidden assumptions of a model and in what context it would be inappropriate to apply the model.