• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Another horse race

 
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In a horse race there are N horses.In how many ways they can finish the race?
 
Ranch Hand
Posts: 1923
Scala Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Assuming two horses, they can finish:
1-2
2-1
(1,2) dead race
1 (2 DNF)
2 (1 DNF)
(1,2 DNF)

DNF: Did not finish. (Horse lost jockey, for instance).
Instead of DNF disqualification could occur.
But the difference isn't important for betters or price-money.

Do you have a more clean abstract idea of 'finishing' a race.

Of course we should argue, whether 'did not finish' is a way to finish.
Sounds absurd.
 
Ranch Hand
Posts: 867
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In how many ways they can finish the race?
If I understand what you ask
Um..........
Assume that there are n horse and without any accident within the racing
the permutation will be nx(n-1)....x1 ==n!

If one accident occurs
the permutation will be 2(n)x2(n-1)....x1== 2(n)!-1

If there are k accident
the permutation will be k(n)xk(n-1)x....x1== k(n)!-(k-1)

It may be wrong
Does it require to write a program to show it out all the permutation and generate it out?
[ October 05, 2004: Message edited by: siu chung man ]
 
Arjun Shastry
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No accident.Assume everything goes well.
Suppose there are two horses,1 and 2 then race can be finished as
1 finished the race followed by 2
1 and 2 finish at the same time.
2 finished the race followed by 1
So there are three ways in which 2 horses can finish the race.
Hope this helps.
 
Stefan Wagner
Ranch Hand
Posts: 1923
Scala Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Excluding dead-race, we get n! results for n horses.

But how many dead-races are possible?
n possibilities
1 0
2 1
3 7
4 ... ?

Hm.
With result of the race, are we interested in every position, or only in the first 3 horses?
 
Arjun Shastry
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes,dead race means reaching at same time ,right? if we exclude that then n! possibilities.But we want to consider dead race!!.That is interesting.Actually its integer partition problem.
Say there are 4 horses then 4 can be partitioned as
4----Means all arrive at same time
1+1+2(one followed by second and rest arrive at same moment).Now 2 horses can be chosen in 6 ways.and another horse in two ways.So there will be 6*3! ways in which this combination can arrive.
in similar fashion,
1+1+1+1 Each arrives at different time,4!,24 ways
1+3---4*2! ways
2+2---6 ways
In all there are 75 ways
How to generalize for N?I am not sure.
 
Arjun Shastry
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is there any similarity between this and factorization of a number.?
Say number is 24.Factors are 2,2,2,3.Number of ways in which 24 can be factored are
2*(12),2*2*(6),2*3*(4),2*2*2*3,3*(8),4*6
 
Ranch Hand
Posts: 309
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Arjun Shastry:
Is there any similarity between this and factorization of a number.?
Say number is 24.Factors are 2,2,2,3.Number of ways in which 24 can be factored are
2*(12),2*2*(6),2*3*(4),2*2*2*3,3*(8),4*6



Let me try.
1. No dead races(one winner) = n!
2. 2 winners = nc2*(n-2)!
We have nc2 ways to choose 2 winners. The rest (n-2) can be arranged in (n-2)!

So on and so forth.

Total = nc1*(n-1)! + nc2*(n-2)! + nc3*(n-3)! + ....+ ncn(n-n)!

Notes: First term = n! is essentially point# 1 stated above.
Last term = 1 = all horses are winners


Is this OK?

SHankar.
[ October 25, 2004: Message edited by: shankar vembu ]
 
shankar vembu
Ranch Hand
Posts: 309
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by shankar vembu:


Let me try.
1. No dead races(one winner) = n!
2. 2 winners = nc2*(n-2)!
We have nc2 ways to choose 2 winners. The rest (n-2) can be arranged in (n-2)!

So on and so forth.

Total = nc1*(n-1)! + nc2*(n-2)! + nc3*(n-3)! + ....+ ncn(n-n)!

Notes: First term = n! is essentially point# 1 stated above.
Last term = 1 = all horses are winners


Is this OK?

SHankar.

[ October 25, 2004: Message edited by: shankar vembu ]



I assumed that dead race applies only to position 1.
A more general solution would be:

Let A(n) = total no. of arrangements for n horses(where dead races are possible in every position).
So A(n) = nc1.A(n-1) + nc2.A(n-2) + nc3.A(n-3).........
where (recurse....)
A(n-1) = (n-1)c1.A(n-2) + (n-1)c2.A(n-3) + (n-1)c3.A(n-4)......
A(n-2) = (n-2)c1.A(n-3) + (n-2)c2.A(n-4) + (n-2)c3.A(n-5)......
.
.
.
.
.
I guess I am near to the solution. Any other formulations?
Basically, this would be a "bottom-up" computation.

SHankar
[ October 25, 2004: Message edited by: shankar vembu ]
 
reply
    Bookmark Topic Watch Topic
  • New Topic