There are six runners in the 100-yard dash. How many ways are there for three medals to be awarded if ties are possible? (The runner or runners who finish with the fastest time receive gold medals, the runner or runners who finish with exactly one runner ahead receive silver medals, and the runner or runners who finish with exactly two runners ahead receive bronze medals.)
I saw a few cases:
Case I: No Ties
P(6,3) = 120 ways to pick the gold medal
Case II: 2 people tie
First we must pick the two people who tie, this can be done C(6,2) = 15 ways. Now I have to pick a medal for them to win, which opens up more cases because if they tie for first no silver medal is awarded and if they tie for second no bronze medal is awarded.
My problem with this method is that it takes way too long to consider all the cases and wouldn't be practical if I was writing a test, or if I was designing an algorithm for this type of question. I'm wondering if there is a more efficient way to solve this?
My book gave the answer $873$ if that helps at all