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