Re: Horse Race Puzzle

*To*: mathgroup at smc.vnet.net*Subject*: [mg9191] Re: [mg9162] Horse Race Puzzle*From*: "Fred Simons" <wsgbfs at win.tue.nl>*Date*: Tue, 21 Oct 1997 02:03:04 -0400*Sender*: owner-wri-mathgroup at wolfram.com

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