8
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ And I guess, in theory, you could have 3-way, 4-way, 5-way, and 6-way ties too! If 4 people tied for first, it seems that that would break the question, since more than 3 medals would be needed. I guess the question really becomes: How many ways can 6 things be partitioned? $\endgroup$
    – JLee
    Nov 7, 2014 at 1:05
  • $\begingroup$ So what you're saying is this is basically the question how many ways can I put 6 marbles in 3 distinct jars? $\endgroup$
    – Dunka
    Nov 7, 2014 at 1:12
  • $\begingroup$ I think it's a little different dunka, because if 3 people tie for gold, the silver and bronze medals are not awarded. That's to say, you don't want to count the case in which there are 3 marbles in the first jar, then 2 in the second, then 1 in the third. $\endgroup$
    – Shane
    Nov 7, 2014 at 1:15
  • $\begingroup$ @Shane very true. Should I proceed with cases, knowing that 4 way ties or more would actually break the questions rules? $\endgroup$
    – Dunka
    Nov 7, 2014 at 1:17
  • 3
    $\begingroup$ I'm not sure, to be honest. I'm one of those annoying commenters who only points out problems with what you're doing rather than offering solutions! Hopefully somebody smarter than I will intervene at any moment now :P $\endgroup$
    – Shane
    Nov 7, 2014 at 1:18

2 Answers 2

Reset to default
8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Shane this was the answer we were looking for! $\endgroup$
    – Dunka
    Nov 9, 2014 at 0:34
  • $\begingroup$ Can you please explain the logic here? Do you mean in case 3 wins gold, so there will be no place for silver and bronze? If 2 wins gold, there will be no place for silver but for bronze (either 1, 2, 3, 4) WhY please? $\endgroup$
    – Avv
    Jul 6, 2021 at 21:13
8
$\begingroup$

Maybe the best way to break it down is by cases likes this:

  1. 6 win gold (1 possibility)
  2. 5 win gold (6 possibilities)
  3. 4 win gold (${6 \choose 2}=15$ possibilities)
  4. 3 win gold (${6 \choose 3}=20$ possibilities)
  5. 2 win gold, four win bronze (15 possibilities)
  6. 2 win gold, three win bronze (60 poss.)
  7. 2 win gold, two win bronze (90 poss.)
  8. 2 win gold, one wins bronze (60 poss.)
  9. 1 wins gold, 5 win silver (6 poss.)
  10. 1 wins gold, 4 win silver (30 poss.)
  11. 1 wins gold, 3 win silver (60 poss.)
  12. 1 wins gold, 2 win silver (60 poss.)
  13. 1 wins gold, 1 win silver, 4 win bronze (30 poss.)
  14. 1 wins gold, 1 win silver, 3 win bronze (120 poss.)
  15. 1 wins gold, 1 win silver, 2 win bronze (180 poss.)
  16. 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!

$\endgroup$
7
  • $\begingroup$ This may be right. My book gives the answer of $873$ however, this is still a time consuming method. I'm wondering if there is an easier way than cases to do this. $\endgroup$
    – Dunka
    Nov 7, 2014 at 1:34
  • 1
    $\begingroup$ Ooh... now you've given me an answer... let's see if I can get to it. Here come some edits! $\endgroup$
    – Shane
    Nov 7, 2014 at 1:36
  • 1
    $\begingroup$ Now the goal is for somebody smarter to show us how to do this faster. Anybody? $\endgroup$
    – Shane
    Nov 7, 2014 at 1:53
  • 1
    $\begingroup$ Thanks for the solution. However, I still want to know if there is a better way than cases to do this one. $\endgroup$
    – Dunka
    Nov 7, 2014 at 1:54
  • $\begingroup$ I would be curious to see that also. In particular, if there are $n$ runners rather than $6$, my approach wouldn't be practical. I'm sure you express the above as some rather complicated sum of sums... $\endgroup$
    – Shane
    Nov 7, 2014 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.