How many ways are there for three medals to be awarded if ties are possible? The Question
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.)
My Attempt
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
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?
The Answer
My book gave the answer $873$ if that helps at all
 A: Let $n$ be the number of gold medals awarded.
$\textbf{1)}\;\;$If $n=2$, then there are $\binom{6}{2}=15$ ways to choose the gold medalists and
$\hspace{.3 in}2^4-1=15$ ways to choose the bronze medalists, so there are $15\cdot15=225$ possibilities.
$\textbf{2)}\;\;$ If $n=1$, there are $\binom{6}{1}$ ways to award the gold medal, and then 
there are $\binom{5}{1}=5$ ways to award one silver medal and $2^4-1=15$ ways to award bronze medals, and
there are $\binom{5}{2}+\cdots+\binom{5}{5}=2^5-\binom{5}{0}-\binom{5}{1}=26$ ways to award more than one silver medal;
so in this case there are $6[5\cdot15+26]=606$ possibilities.
$\textbf{3)}\;\;$ If $n\ge3$, there are $\binom{6}{3}+\cdots+\binom{6}{6}=2^6-\binom{6}{2}-\binom{6}{1}-\binom{6}{0}=42$ ways to award the gold.
Therefore there are a total of $225+606+42=873$ ways to award the medals. 
A: Maybe the best way to break it down is by cases likes this:


*

*6 win gold (1 possibility)

*5 win gold (6 possibilities)

*4 win gold (${6 \choose 2}=15$ possibilities)

*3 win gold (${6 \choose 3}=20$ possibilities)

*2 win gold, four win bronze (15 possibilities)

*2 win gold, three win bronze (60 poss.)

*2 win gold, two win bronze (90 poss.)

*2 win gold, one wins bronze (60 poss.)

*1 wins gold, 5 win silver (6 poss.)

*1 wins gold, 4 win silver (30 poss.)

*1 wins gold, 3 win silver (60 poss.)

*1 wins gold, 2 win silver (60 poss.)

*1 wins gold, 1 win silver, 4 win bronze (30 poss.)

*1 wins gold, 1 win silver, 3 win bronze (120 poss.)

*1 wins gold, 1 win silver, 2 win bronze (180 poss.)

*1 wins gold, 1 win silver, 1 win bronze (120 poss.)


Then we have
$$1 + 6 + 15 + 20 + 15 +60+90+60+6+30+60+60+30+120+180+120= 873$$
Bingo!
