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

Posers and Puzzles

  1. 20 May '08 13:56
    In how many ways, counting ties, can eight horses cross the finishing line?

    (For example, two horses, A and B, can finish in three ways: A wins, B wins, A and B tie.)
  2. Standard member wolfgang59
    Infidel
    20 May '08 16:27 / 1 edit
    8! is the wrong answer
  3. Standard member forkedknight
    Defend the Universe
    20 May '08 20:11 / 3 edits
    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...
  4. Standard member forkedknight
    Defend the Universe
    21 May '08 18:28 / 2 edits
    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
  5. Standard member forkedknight
    Defend the Universe
    21 May '08 18:28
    I don't have time to simplify that; someone else can if they want...
  6. Standard member forkedknight
    Defend the Universe
    21 May '08 18:32
    btw, i is the number of horses in each tie...