Skip to main content.

Hint to puzzle 131: Horse race

Begin by considering fewer horses.  Develop a systematic way of counting the possible outcomes.

Consider the case of four horses.  The horses may finish in 1, 2, 3, or 4 blocks.  Labeling the horses a, b, c, d, one example of three blocks is: (a) (b) (c, d).  This means that horses c and d have tied, and that horses a, b, and (c, d) have finished separately.  Determine the number of ways n horses can cross the finishing line in 1, 2, 3, and 4 blocks.

Note further that the three blocks -- (a), (b), (c, d) -- may be arranged in 3! = 6 ways.  Clearly this is true of any partition that consists of three blocks.

Finally, develop a recurrence relation to facilitate the calculation of S(n, k) = number of ways n horses can cross the finishing line in k blocks.