Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member uzless
    The So Fist
    15 Jul '08 18:16
    In how many ways, counting ties, can eight cars cross the finishing line?

    (For example, two cars, A and B, can finish in three ways: A wins, B wins, A and B tie.)
  2. 15 Jul '08 18:17
    Originally posted by uzless
    In how many ways, counting ties, can eight cars cross the finishing line?

    (For example, two cars, A and B, can finish in three ways: A wins, B wins, A and B tie.)
    This makes me think of horses.
  3. 15 Jul '08 18:18
    Originally posted by heinzkat
    This makes me think of horses.
    http://www.redhotpawn.com/board/showthread.php?subject=Horse_race&threadid=94066
  4. Standard member uzless
    The So Fist
    15 Jul '08 18:25
    Originally posted by heinzkat
    http://www.redhotpawn.com/board/showthread.php?subject=Horse_race&threadid=94066
    Ya, but this one is about cars damn it!
  5. 15 Jul '08 18:44
    Originally posted by uzless
    Ya, but this one is about cars damn it!
    ...with horse powers...
  6. Subscriber AThousandYoung
    It's about respect
    18 Jul '08 07:43 / 1 edit
    8! Different possibilities if no two cars pass at the same time. Added to that are all the different possible ties, including ties for 2nd, 3rd etc.

    If it were only 3 cars, it'd be 3! = 6 plus the ties. There are 6 possible 2 way ties for 1st and 6 for 2nd. There is one possible three way tie. That's 19 possibilities.

    4 cars, we have 4! = 10 plus the 4 way tie, 4 3 way ties, 4 1 way ties, and 12 2 way ties, each multiplied by all the positions they can be in...

    This does not seem like an easy problem.
  7. Standard member forkedknight
    Defend the Universe
    18 Jul '08 13:45
    The link to the "horse race" thread contains my attempted solution. Not sure if anyone has taken a deeper look at it...
  8. Standard member uzless
    The So Fist
    18 Jul '08 16:40
    Originally posted by AThousandYoung
    8! Different possibilities if no two cars pass at the same time. Added to that are all the different possible ties, including ties for 2nd, 3rd etc.

    If it were only 3 cars, it'd be 3! = 6 plus the ties. There are 6 possible 2 way ties for 1st and 6 for 2nd. There is one possible three way tie. That's 19 possibilities.

    4 cars, we have 4! = 10 ...[text shortened]... multiplied by all the positions they can be in...

    This does not seem like an easy problem.
    It indeed is no simple one. I didn't check to see the other threads answer, but if it doesn't start iwth 5 then it is wrong.
  9. Subscriber AThousandYoung
    It's about respect
    19 Jul '08 00:43
    Originally posted by forkedknight
    The link to the "horse race" thread contains my attempted solution. Not sure if anyone has taken a deeper look at it...
    [i]the Sum from i=1 to 8 of ( C(n, i) * P(n-i+1, n-i+1) )

    *edit* where:
    C(n, k) is the number of combinations of size k from a set of size n, and
    P(n, r) is the number of permutations of size r from a set of size n

    *edit 2*
    and n = 8

    *edit 3*
    and this only accounts for cases where there is only one tie, but that tie can be between any or all of the horses, so it's not a complete solution...




    this should be a complete answer....

    from my previous answer:
    for i = 1:
    P(8,8) = 8!
    for i = 2:
    for 1 tie: C(8, 2) * P(7, 7) = 8!/(6!2!) * 7!
    for 2 ties: C(8,2) * C(6,2) * P(6,6) = 8!/(6!2!) * 6!/(4!2!) * 6!
    for 3 ties: C(8,2) * C(6,2) * C(4,2) * P(5,5) = " * " * 4!/4 * 5!
    for 4 ties: C(8,2) * C(6,2) * C(4,2) * C(2,2) * P(4,4) = " * " * " * 2 * 4!
    for i = 3:
    for 1 tie: C(8,3) * P(6,6) = 8!/(5!3!) * 6!
    for 2 ties: C(8,3) * C(5,3) * P(4,4) = 8!/(5!3!) * 5!/(3!2!) * 4!
    for i = 4:
    for 1 ties C(8,4) * P(5,5) = 8!/(4!4!) * 5!
    for 2 ties C(8,4) * C(4,4) * P(2,2) = 8!/(4!4!) * 1 * 2
    for i = 5:
    only 1 tie possible: C(8,5) * P(4,4) = 8!/(3!5!) * 4!
    for i = 6:
    " " " ": C(8,6) * P(3,3) = 8!/(6!2!) * 6
    for i = 7:
    " " " ": C(8,7) * P(2,2) = 16
    for i = 8: 1

    Therefore, the total is:
    1 + 16 + 8!/(6!2!) * 6 + 8!/(3!5!) * 4! + 8!/(4!4!) * 5 * 2 +

    8!/(4!4!) * 5! + 8!/(5!3!) * 5!/(3!2!) * 4! + 8!/(5!3!) * 6! +

    8!/(6!2!) * 6!/(5!2!) * 4!/4 * 2 * 4! +

    8!/(6!2!) * 6!/(4!2!) * 4!/4 * 5! +

    8!/(6!2!) * 6!/(4!2!) * 6! + 8!/(6!2!) * 7! + 8!

    *edit* fixed errors

    Thread 94066
  10. 19 Jul '08 17:33
    OK, I have an answer for this one, but first the approach.

    The possibility of ties in any number of ways complicates calculations greatly, and so the first step is to list all possible kinds of car groupings first, where a "group" of cars are all the cars that tied for a particular position. The actual position tied for does not matter at this point, but will be considered later.

    No ties is one possibility, while an eight-way tie is the opposite possibility. A three-way tie and a two-way tie is also a possibility.

    After these are listed out, I then consider each one separately, counting the total number of ways the cars could be grouped and multiplying it by the number of orders the groups could finish, and accounting for duplications based on several groups being the same size.

    After calaculating this for every possible scenario, I then add up the number of possibilities.

    My answer was 545,835 ways broken down like this.

    * 8-way tie - 1
    * 7-way tie - 16
    * 6-way tie and 2-way tie - 56
    * 6-way tie - 168
    * 5-way tie and 3-way tie - 112
    * 5-way tie and 2-way tie - 1,008
    * 5-way tie - 1,344
    * 2 4-way ties - 70
    * 4-way tie and 3-way tie - 1,680
    * 4-way tie and 2 2-way ties - 1,260
    * 4-way tie and 2-way tie - 10,080
    * 4-way tie - 8,400
    * 2 3-way ties and 2-way tie - 1,680
    * 2 3-way ties - 6,720
    * 3-way tie and 2 2-way ties - 20,160
    * 3-way tie and 2-way tie - 67,200
    * 3-way tie - 40,320
    * 4 2-way ties - 2,520
    * 3 2-way ties - 50,400
    * 2 2-way ties - 151,200
    * 2-way tie - 141,120
    * No ties - 40,320

    GRAND TOTAL - 545,835 ways to finish..

    Feel free to analyze and correct any mistakes above.