MathGroup Archive 1997

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Horse Race Puzzle

In the following solution I restrict myself to the number of different
finishes; the complete list of all possible finishes can be constructed
in a similar way, but I am afraid that already for relative small
values of N the system will crash due to lack of memory.

The result of each race is a list of time of arrivals; on each arrival
time a group of horses finishes. A result will be of type T[n1, n2,
..., np] if there are n1 arrival times on which exactly one horse
finishes, n2 arrival times on which exactly two horses finish, etc.
Obviously, n1 + ... + np is the number of different arrival times and
n1 + 2 n2 + ... + p np = N.

Assume that we have a result of type T[n1, ..., np] for N horses, and 
that we let another horse enter the race. This extra horse may finish 
alone, which yields  (n1 + ... + np + 1) results of type T[n1+1, n2, 
..., np], or it may finish in a time of i of the other horses. The 
latter situation yields ni results of type T[ n1, ..., ni-1,  n(i+1)+1,
..., np] if i<p and np solutions of type T[n1, ..., np-1,  1] if i =p.

This construction can be implemented in the following way:

f[ T[ a__] ] := Module[ {arg = {a}, result, aux, i =1}, 
  aux = arg;
  aux[[1]] = aux[[1]] + 1;
  result = (1+Plus @@ arg) (T @@ aux);
  While[ i < Length[arg],
    aux = arg;
   aux[[i]] = aux[[i]]-1;
   aux[[i+1]] = aux[[i+1]]+1;
   result = result + arg[[i]] (T @@ aux);
   i = i+1];
  aux = arg; aux[[-1]] = aux[[-1]] - 1; AppendTo[aux,1];
  result=  result + arg[[-1]]	(T @@ aux) 

f[ n_Integer x_T] := Expand[ n f[x] ]

f[ x_Plus] := Expand[ f /@ x ]

Obviously, for N=1, there is only one result of type T[1].

To find all types of results for N = 3:

In[1] := n = 3; Nest[ f, T[1], n-1 ]

Out[1] = 6 T[3]+6 T[1,1]+T[0,0,1]

If we want to find the number of different finishes, we have to set  all
T-functions to 1. For example, for n = 20:

In[2] := n =20; Nest[ f, T[1], n-1 ] /. T[___]->1

Out[2] = 2677687796244384203115

Fred Simons
Eindhoven University of Technology

  • Prev by Date: Re: Help with findroot
  • Next by Date: RE: Horse Race Puzzle
  • Previous by thread: Horse Race Puzzle
  • Next by thread: RE: Horse Race Puzzle