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

• 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